Верхние полурешётки арифметических нумераций и арифметических m-степеней тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ИИ4604049

На правах рукописи

Подзоров Сергей Юрьевич ,

" /

Верхние полурешётки арифметических нумераций и арифметических ттг-степеней

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск - 2010

1 7 ИЮН ?0Ю

004604049

Работа выполнена в Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный консультант:

доктор физико-математических наук, профессор, чл.-корр. РАН Гончаров Сергей Савостьянович

Официальные оппоненты:

доктор физико-математических наук, профессор

Морозов Андрей Сергеевич,

доктор физико-математических наук, профессор

Корольков Юрий Дмитриевич,

доктор физико-математических наук, профессор

Добрица Вячеслав Порфирьевич

Ведущая организация:

Казанский государственный университет

Защита состоится 17 июня 2010 г. в 14 час. 00 мин. на заседании диссертационного совета Д.003.015.02 при Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института, математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан "__2010 г.

Ученый секретарь

диссертационного совета Д.003.015.02 кандидат физико-математических наук

Общая характеристика работы

Актуальность темы.

Нумерацией непустого не более чем счётного семейства Э* называется произвольное аорьективное отображение натурального ряда на 1. Если i> — нумерация J и vn = / € 1 для п € N. то число тг называется v-номером объекта /. Для нумераций и и ц мы говорим, что v сводится к /i и пишем v ^ /i, если существует всюду определённая вычислимая функция / : N —> N, такая что v = fi о /.

Фактически нумерация — это система имён для элементов У. Хорошо известно, что для теории вычислимости нет принципиальной разницы между словами конечного алфавита и натуральным рядом, поскольку между этими двумя типами объектов существует вычислимое взаимно однозначное соответствие. В связи с этим натуральные числа, являющиеся номерами объектов, могут восприниматься как слова-имена. Нумерация назначает каждому объекту из Т одно или несколько имён, которые могут служить входными данными для алгоритмов, в связи с чем появляется возможность говорить о вычислимости на 3* вне зависимости от того, какую природу имеют элементы этого семейства. Сводимость нумераций означает наличие эффективной процедуры трансляции, позволяющей переводить одни имена в другие.

Отношение сводимости на множестве всех нумераций семейства 3* является предпорядком. Ассоциированный с ним частичный порядок является верхней полурешёткой, которая обозначается

Допустим теперь, что у нас есть некое "универсальное" семейство S и нас интересуют нумерации подсемейств этого семейства. Предположим также, что уже имеется некоторая "естественная" система имён для S; то есть задан эффективный язык L, слова которого являются именами объектов из S, и отображение d : L —> S, сопоставляющее именам объекты с: этими именами. Тогда для У С S нумерация и семейства 1 называется вычислимой относительно L, если существует вычислимая функция / : N —» такая что и = /оd, то есть если по каждому ¡/-номеру объекта из 3* можно вычислить его "естественное" имя (имя в языке L). Множество всех вычислимых относительно L нумераций семейства 1 задаёт идеал в полурешётке Ж(З'), который обозначается 3^(9").

Первую идею о систематическом изучении нумераций и нумерованных множеств в России высказал А. Н. Колмогоров в середине 50-ых годов XX столетия. Развитие этой идеи, приведшее к созданию теории нумераций, принадлежит В. А. Успенскому (основные результаты

см. в [32]). Параллельно ряд зарубежных математиков (Райе, Деккер, Майхил, Фридберг, Лахлан, Роджерс) изучали схожие структуры, связанные с нумерациями семейств вычислимых функций и вычислимо перечислимых множеств. Впоследствии академик Л. И. Мальцев синтезировал советское и зарубежное направление исследований, сформировав теорию нумераций в современном виде и задав основные направления исследований на десятилетия вперёд (см. обзор [28], после этого обзора выходили также другие статьи А. И. Мальцева, посвященные нумераг циям).

Работы Мапльцева привели к тому, что начиная с 60-ых годов прошлого века основной интерес у исследователей стал вызывать случай, когда 8 равно семейству всех вычислимо перечислимых множеств, а "естественными" именами этого семейства, образующими язык Ь, являлись описания алгоритмов, эффективно перечисляющих множества. Нумерации, вычислимые относительно этого языка, назывались просто вычислимыми; другими словами, исторически термин "вычислимая нумерация" применялся к нумерациям семейств вычислимо перечислимых множеств, для которых существовала эффективная процедура, перечисляющая множество по его номеру. В конце 60-ых - начале 70-ых годов прошлого столетия были опубликованы десятки статей, посвященных полурешёткам вычислимых нумераций (достаточно подробная библиография того, что было опубликовано к середине 70-ых годов, есть в монографии академика Ю. Л. Ершова [23], посвящённой теории нумераций).

В 80-ых годах интерес к вычислимым нумерациям пошёл на спад, несмотря на то, что в теории вычислимых нумераций оставалось множество открытых проблем. Однако этот интерес снова возродился в середине 90-ых благодаря работе Гончарова и Сорби [18]. В этой работе, фактически, была предложена концепция вычислимости относительно "естественного" языка, описанная выше, и было показано, что классическое понятие вычислимой нумерации является частным случаем нумерации, вычислимой относительно языка. Поскольку термин "вычислимая нумерация" к тому времени уже устоялся, Гончаров и Сорби предложили термин "обобщённо вычислимая нумерация". В этой статье был дан старт к изучению обобщённо вычислимых нумераций; в первую очередь нумераций, вычислимых относительно одной из известных иерархий (разностная иерархия или иерархия Ершова, арифметическая иерархия, аналитическая иерархия). Мы не будем приводить здесь подробные определения, данные Гончаровым и Сорби, отметим

лишь, что вычислимость и каждой из этих иерархий может рассматриваться как вычислимость относительно некоторого эффективно заданного языка, естественного для этой иерархии. Кроме того, в случаях с разностной и арифметической иерархиями вычислимость нумерации относительно начального уровня этих иерархии равносильна вычислимости нумерации в классическом смысле.

После доклада С. С. Гончарова на международной конференции в г. Боулдер (США) в июне 1999 года, (тезисы доклада см. в [3]) тема получила широкий резонанс среди мировой научной обществественно-сти. Вычислимые нумерации стали изучать в Новосибирске (Россия), Алма-Ате (Казахстан), Сиене (Италия), Гейдельберге (Германия).

Одним из основных направлений исследований стали нумерации, вычислимые в арифметической иерархии. Дадим точные определения, касающиеся этого важного для нас случая. Пусть 3" С Е°+1 и I/ — нумерация семейства 3". Эта нумерация называется Е°-вычислимой, если множество {(ж, у) : х G иу} принадлежит классу Е°+1. Это равносильно тому, что по «/-номеру множества из 3* можно эффективно вычислить S, i+i-формулу языка арифметики первого порядка, выделяющую это множество на стандартной модели арифметики. Таким образом, Е®+1-вычиелимость нумерации является частным случаем вычислимости относительно языка. Идеал в полурешётке нумераций 3", образованный ¡-вычислимыми нумерациями, обозначается 3¿°+1(3") и называется полурешёткой Роджерса (Е"+1-вычислимых нумераций семейства 9~). В случае п = О полу решётка Роджерса 3¿i(3") совпадает с классической полурешёткой вычислимых нумераций.

Алгебраические и теоретико-модельные свойства полурешёток Роджерса Е® .^-вычислимых нумераций (неклассический случай, классический случай — это полурешётка Ж® (7)) стали темой множества публикаций. Помимо работ автора, посвященных этой теме, можно отметить работы [1, 2, 3, 11, 13, 12, 4], уже упоминавшуюся работу [18] и ряд других, не вошедших в список литературы. Все эти работы перекликаются с четвёртой главой диссертации, более того, в четвёртой главе решается ряд вопросов, поставленных в перечисленных работах.

Результаты, касающиеся арифметических нумераций, имеют обширные приложения в теории конструктивных моделей [19]. Это одно из основных направлений современной теории вычислимости, имеющее большую популярность среди исследователей как в России, так и за рубежом. О приложениях арифметических нумераций к конструктивным моделям смотри конструкции в книге [19], а также [5, 6, 4, 7].

Исследования полурешёток Роджерса со временем привели автора диссертации к исследованию арифметических т-степеней. Эти степени и связанная с ними т-сводимость -- один из основных объектов теории вычислимости, введённый Постом в 40-ых годах XX столетия. Они упоминаются во всех классических монографиях по теории вычислимости (см., например, [10, 30, 31]), им посвящены сотни статей различных авторов. Из наиболее фундаментальных результатов, полученных в разное время предшественниками автора диссертации и связанных с т-степенями, можно назвать следующие четыре:

(1) В 1972 году Лахлан описал типы изоморфизма главных идеалов полурешётки вычислимо перечислимых т-степеней [9, 10, 23];

(2) В 1975 Ершов и Палютин дали описание полурешётки всех т-степеней с точностью до изоморфизма в терминах с-универсаль-ных полурешёток [27, 10, 23];

(3) В 1978 Денисов дал характеризацию типа изоморфизма полурешётки всех вычислимо перечислимых т-степеней [20, 10];

(4) В 1980 Нероуд и Шор показали, что теория первого порядка полурешётки т-степеней вычислимо изоморфна арифметике второго порядка [10].

В третьей главе диссертации первый и третий результат из этого списка получили дальнейшее развитие. Характеризация Лахлана [9] обобщена на произвольные уровни арифметической иерархии, найдены новые примеры введённых Денисовым [20] универсальных полурешёток.

Лахлановское описание [9] задаёт полурешётки, изоморфные главным идеалам вычислимо перечислимых т-степеней довольно сложным образом. Они представлены в виде прямого предела последовательности конечных дистрибутивных решёток, удовлетворяющей списку из нескольких свойств (подробности в [9, 23, 10] и в первой главе диссертации). Позднее такие полурешётки были названы лахлановскими. Анализируя определение лахлановской полурешётки, можно заметить, что каждая лахлановская полурешётка является ограниченной дистрибутивной полурешёткой, имеющей Е^-представление. Вопрос о том, верно ли обратное, занимал умы многих исследователей, однако оставался открытым на протяжении более 30 лет. Отдельные частные случаи (ограниченные дистрибутивные решётки с Ед-представлениями, конструк-тивизируемые ограниченные дистрибутивные полурешётки), для которых доказательства в обратную сторону были найдены, использовались Ершовым в [23], однако общий случай оставался открытой проблемой.

Автор решает этот вопрос во второй главе диссертации, давая па него положительный ответ. Результат доказывается сразу для обобщённого случая п-лахлановских полурешёток.

Цель работы.

Работа посвящена исследованию алгебраических и алгоритмических свойств таких дистрибутивных верхних нолурешёток, как полурешётки арифметических т-степеней и полурещётки Роджерса арифметических нумераций, а также вообще полурешёток и решёток, имеющих арифметические представления различных типов.

Основные результаты.

В работе получены следующие основные результаты:

(1) Установлен ряд фактов, касапющихся арифметических представлений полурешёток: доказано, что п-лахлановские полурешётки — это, в точности, ограниченные дистрибутивные полурешётки, обладающие Х>^1+3-представлением; построен пример дистрибутивной решётки, конструктивизируемой как частичный порядок, но не конструктивизируемой как верхняя полурешётка; доказано, что каждый О'-конструктивизируемый локально решёточный частичный порядок имеет позитивное представление.

(2) Описаны типы изоморфизма главных идеалов в полурешётках арифметических т-степеней: получена полная локальная ха-рактеризация полурешёток арифметических т-степеней; доказано, что полурешётки гиперпростых, простых и принадлежащих классу Д(2 т-степеней, а также полурешётки Роджерса вычислимых нумераций конечного семейства, состоящего из попарно не сравнимых по включению множеств, изоморфны универсальной лахлановской полурешётке без наибольшего элемента.

(3) Исследованы типы изоморфизма главных идеалов в полурешётках Роджерса арифметических нумераций: доказано сильное достаточное условие на вложимость дистрибутивной полурешётки в арифметическую полурешётку Роджерса в качестве идеала; получена полная локальная характеризация полурешёток Роджерса арифметических нумераций конечных семейств;

(4) усилен результат Бадаева, Гончарова и Сорби о различии типов изоморфизма полурешёток Роджерса на разных уровнях

арифметической иерархии, разрыв между уровнями сокращён с 3 до 2;

(5) получен ряд достаточных условий существования минимальных накрытий в полурешётках Роджерса арифметических нумераций, полностью решён вопрос о минимальных накрытиях в полурешётках Роджерса арифметических нумераций конечных семейств.

Основные методы.

В работе использовались как общие методы теории решёток и теории вычислимости (в частности, методы приоритета с конечными и бесконечными нарушениями), так и специальный метод, основанный на конструкциях, использующих каркасы и башни. Этот метод был изобретён Лахланом [9] и впоследствии усовершенствован Денисовым [20], Ершовым [25], а также автором в ряде работ та списка диссертации.

Теоретическая и практическая ценность.

Работа носит теоретический характер. Ее результаты могут быть использованы для дальнейших исследований в области теории вычислимости вообще и теории нумераций в частности, при исследовании структуры полурешётки то-степеней и полурешёток степеней относительно других типов алгоритмической сводимости, а также для чтения специальных курсов для студентов и аспирантов, специализирующихся в указанных областях.

Научная новизна работы.

Все основные результаты диссертационной работы являются новыми. Апробация результатов работы.

Результаты работы были представлены автором в пленарных докладах на международных конференциях "Мальцевские чтения" (2005, 2006 и 2008 гг., Новосибирск), а также в секционных докладах международных конференций "Logic Colloquium" (2004, Турин; 2006, Наймеген) и "Computability in Europe" (2007, Сиена; 2008, Афины).

По теме диссертационной работы автором был сделан ряд докладов на общеинститутском семинаре Института математики им. С. Л. Соболева СО РАН, а также на научных семинарах Новосибирского государственного университета, Московского государственного университета,

Казанского государственного университета и Казахского национального университета им. Аль-Фараби в г. Алма-Ата (Казахстан). Результаты, доложенные на общеиститутском семинанаре института математики им. С. Л. Соболева СО РАН, трижды признавались одними из лучших научных достижений института (2001, 2006 и 2008 гг.) Наработанная в ходе получения результатов диссертации техника использовалась при чтении основного спецкурса "Дополнительные главы теории вычислимости" на кафедре ДМИ Новосибирского государственного университета.

Публикации.

Основные результаты диссертации опубликованы в журналах [34, 35] и [38 - 42], входящих в список ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук. Результаты, также представленные в диссертации, но не являющиеся основными, опубликованы в [36, 37].

Структура и объем работы.

Диссертация состоит из введения, четырёх глав, разбитых на параграфы, и списка литературы. Утверждения нумеруются тремя цифрами: первая обозначает номер главы, вторая — номер параграфа в главе, а третья — номер утверждения в параграфе. Список литературы содержит 42 наименования. Объём диссертации составляет 118 страниц (112 страниц без оглавления и вводной части).

Содержание работы

Первая глава диссертации носит вспомогательный характер. В ней вводятся все определения и обозначения, необходимые для изложения результатов основной части. Глава разбита на шесть тематических параграфов. В первом содержатся общие сведения по теории вычислимости, во втором — сведения из общей теории решёток. В третьем вводятся различные тины алгоритмических представлений дистрибутивных верхних полурешёток, исследованию которых посвящена вторая глава диссертации. В четвёртом присутствует всё необходимое, касающееся m-стспеней, в пятом — сведения из теории нумераций. Наконец, в шестом параграфе вводятся такие элементы алгоритмических конструкций, как спектры, каркасы и башни, присутствующие в доказательствах ряда теорем из третьей главы.

Вторая глава посвящена изучению свойств различных алгоритмических представлений ограниченных дистрибутивных полурешёток, которые вводятся в третьем параграфе предыдущей главы. Результаты этой главы существенно используются в последующих главах.

Глава разбита на пять параграфов. Первый параграф содержит один из основных результатов диссертации, в нем решается остававшийся несколько десятилетий открытым вопрос о характеризации лахланов-ских представлений верхних полурешёток. Этот результат сформулирован в диссертации как следствие из доказанной ранее теоремы 2.1.1

Следствие 2.1.1. Если ограниченная (то есть имеющая наибольший и наименьший элементы) дистрибутивная полурешётка имеет представление, то она имеет п-лахлановское представление, причём первое из этих представлений эффективно сводится ко второму.

Отсюда, в частности, следует, что лахлановские полурешётки (то есть полурешётки, введённые в работе [9] и согласно этой же работе изоморфные полурешёткам вычислимо перечислимых тп-стеленей, есть, в точности, ограниченные дистрибутивные полурешётки, обладающие £з-представлением.

Следующий, второй параграф второй главы, очень короток. Его основной результат носит более технический характер, однако оказывается полезным при исследовании т-степеней и связанных с ними арифметических нумераций. В диссертации он сформулирован как следствие из теоремы 2.2.1.

Следствие 2.2.1. Если полурешётка имеет предлахлановское представление, в котором, тернарное отношение, задающее предпорядки на последовательности конечных дистрибутивных предрешёток, принадлежит. классу П®+2 арифметической иерархии, то она имеет п-лахлановское представление, к которому сводится исходное представление.

Отсюда можно, в частности, заключить, что класс полурешёток, с которыми работает Ю. Л. Ершов в статье [25], совпадает с классом лахлановских полурешёток.

Третий параграф главы посвящён исследованию конструктивных дистрибутивных решёток. В контексте диссертации он носит вспомогательный характер, хотя его основной результат представляет самостоятельную ценность для теории конструктивных моделей. Основной результат этого параграфа (являющийся одним из основных результатов диссертации) сформулирован в диссертации в виде следствия:

Следствие 2.3.2. Для. каждого из трёх перечисленных ниже случаев существует дистрибутивная решётка конструктивизируемая как частичный порядок, такая что

(1) £ копструктивизируема как нижняя полурешётка, но не кон-структивизируема как верхняя полурешётка;

(2) £ копструктивизируема как верхняя полурешётка, но не копструктивизируема как нижняя полурешётка;

(3) £ не копструктивизируема ни как нижняя полурешётка, ни ка.к верхняя полурешётка.

В четвёртом параграфе исследуются позитивные представления так называемых локально решёточных частичных порядков. Основной результат имеет ценность для теории конструктивных моделей и формулируется в следующей теореме.

Теорема 2.4.1. Всякий локально решёточный 0'-конструктивизиру-емый частичный порядок имеет позитивное представление.

Эта теорема также относится к основным результатам диссертации.

Пятый, заключительный параграф второй главы подводит своеобразный итог исследованиям, результаты которых изложены в двух предыдущих параграфах. Основным утверждением этого короткого параграфа является следующее следствие, имеющее непосредственное отношение к теме всей второй главы и хорошо вписывающееся в контекст диссертации.

Следствие 2.5.1. Для каждого натурального п существует ограниченная верхняя дистрибутивная решёт,ха, имеющая -представление как частичный порядок, но не имеющая Т^-предслпавления как верхняя полурешётка.

Из него, в частности, видно, что класс лахлановских полурешёток не совпадает с классом ограниченных дистрибутивных полурешёток. имеющих £°+3-представление как частичные порядки.

Третья глава диссертации посвящена изучению полурешёток, возникающих в арифметических т-степенях. Она содержит три параграфа, имеет наибольший объём и является наиболее сложным с технической точки зрения фрагментом работы.

Первый параграф третьей главы довольно короткий. В нём сформулированы две теоремы и следствие из них, дающее локальную характе-ризацию полурешётки арифметических т-степеней (один из основных

результатов диссертации, имеющий несколько интересных приложений в теории нумераций). Полная формулировка результата такова.

Следствие 3.1.1. Для не более чем счётной верхней полурешётки -С и произвольного натурального п следующие условия эквивалентны.

(1) £. явля-егпся ограниченной дистрибутивной полурешёткой, имеющей Т,°1+3-представление;

(2) Л изоморфна главному идеалу полурешётки т-степеней, порождённому к огиперимм.унны.м ^ -множ^еством;

(3) £ изоморфна главному идеалу полурешётки т-степеней, порождённому гипериммунным множеством;

(4) £. изоморфна главному идеалу полурешётки т-степеней, порождённому произвольным Д°4.2-множеством.

Результат напрямую следует из теорем 3.1.1 и 3.1.2. Теорема 3.1.1 довольно проста и доказывается тут же, в первом параграфе. Теорема 3.1.2, напротив, весьма сложна с технической точки зрения. Она требует отдельного доказательства для случая п = 0 и случая п > 0. Доказательству случая п > 0 целиком посвящён второй параграф третьей главы диссертации, занимающий 10 страниц. Случай п = 0 следует из результатов третьего параграфа (исторически он был доказан на два года ранее, чем результаты третьего параграфа, однако, поскольку он может быть получен в качестве простого следствия из более поздних работ, ранние работы в тексте диссертации не отражены; см. [38] и [41]).

Третий параграф третий главы занимает 25 страниц и содержит доказательство наиболее сложного с технической точки зрения основного результата диссертации. Этот результат сформулирован в виде следующего утверждения.

Следствие 3.3.1. Следующие верхние полуреыётки изоморфны:

(1) полурешётка всех гиперпростых т-степеней;

(2) полурешётка всех простых тп-степеней;

(3) полурешётка всех вычислимо перечислимых т-степеней с удалённым. наибольшим элементам;

(4) полурешётка Роджерса Е^- вычислимых нумераций конечного семейства, состоящего из попарно не сравнимых по включению множеств.

Другими словами, тип изоморфизма всех этих полурешёток совпадает с типом изоморфизма введённой и изученной в работе Денисова [20] универсальной лахлановской полурешетки с удалённым наибольшим

элементом. Если в четвертом пункте взять полурешётку Роджерса двухэлементного семейства, то, как несложно вывести, будем иметь полурешётку всех т-степеней, составленных из Д^-множеств (следствие 3.3.2 в тексте диссертации). Тот факт, что такая полурешётка изоморфна полурешётке всех вычислимо перечислимых не креативных т-степеней, был анонсирован Денисовым в 1978 году в уже упомянутой работе [20], однако доказательство так и не было опубликовано.

В четвёртой, последней, главе диссертации содержатся результаты из теории нумераций. Они касаются строения полурешёток Роджерса Х£+1-вычислимых нумераций для различных натуральных п, главным образом для п > 0. Случай п = 0 является классическим для теории нумераций; ему, начиная с конца 60-ых годов прошлого века, посвящено множество работ самых различных авторов. Случай п > 0 сравнительно новый; он активно изучается лишь в последнее десятилетие.

Глава разбита на два параграфа. В первом параграфе представлены результаты, касающиеся локального строения (то есть типов изоморфизма главных идеалов) полурешёток Роджерса. Даётся полная локальная характеризация типов изоморфизма иолурешёток Роджерса арифметических нумераций конечных семейств. Для бесконечных семейств доказывается некое довольно сильное достаточное условие вло-жимости ограниченной верхней полурешётки в полурешётку Роджерса в качестве идеала. На основании всего этого доказывается теорема о различии типов изоморфизма нетривиальных полурешёток Роджерса разных уровней арифметической иерархии в случае, когда разрыв между уровнями составляет 2 или более. Кратко эти результаты могут быть сформулированы следующим рядом теорем (формулировки которых входят в число основных результатов диссертации).

Теорема 4.1.1. Пусть полурешётка Ж°+2(3") не тривиальна (то есть семейство 3* С £®+2 не одноэлементно и имеет хотя бы одну вычислимую нумерацию) и Л — произвольная ограниченная дистрибутивная полурешётка, имеющая ТРп+-упреставление, Тогда в полурешётке Роджерса суш,ествует идеал, изоморфный:

(1) если 1 конечно;

(2) £ без наименьшего элемента, если 7 бесконечно.

Теорема 4.1.2. Пусть 5" конечное непустое семейство £„+2 множеств. Тогда имеет место один, из следующих трёх случаев:

(1) семейство 3* одноэлементно и полурешётка ^^(Я) тривиальна (т.е. одноэлементна);

(2) 3" не одноэлементно, состоит из попарно несравнимых по включению множеств и главные идеалы в — это в точности ограниченные дистрибутивные полурешётки, имеющие

+3 - представление;

(3) У содержит пару различных вложенных друг в друга множеств и главные идеалы в Ж(Г)1+2(У) — это в точности ограниченные дистрибутивные полурешётки, имеющие Т^+А-представление.

Теорема 4.1.3. Пусть п, т <Е N таковы, что п + 2 ^ т. Если для некоторых семейств 3", 9 полурешётки и локально

изоморфны, то они тривиальны.

Последнее утверждение усиливает ряд результатов, доказанных ранее Бадаевым, Гончаровым и Сорби.

Во втором параграфе четвёртой главы исследуются вопросы, связанные с минимальными и строго минимальными накрытиями в полурешётках Роджерса арифметических нумераций. Этих вопросов два: вопрос о существовании минимальных накрытий и вопрос о предельности наибольшего элемента полурешётки, то есть вопрос о том, может ли наибольший элемент (если он существует) являться минимальным накрытием другого элемента.

Наиболее правдоподобная в настоящий момент гипотеза гласи г, что в нетривиальных полурешётках Роджерса арифметических нумераций строго минимальные накрытия есть у любого не наибольшего элемента. Этот факт, к сожалению, так и не был доказан и до сих пор остаётся гипотезой. Однако автором был получен ряд довольно сильных достаточных условий того, что у элемента полурешётки Роджерса имеется минимальное, а в некоторых случаях и строго минимальное накрытие. Условия могут быть представлены тремя утверждениями (составляющими в совокупности один из основных результатов диссертации).

Предложение 4.2.1. Если в полурешётке элемент представ-

лен некоторой нумерацией, для которой существует -вычисли-

мая функция без неподвижной точки, то этот элемент имеет минимальное накрытие.

Следствие 4.2.3. Если семейство 3* содержит ■наименьший по включению элемент, то в полурешётке 31®+2(3") каждый не наибольший элемент имеет строго лтнимальное накрытие.

Следствие 4.2.4. Если семейство 3" конечно, то в полурешётке Kasicdbiü не наибольший элемент имеет минимальное накрытие.

Перечисленные выше результаты доказаны в статье [34), написанной автором совместно с С. А. Бадаевым.

Кроме перечисленных выше во втором параграфе представлены результаты, касающиеся предельности наибольшего элемента в полурешётках Роджерса арифметических нумераций. Из классической теории нумераций хорошо известна теорема Хуторецкого, следствием которой является утверждение о предельности наибольшего элемента в полурешётках вида (если он там существует). Для полурешёток вида Э1°+2(3") аналогичный вопрос, к сожалению, остаётся открытым. Автор не решает его полностью, однако доказывает, что в очень многих случаях наибольший элемент, если он существует, действительно пределен. Точная формулировка доказанного автором содержится в следующей теореме.

Теорема 4.2.3. Если в полурешётке существует наибольший

элемент, vio он является предельным в случае, когда выполняется хотя бы одно из следующих четырёх условий:

(1) семейство 3" содержит наименьший но включению элемент;

(2) семейство 3* конечно;

(3) семейство 3" содержит, конечное лтожество;

(4) семейство 3* обладает вычислимой нумерацией.

Теорема показывает, что контрпример с предельным наибольшим элементом, если он существует, должен выглядеть довольно замысловато; в частности, не должно выполняться ни одно из четырёх перечисленных в теореме условий. В настоящее время такой контрпример неизвестен.

В заключение отметим, что первый пункт этой теоремы является следствием георемы 4.2.2. В теореме 4.2.2, в свою очередь, содержится одно любопытное утверждение о минимальных элементах полурешётки Роджерса, имеющее самостоятельную ценность.

Теорема 4.2.2. Если семейство 3" с содержит наименьший по

включению элемент, то в полурешётке Роджерса Э?°+2(3*) для каждого не наибольшего элемента найдётся несравнимый с ним минимальный элемент..

Автор выражает глубокую признательность: Сергею Савостьяновичу Гончарову за всестороннюю помощь и поддержку, а также за постановку задач, инициировавших представленные в диссертации исследования; Юрию Леонидовичу Ершову за ряд ценных идей, которые помогли ему в доказательстве полученных результатов; Серикжану Агыбаевичу Бадаеву и Андреа Сорби, помогавшим автору в создании плодотворной рабочей обстановки и проявлявшим интерес к его исследованиям.

Список ЛИТЕРАТУРЫ

[1] Badaev S. A., Goncharov S. S., Sorhi A. Completeness and Universality of Arithmetical Numberings. // in: Compatibility arid Models. 2003. Kluwer Academic/Plenum Publishers, P. 11 - 44.

[2] Badaev S. A., Goncharov S S., Sorhi A. Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings. // in: Cornputability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 79 - 91.

[3] Badaev S. A., Goncharov S. S. Theory of Numbering: open problems. // Contemporary Mathematics (AMS). 2000. vol. 257, pp. 23 - 38.

[4] Badaev S. A., Goncharov S. S. Cornputability and Numberings. // New Computational Paradigms. Changing Conceptions of what is Computable, ed.: S. Б. Cooper, B. Lowe, A. Sorbi. Springer Science f Business Media, LLC, New York. 2008. pp. 19 - 34.

¡5] Goncharov S. S., Harizanov V., Knight J., McCoy Ch., Millar R., Solomon R. Enumerations in computable structure theory. // Annals of Pure and Applied Logic. 2005. vol. 136, №. 3, pp. 219 - 246.

[6] Goncharov S. S., Chisholm J., Fokina E., Harizanov V., Knight J., Miller S. Intrinsic bounds on complexity and definability at limit levels. // Journal of Symbolic Logic. 2009. vol. 74, №. 3, pp. 1047 - 1060.

[7] Goncharov S. S. Computable Numberings of Hyperarithmetical Sets and Complexty of Countable Models. // Mathematical Theory and Computational Practice, 5th Conf. On Cornputability in Europe, CiE 2009, Heidelberg, Germany (July 19-24), Univer. Of Heidelberg. 2009. pp 13 - 14.

¡8) Lachlan A. H. Two theorems on many-one degrees of recursively enumerable sets / / Алгебра и Логика. 1972. T И, №. 2, С. 216 - 229.

[9] Lachlan А. Н. Recursively enumerable many-one degrees // Алгебра и логика. 1972. Т. 11, № 3. С. 326 - 358.

[10] Odifreddi P. Classical recursion theory, volume II. Elsivier, Amsterdam, 1999.

[11] Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и Логика. 2001. Т. 40, №. 5, С. 507-522.

[12] Бадаев С. А., Гончаров С. С., Сорби А- Об элементарных теориях полурешёток Роджерса. // Алгебра и логика. 2005. Т. 44, № 3. С. 261 - 268.

[13] Бадаев С. А., Гончаров С. С., Сорби А. Типы изоморфизма полурешёток Роджерса семейств из различных уровней арифметической иерархии // Алгебра и логика. 2006. Т. 45, № 6. С. G37 - 654.

[14] Въюгин В. В. Сегменты рекурсивно перечислимых m-степеней. // Алгебра и Логика. 1974. Т. 13, №. 6, С. 635 - 654.

[15] Вьюг им В. В. О верхних полурешетках нумераций. // Докл. АН СССР. 1974. Т. 217, № 4, С. 749 - 751.

Гретцер Г. Общая теория решёток. М.: Мир, 1982.

Гончаров С. С. Счётные булевы алгебры и разрешимость. Научная книга, Новосибирск, 1996.

Гончаров С. С., Ссрбч А. Обобщенно вычислимые нумерации и нетривиальные полурешеткн Роджерса. /',/ Алгебра и Логика. 1997. Т. 36, № 6, 621 - 641. Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Научная книга, Новосибирск, 1999.

Денисов С. Д. Строение верхней полурешётки рекурсивно перечислимых, т-сте-пеней и смежные вопросы. 1 // Алгебра и логика. 1978. Т. 17, № б. С. 643 - 683. Дёгтев А. И. Рекурсивно перечнелимые множества и сводимости табличного типа. Наука, Физматлиг, Москва, 1998.

Ершов ¡0. Л.. Гипергиперпростые т-степени. // Алгебра и Логика. 1У69. Т. 8, № 5, С. 523 - 552.

Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.

Ершов Ю. Л. Необходимые условия изоморфизма полурешеток Роджерса конечных частично упорядоченных множеств. /'/ Алгебра и Логика. 2003. Т. 42, № 4, С. 413 - 421.

Ершов Ю. Л.. Полурешётки Роджерса конечных частично упорядоченных множеств. Ц Алгебра и логика. 2006. Т. 45, № 1. С. 44 - 84.

Ершов Ю. Л., Лавров И. А. Верхняя полурешетка Ь(&). Алгебра и Логика. // 1973. Т. 12, № 2, С. 167 - 189.

Ершов Ю. Л. Верхняя полурешетка нумераций конечного множества. // Алгебра и Логика. 1975. Т. 14, № 3, С. 258 - 284.

Мальцев А. И., Конструктивные алгебры, 1. // Успехи Мат. Наук. 1961. Т. 16, № 3, С. 3 - 60.

Па.лютин А. Дополнение: к статье Ю. Л. Вршова "Верхняя полурешётка нумераций конечного множества". // Алгебра и логика. 1975. Т. 14, № 3. С. 284 — 287.

Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

Соар Р. И. Вычислимо перечислимые множества и степени. "Казанское математическое общество", Казань, 2ООО.

Успенский В. Л., Лекции о вычислимых функциях. Физматгиз, М., 1960. Хуторецкий А. Б. О мощности верхней полурешетки вычислимых нумераций. // Алгебра и Логика. 1971. Т. 10, № 5, С. 561 - 569.

Работы автора по теме диссертации

[34J Бадаев С. А., Подзоров С. Ю. Минимальные накрытия в полурешетках Роджерса £°-вычислимых нумераций. // Сиб. Мат. Ж. 2002. Т. 43, № 4, С. 769 - 778.

[35] Подзоров С. Ю. Начальные сегменты в полурешетках Роджерса ^-вычислимых нумераций. //' Алгебра и Логика. 2003. Т. 42, № 2, С. 211 - 225.

[36] Badaev S. A., Goncharov S. S., Podzorov S. Yu., Sorbi A. Algebraic properties of Rogers semilattices of arithmetical riumberings. // in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 45 - 77.

[37] Подзоров С. Ю. О предельности наибольшего элемента полурешетки Роджерса. // Матем. Труды. 2004. Т. 7, № 2, С. 98 - 108.

[38] Podzorov S. Yu. On the local structure of Rogers semilattices of S^-computable numberings. // Algebra and Logic. 2005. vol. 44, № 2, pp. 82 - 94. (пер. Подзоров С. Ю. О локальном строении полурешеток Роджерса S^-вычислимых нумераций. // Алгебра и Логика. 2005. Т. 44, № 2, С. 148 - 172.)

[39] Подзоров С. Ю. Об определении лахлановской полурешетки. // Сиб. Мат. Ж. 2006. Т. 47, № 2, С. 383 - 393.

[40] Podzorov S. Yu. Numbered distributive semilattices..// Siberian Adv. in Math. 2007. vol. 17, № 3, pp. 171 - 185. (пер. Подзоров С. Ю. Нумерованные дистрибутивные полурешётки. // Матем. Труды. 2006. Т. 9, if' 2, С. 109 - 132.)

[41] Podzorov, S. Yu. The universal Lachlan semilattice without the greatest element. 11 Algebra and bogie. 2007. vol. 46, № 3, pp. 163 - 187. (пер. Подзоров С. Ю. Универсальная лахлановская полурешетка без наибольшего элемента. // Алгебра и Логика. 2007. Т. 46, Л"' 3, С. 299 - 345.)

[42] Подзоров С. Ю. Арифметические m-стеиени. // Сиб. Мат. Ж. 2008. Т. 49, № 6, С. 1391 - 1410.

Подзоров Сергей Юрьевич

Верхние полурешётки арифметических нумераций и арифметических пг-степеней

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

Подписано в печать 25.03.10 Формат 60x84 1/16 Усл. печ. л. 1,2 Уч.-изд. л. 1,2 Тираж 130 экз. Заказ № 13

Отпечатано в ООО "Омега Принт" 630090, Новосибирск, пр. Лаврентьева, 6

1 Определения и обозначения

1.1 Общие понятия теории вычислимости.

1.2 Дистрибутивные полурешётки и предполурешётки

1.3 Представления дистрибутивных полурешеток

1.4 ?77-сводимость и т-степени.

1.5 Нумерации.

1.6 Каркасы и башни.

2 Представления дистрибутивных полурешёток

2.1 Классы Г22,п+з п

2.2 Классы А3]„ и П2,„+з

2.3 Конструктивные дистрибутивные решётки.

2.4 Позитивные частичные порядки

2.5 Классы Г23)Г1, П2,п и заключительные замечания

3 Полурешётки т-степеней

3.1 Характеризация главных идеалов полурешётки арифметических т-степеней.

3.2 Доказательство теоремы 3.1.2 для случая п >

3.3 Универсальные полурешётки.

4 Полурешётки арифметических нумераций

4.1 Главные идеалы полурешёток Роджерса.

4.2 Накрытая в полурешётках Роджерса.

Диссертация содержит ряд результатов, касающихся таких объектов теории вычислимости, как т-степени и полурешётки нумераций. Эти два понятия тесно переплетаются между собой. С одной стороны, 777-сгепс-ни являются, по с.ути, частным случаем нумераций (нумерации двухэлементного множества). С другой стороны, значительная часть изложенных в этой диссертации результатов показывает, что методы, используемые при изучении 777-стспенсй, могут с успехом применяться для изучения строения полурешёток арифметических нумераций. Более того, ряд теорем из четвёртой главы дают возможность установить изоморфизм между полурешётками 771-степеней и идеалами полурешёток нумераций, что позволяет сделать утверждение о большой степени схожести локального строения этих двух типов объектов.

Много-одно-своднмость и /»-степени являются традиционными объектами теории вычислимости. Впервые эти понятия были введены Постом в середине 10-ых годов XX столетия и с тех пор привлекали внимание многих исследователей. В той или иной степени эти понятия освещаются во всех солидных монографиях по теории вычислимости. Результаты, касающиеся т-степеней, появлялись в сотнях публикаций, выходивших на протяжении десятилетий. Среди них можно выделить следующие четыре основных достижения:

1. В 1972 году Лахлан описал типы изоморфизма главных идеалов полурешётки вычислимо перечислимых т-степеней;

2. В 1975 Ершов и Палютин дали описание полурешётки всех т-степеней с точностью до изоморфизма в терминах с-универсальных полурешёток;

3. В 1978 Денисов дал характеризацию типа изоморфизма полурешётки всех вычислимо перечислимых т-степеней;

4. В 1980 Нероуд и Шор показали, что теория первого порядка ио-лурешётки т-степеней вычислимо изоморфна арифметике второго порядка.

Работы, содержащие результаты из первого и третьего пунктов этого списка, дали основной толчок к части исследований автора, представленных во второй и третьей главах этой диссертации. 3

Характеризации типов изоморфизма, полученные Лахланом и Денисовым, существенно опирались на понятие лахлановекой полурешётки. Это понятие имеет довольно сложное определение, состоящее из многих пунктов. В связи с этим с конца 1970-х годов внимание исследователей привлекал вопрос о том, возможно ли описать класс лахлановских полурешёток более коротким и ''естественным" способом. С одной стороны. легко заметить, что каждая лахлановская полурешётка представляет из себя ограниченную дистрибутивную полурешётку, имеющую представление. С другой стороны, было сразу замечено, что для таких естественных классов ограниченных дистрибутивных полурешёток с Ео-представлениями, как решётки и конструктивные полурешётки, справедливо обратное и все полурешётки из этих классов являются лахла-новскими. В связи с этими наблюдениями возникла естественная гипотеза о том, что лахлановекмн полурешётки — это, в точности, ограниченные дистрибутивные полурешётки с ^-представлениями. Вопрос о том, верна ли гипотеза, долгое время оставался открытым.

Во второй главе настоящей диссертации автор доказывает эту гипотезу и даёт положительный ответ на этот вопрос. Более того, устанавливается, что каждое Ез-представление полурешётки сводится к некоторому лахлановскому представлению и, значит, в конструкциях, использующих технику Лахлана и Денисова, можно оперировать с Ез-представ-лениями полурешёток вместо лахлановских представлений. Результат обобщается на нолурешётки с любыми арифметическими представлениями; кроме того, исследуется ряд представлений, близких к двум указанным.

Другой естественный вопрос, вставший перед автором после прочтения работы Лахлана, заключался в возможности обобщения результата Лахлана на произвольные уровни арифметической иерархии. Раз главными идеалами ш-степеней в классе Ермпожеств оказались в точности ограниченные дистрибутивные полурешётки с Ез-представлениями, то логично было предположить, что главными идеалами т-степеней в классе Е^+1-множеств являются в точности ограниченные дистрибутивные полурешётки, имеющие ^-представление. В свяли с полученными чуть ранее результатами о главных идеалах полурешёток Роджерса арифметических нумерации этот вопрос приобрёл важное прикладное значение. Положительный ответ на него даётся в третьей главе.

Соответствующая теорема третьей главы доказана в усиленной форме: для каждой полурешётки с Е°+3-представлением строится главный идеал, порождающее множество которого обладает дополнительным свойством гипериммунности. Усиление требуется для дальнейших приложений в теории нумераций, однако сама возможность такого усиления напела автора на ряд мыслей, приведших к результатам третьего параграфа третьей главы. Легко заметить, что простые и гиперпростые ш-степени (то есть т-стспени, содержащие простое (гиперпростое) либо вычислимое множество) образуют идеалы в полурешётке вычислимо перечислимых т-степеней В связи с возможностью усиления оказывается, что эти идеалы локально изоморфны полурешётке вычислимо перечислимых т-степеней без наибольшего элемента п нолуретётке О'-вычпс-лимых т-степеней. Буду г ли упомянутые полурешётки просто изоморфны? Последний параграф третьей главы (технически наиболее сложный и занимающий наибольший объём по сравнению с другими параграфами) даёт положительный ответ на этот вопрос.

Что касается нумераций, то интересующие нас + (-вычислимые нумерации подразделяются на "классический" случай п = 0и "неклассический" случай п > 0. "Классический" случай изучался начиная с 60-ых годов XX столетия; по нему вышли десятки статей и монография Ю. Л. Ершова. "Неклаееттческий" случай привлёк внимание исследователей в середине 90-ых годов XX столетия.

Первые исследования различных авторов, изучавших полурешётки Роджерса числимых нумераций в некласснческом случае, касались их локального строения. Довольно быстро было доказано, что каждая нетривиальная полурешётка из этого класса имеет бесконечно много минимальных элементов, однако после этого дело застопорилось. Долгое время не удавалось доказать даже существование безатомных элементов в общем случае.

Автор диссертации в одной из своих первых статей по теории нумераций решил этот вопрос. Попутно им было доказано, что в любую нетривиальную "неклассическую" полурешётку в качестве идеала можно вложить главный идеал т-степеней, порождённый иммунным Д°+2~множеством- После этого возник вполне закономерный интерес к ///-степеням и на протяжении нескольких лет активно изучались вопросы их локального строения. Однако после того, как эти работы были завершены, они тут же нашли непосредственное применение I; теории нумераций. Следствием основных теорем, доказанных во второй, третьей и нервом параграфе четвертой главы, стал следующий результат: каждая нетривиальная полурешётка 72.^+2[У7) содержит идеал, изоморфный произвольной ограниченной дистрибутивной полурешётке с ^-представлением. Следствием этого стали, в свою очередь, полученная автором локальныя характеризация полурешёток +2 для конечных семейств О- и утверждение о том, что все нетривиальные полурешётки и при т > п + 2 не изоморфны (что значительно усиливало результаты, полученные ранее в нескольких работах других авторов).

Последний параграф четвёртой главы посвящен вопросам о минимальных накрытиях и, в частности, вопросу о предельности наибольшего элемента, в полуротпётках которые также активно изучались. Были достигнуты значительные успехи, получен ряд довольно сильных достаточных условий. Полностью вопросы о минимальных накрытиях и о предельности были решены для полурешёток С-^); У которых конечно или имеет наименьший по включению элемент.

Автор выражает глубокую признательность: Сергею Савостьяновичу Гончарову за всестороннюю помощь и поддержку, а также за постановку задач, инициировавших представленные здесь исследования; Юрию Леонидовичу Ершову за ряд ценных идей, которые помогли ему в доказательстве полученных результатов; Серикжану Лгыбаевичу Бадаеву и Андреа Сорби, помогавшим автору в создании плодотворной рабочей обстановки и проявлявшим интерес к обсуждаемым здесь проблемам. Отдельную благодарность автор выражает Виталию Геннадьевичу Ше-лиховскому за всестороннюю помощь и интерес, проявленный к работе. 6

1. Badaev S. A., Goncharov S. S., Sorbi A. Completeness and Universality of Arithmetical Numberings. / / in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 11 — 44.

2. Badaev S. A., Goncharov S. S., Sorbi A. Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings. // in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 79 91.

3. Badaev S. A., Goncharov S. S. Theory of Numbering: open problems. // Contemporary Mathematics (AMS). 2000. vol. 257, pp. 23 38.

4. Badaev S. A., Goncharov S. S. Computability and Numberings. // New Computational Paradigms, Changing Conceptions of what is Computable, ed.: S. B. Cooper, B. Lowe, A. Sorbi. Springer Science + Business Media, LLC, New York. 2008. pp. 19 34.

5. Goncharov S. S., Harizanov V., Knight J., McCoy Ch., Millar R., Solomon R. Enumerations in computable structure theory. // Annals of Pure and Applied Logic. 2005. vol. 136, №. 3, pp. 219 246.

6. Goncharov S. S. Chisholm J., Fokina E., Harizanov V., Knight J., Miller S. Intrinsic bounds on complexity and definability at limit levels. // Journal of Symbolic Logic. 2009. vol. 74, №. 3, pp. 1047 1060.

7. Lachlan Л H. Two theorems on many-one degrees of recursively enumerable sets // Алгебра и Логика. 1972. Т. 11, j\°. 2, С. 216 229.

8. Lachlan А. Н. Recursively enumerable many-one degrees // Алгебра и логика. 1972. Т. 11, № 3. С. 326 358.

9. Odifreddi P. Classical recursion theory, volume II. Elsivier, Amsterdam, 1999.109

10. Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и Логика. 2001. Т. 40, №. 5, С. 507-522.

11. Бадаев С. А., Гончаров С. С., Сорби Л. Об элементарных теориях полурешёток Роджерса. // Алгебра и логика. 2005. Т. 44, № 3. С. 261 268.

12. Бадаев С. А., Гончаров С. С., Сорби А. Типы изоморфизма полурешёток Роджерса семейств из различных уровней арифметической иерархии // Алгебра и логика. 2006. Т. 45, № 6. С. 637 654.

13. Въюгип В. В. Сегменты рекурсивно перечислимых ш-степеней. // Алгебра и Логика. 1974. Т. 13, №. 6, С. 635 654.

14. Вьюгин В. В. О верхних полурешетках нумераций. // Докл. АН СССР. 1974. Т. 217, №. 4, С. 749 751.

15. Грегпцер Г. Общая теория решёток. М.: Мир, 1982.

16. Гончаров С. С. Счётные булевы алгебры и разрешимость. Научная книга, Новосибирск, 1996.

17. Гончаров С. С., Сорби А. Обобщенно вычислимые нумерации и нетривиальные полурешетки Роджерса. // Алгебра и Логика. 1997. Т. 36, №. 6, 621 641.

18. Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Научная книга, Новосибирск, 1999.

19. Денисов С. Д. Строение верхней полурешётки рекурсивно перечне-лимых т-степеней и смежные вопросы. 1 // Алгебра и логика. 1978. Т. 17, № 6. С. 643 683.

20. Дёгтев А. II. Рекурсивно перечислимые множества и сводимости табличного типа. Наука, Физматлит, Москва, 1998.

21. Ершов Ю. Л. Гипергиперпростые т-степени. // Алгебра и Логика. 1969. Т. 8, №. 5, С. 523 552.

22. Ершов Ю. Л. Теория нумераций. М.: Паука, 1977.

23. Ершов Ю. Л. Необходимые условия изоморфизма полурешеток Роджерса конечных частично упорядоченных множеств. // Алгебра и Логика. 2003. Т. 42, №. 4, С. 413 421.110

24. Ершов Ю. Л. Полурешётки Роджерса конечных частично упорядоченных множеств. // Алгебра и логика. 2006. Т. 45, № 1. С. 44 — 84.

25. Ершов Ю. Л., Лавров И. А. Верхняя полурешетка Ь(&). Алгебра и Логика. // 1973. Т. 12, №. 2, С. 167 189.

26. Ершов 10. Л. Верхняя полурешетка нумераций конечного множества. // Алгебра и Логика. 1975. Т. 14, №. 3, С. 258 284.

27. Мальцев А. И., Конструктивные алгебры, 1. // Успехи Мат. Наук. 1961. Т. 16, №. 3, С. 3 60.

28. Палютин Е. А. Дополнение к статье Ю. Л. Ершова "Верхняя полурешётка нумераций конечного множества". // Алгебра и логика. 1975. Т. 14, № 3. С. 284 287.

29. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

30. Соар Р. И. Вычислимо перечислимые множества и степени. "Казанское математическое общество", Казань, 2000.

31. Успенский В. Л., Лекции о вычислимых функциях. Физматгиз, М., 1960.

32. Хуторецкий А. Б. О мощности верхней полурешетки вычислимых нумераций. // Алгебра и Логика. 1971. Т. 10, №. 5, С. 561 569.Работы автора по теме диссертации

33. Бадаев С. А., Подзоров С. Ю. Минимальные накрытия в полурешетках Роджерса -вычислимых нумераций. // Сиб. Мат. Ж. 2002. Т. 43, №. 4, С. 769 778.

34. Подзоров С. Ю. Начальные сегменты в полурешетках Роджерса вычислимых нумераций. // Алгебра и Логика. 2003. Т. 42, №. 2, С. 211 225.

35. Badacv S. A., Goncharov S. S., Podzorov S. Yu., Sorbi A. Algebraic properties of Rogers semilattices of arithmetical numberings. // in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers,P. 45 77.1.l

36. Подзоров С. Ю. О предельности наибольшего элемента полурешетки Роджерса. // Матем. Труды. 2004. Т. 7, №. 2, С. 98 108.

37. Подзоров С. Ю. Об определении лахлановской полурешетки. // Сиб. Мат. Ж. 2006. Т. 47, №. 2, С. 383 393.

38. Podzorov S. Yu. Numbered distributive semilattices. // Siberian Adv. in Math. 2007. vol. 17, №. 3, pp. 171 185. (пер. Подзоров С. Ю. Нумерованные дистрибутивные полурешётки. // Матем. Труды. 2006. Т. 9, №. 2, С. 109 - 132.)

39. Подзоров С. Ю. Арифметические m-степени. // Сиб. Мат. Ж. 2008. Т. 19, №. 6, С. 1391 1410.