Счетные линейные порядки и их алгоритмическая сложность тема автореферата и диссертации по математике, 01.01.06 ВАК РФ



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

Фролов Андрей Николаевич

Счетные линейные порядки и их алгоритмическая сложность

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

00554о7ЬТ

г г пт 2014

Казань-2014 ^--^ ^ ^

005548761

Работа выполнена в отделе алгебры и математической логики ФГАОУВПО

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

Арсланов Марат Мирзаевич, доктор физико-математических наук, профессор, член-корреспондент АН республики Татарстан.

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

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

Перетятькин Михаил Георгиевич доктор физико-математических наук, профессор, Институт математики и математического моделирования Министерство образования и науки республики Казахстан, республиканское государственное предприятие, главный научный сотрудник,

Хисамиев Назиф Гарифуллинович, доктор физико-математических наук, профессор, Восточно-Казахстанский государственный технический университет им. Д. Серикбаева, заведующий кафедрой.

Ведущая организация: Омский государственный университет Защита состоится «6» июня 2014 г. в ^3~~~часов на заседании диссертационного совета 212.081.24 при Казанском (Приволжском) федеральном университете, расположенном по адресу: 420008, г. Казань, ул. Кремлевская,

С диссертацией можно ознакомиться в библиотеке Казанского (Приволж-

Казанского (Приволжского) федерального университета".

ского) федерального университета.

Автореферат разослан «. „ Яуррия 2014 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, дог

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

Актуальность работы. Данная работа посвящена изучению алгоритмических свойств счетных линейных порядков на основе построения эффективных представлений этих структур на множестве натуральных чисел. Это направление исследований находится на стыке теории вычислимости и теории слстных линейных порядков. Счетные линейные порядки твердо заняли свое место в теории моделей — каждая счетная булева алгебра порождается некоторым счетным линейным порядком, а в теории групп особое место занимает направление исследований упорядоченных групп и прочее.

Основы теории вычислимых алгебраических структур и их моделей были заложены в работах 50-х годов прошлого века П.С.Новикова [5], О. Раби-на [411, А. Фролиха и Дж. Шефердсона [23], Р. Воота [50], А.И. Мальцева [3] и [4] и с тех пор активно развивается. В качестве наиболее важных и современных источников можно указать книги С.С.Гончарова и Ю.Л.Ершова [2] и Дж. Найт и К.Эша [10], а также большую обзорную работу 2007 года С.С. Гончарова [241.

Исследования в области вычислимых линейных порядков были начаты почти одновременно с зарождением теории вычислимых структур с работы 1956 года X. Райса [43], были продолжены в работах Д. Янга [53], Л. Фейнера [19] и [20], Р.Соара [47], М. Перетятькина [6], А. Пинуса [7], С. Фслнера [21] и с тех пор прочно заняли свое место в теории вычислимых структур. Так, нарубеже веков выходит в свет обзорная работа Р. Доуни и Дж. Реммела [18] охватывающая все актуальные направления исследований и важные открытые вопросы в теории вычислимых структур, где теории вычислимых линейных посвящен отдельный раздел. В этом направлении наиболее важными и современными источниками являются книга Дж. Розенштейна [45] и обзорные работы Р. Доуни [13] и [12].

' 4 3

Все исследования в области вычислимых линейных порядков (и вычислимых алгебраических структур, в общем) можно условно разделить на три основных направления:

I. Исследование свойств вычислимых линейных порядков;

II. Описание достаточных (и необходимых) условий вычислимой представимости линейных порядков;

III. Описание спектров линейных порядков (то есть описание класса степеней представлений).

В представленной диссертации получены результаты по всем этим трем направлениям. Опишем их более подробно.

I) Исааедование свойств вычислимых линейных порядков направлено на такие вопросы, как описание эффективной категоричности, разрешимости и n-разрешимости вычислимых линейных порядков, описание эффективных свойств отношений на них. Проще говоря, в этом направлении исследуются вычислимые линейные порядки на предмет дополнительных алгоритмических свойств.

С.С.Гончаровым и В.Д.Дзгоевым [1] и, независимо, Дж.Реммелом [42] было получено описание вычислимо категоричных вычислимых линейных порядков. А именно, ими было показано, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он содержит только лишь конечное число пар соседних элементов.

Ч. МакКой [33] получил описание относительно О'-вычнслимо категоричных линейных порядков. Он доказал, что вычислимый лилейный порядок является относительно О'-вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый из которых имеет тип п, w, и', £ или п - щ, где каждый интервал п ■ г) имеет наибольший и наименьший элементы.

Последнее время все более популярными становятся исследования степеней категоричности алгебраических структур. Отметим в этом направлении работы И. Калим.уллина, Р.Миллера и Е. Фокиной [22], Р.Миллера [35], Дж. Франклина, Б. Чимы и Р. Шора [И] и других. Например, И. Калимуллин, Р. Миллер и Е. Фокина [22] для произвольной 2-перечислимой степени (1 построили вычислимую алгебраическую структуру, степень категоричности которой есть <1.

М. Мозес [34] показал, что вычислимый линейный порядок является 1-раз-решимым тогда и только тогда, когда его отношение соседства вычислимо. Отметим здесь результат К.Лэнгфорда [32], который фактически означает, что дискретный линейный порядок является разрешимым тогда и только тогда, когда он является 1-разрешимым.

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

Для исследования свойств отношений на вычислимых структурах В. Ха-ризанова [26] взела понятие спектра отношения, как класс степеней отношений различных вычислимых представлений заданной структуры. Таким образом, спектром отношения соседства вычислимого линейного порядка Ь называется класс ИдБрь^исс) = | V ~ £ & degT(L') < О}.

В выше упомянутой работе Р. Доуни и Дж. Реммела [18], опубликованной на рубеже веков, описывающей основные направления исследований и содержащей важные открытые вопросы по теории вычислимых линейных порядков, исследованию спектра отношения соседства уделяется особое внимание. Фундаментальный вопрос здесь сформулирован как вопрос об описании спектров отношения соседства вычислимых линейных порядков.

Так как отношение соседства вычислимого линейного порядка Ь задается П1-формулой в сигнатуре линейного порядка, то ОдЗрь(Зисс) содержит только перечислимые степенн. то есть ОдЯр^Бисс) С Е".

Очевидно, что если линейный порядок Ь содержит только лишь конечное число пар соседних элементов, то ИдБр^Зисс) = {0}. Такой линейный порядок и спектр его отношения соседства назовем тривиальными. Д. Хирш-фельдт [28] показал, что спектр отношения соседства нетривиального вычислимого линейного порядка бесконечен, то есть если ОдБр^Бисс) ^ {0}, то ОдБр^Бисс) бесконечен. Р.Доуни и М.Мозес [17] построили вычислимый линейный порядок, спектр отношения соседства которого одноэлементный и равен {С}.

Существование вычислимых линейных порядков, имеющих конечные спектры отношения соседства, подтолкнуло ряд исследователей к постановке следующих проблем, которые были опубликованы в работе Р. Доуни и Дж. Рем-мела [18] в 2000 году.

Проблема Существует ли вычислимый линейный порядок, спектр отношения соседства которого одноэлементный или хотя бы конечный, но не равный {0} и {О'} ?

Проблема Всегда ли спектр отношения соседства нетривиального вычислимого линейного порядка содержит степень 0' ?

Нетрудно видеть, что вышеприведенные проблемы связаны со следующей проблемой, которая впервые была сформулирована в работе автора [61] (совместно с В. Харизановой и Дж. Чаб). А именно, положительное решение следующей проблемы влечет отрицательный ответ на первую из них и положительный ответ — на вторую.

Проблема Верно ли, что спектр отношения соседства вычислимого линейного порядка либо тривиальный, либо замкнут наверх в классе перечислимых степеней?

В диссертационной работе получено положительное решение последней проблемы, которая также имеет применение в описании свойств эффективной категоричности. А именно, из положительного решения этой проблемы следует, что степенями категоричности относительно О'-вычислимо категоричного линейного порядка могут быть только лишь 0 и О'.

II) В одной из самых ранних работ по исследованию вычислимых свойств линейных порядков Л.Фейнер [20] построил О'-вычислнмый линейный порядок, не имеющий вычислимого изоморфного представления. Этот результат естественным образом подталкивает к вопросу об исследовании достаточных условий вычиыимой представимости линейных порядков и, более общо, к описанию вычислимо представимых линейных порядков. Последний более общий вопрос был сформулирован как фундаментальный вопрос теории вычислимых линейных порядков в уже выше упомянутой работе 2000 года Р. Доуни и Дж. Реммела [18].

А в 1998 году Р. Доуни [13] сформулировал программу исследования и описания достаточных условий вычиыимой представимости линейных порядков. Эта программа является результатом целого ряда результатов. В теории вычислимости известны низкие множества, не являющиеся вычислимыми, в то же самое время низкие множества «близко расположены» к вычислимым множествам (см., например, книгу Р. Соара [8]). Естественно напрашивается предположение, что возможно некоторые низкие структуры имеют вычислимые представления. Действительно, Р. Доуни и К. Джокуш [14] дока-

7

зали, что каждая низкая булева алгебра является вычислимо представимой.

Дж. Найт (неопублпковано) поставила вопрос о вычислимой представимости низких линейных порядков. Однако, К. Джокуш и Р. Соар [30] дали отрицательный ответ на вопрос Дж. Найт, показав, что не каждый низкий линейный порядок имеет вычислимое представление. Все же Р. Доуни и М. Мозес [16] доказали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Как уже было сказано выше, в результате всех перечисленных исследований Р. Доуни [13[ сформулировал программу описания достаточных условий вычислимой представимости линейных порядков в виде проблемы описания порядковых свойств Р таких, что для любого низкого линейного порядка Ь из выполнимости Р{Ь) следует существование вычислимого представления.

С целью продолжения исследований в этом русле естественно обобщить выше приведенную проблему, заменив условие «низкости» на условие «п-низ-кости». Действительно, также, как и низкие множества, что было приведено выше, тышзкие множества «близко расположены» к вычислимым множествам. А также некоторые п-низкие структуры являются вычислимо пред-ставнмыми. Например, Дж. Тёрбер [49] доказал, что каждая 2-низкая булева алгебра имеет вычислимое представление, а Дж. Найт и М. Стоб [39] показали, что любая 3-гшзкая и даже 4-низкая булева алгебра является вычислимо представимой.

Другими словами, естественно расширить проблему Р. Доуни. А именно, уделить внимание проблеме описания порядковых свойств Рп таких, что для любого п-низкого линейного порядка Ь из выполнимости Рп(Ь) следует существование вычислимого представления.

Первые исследования этой расширенной проблемы Р. Доуни были проведены в работе автора диссертации [55], результаты которой представлены ниже. Из прочих результатов приведем работу 2011 года, в которой Э. Кэч и

8

А. Монталбан [31J опубликовали результат о том, что для любого натурального числа п каждый n-низкнй линейный порядок L, имеющий только лишь конечное число разбиений на сумму двух непустых сегментов L = Li 4- L2 таких, что L>2 не имеет наименьшего элемента, является вычислимо предста-вимым. Они же отметили, что рассмотренный порядковый тип не является тривиальным. А именно, они доказали, что существует О'-вычиелимый линейный порядок такого типа, не имеющий вычислимой копии.

Заметим, что выше описанный порядковый тип является разреженным. Это и некоторые другие наблюдения подтолкнули в той же работе Э. Кэча и А. Монталбана [31] поставить следующую проблему о 2-низких разреженных линейных порядках.

Проблема Верно ли, что каждый 2-низкий разреженный линейный порядок имеет вычислимое представление?

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

III) Описание спектров линейных порядков, как и произвольных структур, является сравнительно молодым направлением исследований, но естественно дополняет два выше перечисленных, и в последние годы становиться все более актнвно изучаемым. Поэтому описание спектров линейных порядков также, как и предыдущие направления исследований, не осталось без внимания в работе Р.Доуни и Дж. Реммела [18], как уже говорилось выше, опубликованной на рубеже веков и содержащая самые актуальные вопро-

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

Понятие спектра степеней произвольной алгебраической структуры (не обязательно линейного порядка) было введено Л. Рихтер [44]. Спектром алгебраической структуры А (и, в частности, линейного порядка) называется класс тьюринговых степеней представлений данной структуры, то есть Зрес(А) = {¿е&г(В) | В = А}.

Несмотря на уже достаточно большое количество исследований по описанию спектров алгебраических структур, полное их описание еще далеко от своего завершения. Отметим исследования, в том числе и связанные с линейными порядками, таких авторов, как В. Харизанова и Р. Миллер [27], А. Слинко, Д. Хиршфильтд, Б.Хусаинов и Р. Шор [29], И. Сосков [48].

Особо стоит отметить следующие работы. Дж.Найт [38] показала, что спектр большинства (а именно, не являющихся автоморфно тривиальными) алгебраических структур и, в частности, линейных порядков, замкнут наверх.

Т. Сламан [46] и С. Вейнер [52] независимо друг от друга построили счетную алгебраическую структуру А такую, что Брес.(А) = Б \ {0}, где Б — класс всех тьюринговых степеней. Другими словами, построена алгебраическая структура, спектр которой состоит в точности из всех ненулевых степеней.

С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон [25] построили для любого тг е ш алгебраическую структуру Ап, чей спектр содержит в точности всех степени, не являющиеся в-низкими, то есть, такую, что 5рес(Л>) = КопЬо\уп, где 1\топЬошп — класс всех степеней, не являющихся п-низкими.

Изучение же спектров линейных порядков оказалась более трудной за-

10

дачей. Напомним, Дж. Найт [38] показала, что спектр линейных порядков замкнут наверх (см. также Дж.Найт [37] или К. Джокуш и Р. Соар [30]). Л. Рихтер [44] доказала, что если спектр линейного порядка имеет наименьшую степень, то этой степенью может быть только степень О.

В 1998 г. Р. Доуни [13] поставил вопрос о существовании линейного порядка, спектр которого совпадает со спектром Сламана-Вейнера. А именно, он поставил следующую проблему.

Проблема Существует ли линейный порядок, спектр которого содержит в точности все ненулевые степени.

Р. Миллер [36] с целью лучшего понимания строения спектров предложил изучить Д^-спектры линейных порядков. А^-Спектром линейного порядка называется класс Брес^Ць) = БресЩ П Изучение таких ограниченных спектров алгебраических структур (не обязательно линейных порядков) также вызывает самостоятельный интерес у исследователей.

Р. Миллер [36] доказал, что существует такой линейный порядок Ь, что Зрес^{Ь) = Д° — {0}, то есть Д^-спектр этого порядка состоит в точности из всех ненулевых Д^-степеней. Позже было замечено, что построенный Р. Миллером линейный порядок имеет представления по крайней мере во всех гипериммунных степенях. Исследования этого порядка продолжаются и до сих пор.

Так как спектры линейных порядков замкнуты наверх, то естественно рассмотреть в качестве таких примеров известные замкнутые наверх классы степеней. В качестве таких классов, по аналогии с выше упомянутой работой С.Гончарова, В.Харизановой, Дж.Найт, К. МакКоя, Р. Миллера и Р. Соломона [25]. рассматриваются классы степеней, не являющихся п-низ-кими, (класс ]ЧопЬол¥„) и п-высоких степеней (класс

Среди методов, использованных при построении спектров и Д^-спектров линейных порядков, стоит отметить метод кодирования множества или некоторого линейного порядка в другой. Интересно заметить, что этот метод используется не только в этом разделе исследований, но и в первых двух, озвученных выше.

Впервые метод кодирования множества в линейный порядок применил М. Лерман [40], который доказал, что линейный порядок, являющийся сильным ^-представлением множества А, имеет вычислимое представление тогда и только тогда, когда А является Ед-множеством. Линейный порядок, упорядоченный по типу С + ао + С + а1 + С + °2 + • • • > называется сильным представленьем множества А = {ао < < а.2 < ■■•}• Таким образом, если зафиксировать множество из класса \ то линейный порядок, являющийся сильным ^-представлением этого множества, будет являться О'-вы-числимым и не будет иметь вычислимого представления. Другими словами, спектр этого порядка содержит степень 0' и не содержит степень 0 (не является тривиальным). Так как множество и линейных порядок, в который это множество кодируется, «связаны» оракулом £§, то такое кодирование называется £3-кодированием, а теорема М.Лермана— -кодирующей теоремой.

Следующая теорема, полученная Р. Доуни и Дж. Найт [15], является примером кодирования одного линейного порядка в другой. Линейный порядок Ь имеет О'-вычислимое представление тогда и только тогда, когда линейный порядок (г] + 2 + г/) ■ Ь имеет вычислимое представление. По аналогии с теоремой М. Лермана, такие теоремы носят название 01 -кодирующих теорем, а функционал Ф(Ь) = [г] + 2 + т]) ■ Ь —■ 0'-кодированием. Если в этой теореме вместо оракула 0' использовался бы оракул то, аналогично, такая теорема назвалась бы -кодирующей, а соответствующий функционал — О'")-кодирующим.

В качестве примера 0"-кодирующей теоремы приведем результат Р. Ват-

ника [51]. Линейный порядок Ь имеет 0"-вычиелимое представление тогда и только тогда, когда (" • Ь имеет вычислимое представление. Еще одним примером 0"-кодирующей теоремы является результат К. Эша и Дж. Найт [10]. Линейный порядок Ь имеет 0"-вычислимое представление тогда и только тогда, когда ш ■ Ь имеет вычислимое представление.

Заметим, что любая О'п^-кодирующая теорема позволяет получить пример спектра линейного порядка с некоторым свойством. А именно, пусть Фп — 0'")-кодируюш,ий функционал из О^-кодирующей теоремы, тогда спектр линейного порядка Фп(Ь) является нетривиальным и содержит степень О', где Ь — линейный порядок, построенный Л. Фейнером и релятивизованный относительно . В работе К. Эша [9] приведены некоторые обобщения кодирующих теорем.

В диссертационной работе получен ряд новых свойств спектров линейных порядков, а также

-кодирующих теорем. Отметим, что оба вышеприведенных примера 0"-кодирующих теорем Р. Ватника и К. Эша-Дж. Найт доказываются с помощью так называемого метода приоритета с бесконечными нарушениями или, по-другому, метода 0"-приорнтета. (С классификацией приоритетных методов можно познакомиться в книге Р. Соара [8].) Все известные О'-кодирующие теоремы доказаны с помощью приоритетного метода с конечными нарушениями или, по-другому, метод О'-приоритета. Метод 0"-приоритета явно сложнее метода О'-приоритета. Имеющаяся картина кажется логичной. Однако, в диссертационной работе доказываются некоторые обобщения всех известных 0"-кодирующих теорем с использованием только лишь метода О'-приоритета, то есть более простым методом.

Цель диссертационной работы. Диссертационная работа направлена на исследование алгоритмических свойств счетных линейных порядков. Целями работы являются изучение спектров отношения соседства, описание

достаточных свойств вычислимой представимости и исследование спектров линейных порядков.

Научная новизна. Все результаты диссертации являются новыми и снабжены подробными доказательствами, все они опубликованы в научных журналах из перечня рекомендуемых ВАК ведущих рецензируемых научных журналах и изданиях.

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

Результаты и положения, выносимые на защиту. На защиту выносятся следующие результаты:

1) Доказана замкнутость наверх нетривиального спектра отношения соседства вычислимого линейного порядка в классе перечислимых степеней. Этот результат дает исчерпывающие ответы на вопросы, поставленные в работе Р.Доуни и Дж. Реммела [18]. А именно, на вопрос существования одноэлементного или хотя бы конечного спектра отношения соседства отличного от О и О' и на вопрос принадлежности степени 0' каждому нетривиальному спектру отношения соседства вычислимого линейного порядка.

2) Проведено исследование по описанию порядковых типов линейных порядков, для которых существование низкого представления влечет существо-

14

вание вычислимого представления (вопрос Р. Доуни [13]). А именно, было

а) доказано, что каждый низкий /с-квазидискретный линейный порядок имеет вычислимое представление,

б) доказано, что каждый 2-низкий 1-квазндискретный линейный порядок является вычислимо представимым,

в) построен 2-низкий разреженный линейный порядок, не имеющий вычислимого представления (отрицательное, решение проблемы Э. Кэча и А. Монталбана [31]).

3) Проведено исследование вопроса описания спектров линейных порядков (вопрос Р. Доуни и Дж. Реммел [18]). А именно,

а) для каждого п > 1 построен линейный порядок, спектр которого в точности состоит из всех степеней, не являющихся п-низкими (косвенное подтверждение положительного решения проблемы Р. Доуни [13] о существовании линейного порядка, спектр которого содержит в точности все ненулевые степени),

б) для каждого п > 1 построен линейный порядок, спектр которого в точности состоит из всех п-высоких степеней и доказано, что не существует линейного порядка, спектр которого в точности содержит все 0-высокие или 1-высокие степени,

в) построены линейные порядки, Д^-спектры которых содержат в точности все 0-высокие и 1-высокне О'-вычислимые степени, а также О'-вычисли-мые степени, не являющиеся 1-низкими, соответственно.

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

1. Вычислимые модем и нумерации. Новосибирск, 2007, 6 - 11 августа;

2. Algebra and Logic, Theory and Applications. Красноярск, 2010, 19 - 27 июля;

3. Мальцевские чтения, Новосибирск, 2011. И - 14 октября;

4. Современные проблемы алгебры и математической логики, Казань, 2011, 22 сентября - 3 октября;

5. Workshop on Cornputability Theory, Барселона (Испания), 2011, 17 июля;

6. Definability in Computable Structures, Чикаго (США), 2012, 12- 13 мая; с краткими сообщениями:

* Logic Colloquium (Вроцлав, Польша, 2007 г.; София. Болгария, 2009; Барселона, Испания, 2011):

* Мальцевские чтения (Новосибирск, 2005, 2006, 2007, 2008, 2009, 2010, 2012 гг.);

* Вычислимость и модели (Усть-Каменогорск, Казахстан, 2009);

* Conference on Cornputability, Complexity and Randomness (Москва, 2012).

а также на научных семинарах по .математической логике в Казанском федеральном университете, Новосибирском государственном университете, институте математики им. С.Л. Соболева (Новосибирск), Омском государственном университете, Технологическом институте природы и интеллекта Чунцина (Китай, Чунцинь).

Публикации. Все основные результаты диссертации опубликованы в работах [54j-[75], из них работы [54j-[65j опубликованы в журналах, входящих в перечень ВАК рецензируемых научных журналов, в которых должны быть

опубликованы основные научные результаты диссертации на соискание ученых степеней доктора п кандидата наук.

Личный вклад автора. Работа [54] получена совместно с П. Алаевым и Дж.Тёрбером, работа [61] — с В. Харизановой и Дж. Чаб, работа [63] — с И. Калимуллиным, О. Кудиновым, Р. Миллером и В. Харизановой, работа [64] — с М. Зубковым. Во всех этих работах результаты получены в неразрывном сотрудничестве с соавторами при равном участии обеих сторон. Все остальные работы [55]—[60], [62] и [65] получены автором лично.

Структура и объем диссертации. Диссертационная работа изложена на 172 страницах и состоит из введения, четырех глав, включающих параграфы, и библиографического списка использованных источников, содержащих 81 наименований.

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

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

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

Теорема 1.1.3 Спектр отношения соседства вычислимого линейного порядка либо тривиальный, либо замкнут наверх в классе перечислнмых сте-

пеней.

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

Теорема 1.1.3 позволяет для произвольной перечислимой степени х построить вычислимый линейный порядок, спектр отношения соседства которого образует главный конус перечислимых степеней с вершиной х (следствие 1.1.6). Другими словами, для каждой перечислимой степени х существует вычислимый линейный порядок Ь такой, что ОдБр^Эисс) = {у 6 Е? | у < х}.

Также, из теоремы 1.1.3 выводится следствие 1.1.10, в которой доказывается, что степенями категоричности относительно О'-вычислимо категоричного линейного порядка могут быть только лишь 0 и 0'.

Во втором параграфе первой главы исследуется Д^-спектры отношения соседства линейных порядков. А^-Спектром отношения соседства вычислимого линейного порядка Ь называется класс

ОдБр^Бисс) = {с^т(5'исс/г) | <1е8г(Я) < 0 & Д =д, Ь}.

В теоремах 1.2.2 и 1.2.8 доказывается, что если вычислимый линейный порядок Ь либо не имеет ни наибольшего элемента, ни финального плотного сегмента, либо является сильно гу-схожим, то ИдБр^^исс) замкнут наверх в классе перечислимых степеней. Рассмотренные случаи позволяют так же, как это было сделано в предыдущем параграфе, для произвольной перечислимой степени х построить вычислимый линейный порядок, А^-спектр отношения

18

соседства которого образует главный конус псречислимых степеней с вершиной х (следствие 1.2.3).

В третьем параграфе первой главы улучшен результат Д. Хиршфельд-та. А именно, доказана теорема 1.3.1, которая утверждает, что для любого

дО

нетривиального вычислимого линейного порядка Ь, что 0 £ ОуБр^^исс), выполнено ИдБр^^исс) = Е®.

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

Теорема 2.1.1 Линейный порядок (|£/|,</,) имеет низкое представление тогда и только тогда, когда структура (|Ь|, <£, полученная путем

обогащения сигнатуры линейного порядка его отношением соседства, имеет О'-вычислимое представление.

Теорема 2.2.5 является основной теоремой второго параграфа второй главы, из нее следует, что каждый низкий линейный порядок, являющийся сильно г}-схожим, А:-дискретным или ¿-квазидискретным, соответственно О'-, О"- или О'"-изоморфен некоторому вычислимому линейному порядку. Линейный порядок называется Ажвазидискретным (¿-дискретным), если каждый максимальный блок либо мощности не больше к, либо бесконечен (имеет тип С, соответственно. Линейный порядок называется сильно ^-схожим, если существует некоторый к такой, что каждый максимальный блок мощности не больше к.

В третьем параграфе второй главы доказывается (следствие 2.3.9), что каждый низкий линейный порядок, фактор-порядок которого есть ту и который не содержит бесконечного сильно 77-схожего интервала, имеет вычислимое представление посредством 0"-вычпслимого изоморфизма.

В четвертом параграфе второй главы строятся контрпримеры ко всем выше приведенным случаям, показывающие невозможность улучшения арифметической сложности изоморфизмов. А именно, строятся низкие сильно ^-схожий, дискретный, О-квазидискретный линейные порядки, а также линейный порядок, фактор-порядок которого есть т? и который не содержит бесконечного сильно 77-схожего интервала, которые соответственно не являются вычислимо, 0'-, 0"- и О'-изоморфными никакому вычислимому линейному порядку (теоремы 2.4.1, 2.4.3, 2.4.4, 2.4.10, соответственно).

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

Следствие 3.1.2 Линейный порядок Ь = (|1<|, <ь) имеет 2-низкое представление тогда и только тогда, когда структура {\Ь\,<1, Бисс^ Р£, С^ь) имеет 0"-вычислимое представление. Здесь <5¿(п, х, у) ^ (х <ь у) & -'(З.т', у' : х <1 х' <1 у' <£ у к. |[.г-', г/'Ы = п).

Во втором параграфе третьей главы доказывается (следствие 3.2.4), что каждый 2-низкий 1-квазидискретный (1-дискретный) линейный порядок 0"'-изоморфен (0"-изоморфен, соответственно) некоторому вычислимому порядку.

В третьем параграфе третьей главы приводятся 2-низкие линейные порядки, не имеющие вычислимых представлений. В частности, доказана следующая теорема, которая является отрицательным ответом на проблему Э. Кэча и А. Монталбана [31].

Теорема 3.3.3 Существует 2-низкий разреженный линейный порядок, не имеющий вычислимого представления.

Также построены не являющиеся вычислимо нредставимыми 2-низкий сильно г?-схожий линейный порядок (предложение 3.3.4), 2-низкий ^схожий линейный порядок, не имеющий бесконечного сильно -ц-схожего интервала (теорема 3.3.5), З-ннзкий дискретный линейный порядок (предложение 3.3.6).

В четвертой главе исследуются спектры и Д^-спектры линейных порядков. В первом параграфе четвертой главы для каждого натурального числа п > 2 строятся линейные порядки, спектр одного из которых равен 1ЧопЬо\уп (теорема 4.1.4), а спектр другого равен Н^11п (предложение 4.1.8). Так как вопрос Р. Доуни о существовании линейного порядка, спектр которого содержит в точности все ненулевые степени, равносилен вопросу о существовании линейного порядка, спектр которого равен ]ЧопЬотуо; то первый из последних двух построенный пример является косвенным аргументом положительного ответа на вопрос Р. Доуни.

Во втором параграфе четвертой главы показывается, что для любого натурального числа п классы Д^-степенсй. не являющихся ».-низкими, и п-высокпх Д^-степеней также реализуются Д^-спектрами некоторых линейных порядков. Другими словами, для любого натурального числа п существуют

21

линейные порядки L\ и Li такие, что Specr**{Li) = NonLown и Spet&iM) = Highn (теорема 4.2.2 и теорема 4.2.3, соответственно).

Доказывается теорема 4.2.7, в которой устанавливается связь между £?-спектрами (и, следовательно, Д^-спектрами) линейных порядков и спектрами отношения соседства вычислимых линейных порядков, исследуемых в первой главе. Ylj-спектром линейного порядка L называется класс Spec1" (L) = Spec(L) П £?.

Теорема 4.2.7 Для каждого О'-вычислимого линейного порядка L существует вычислимый линейный порядок L, спектр отношения соседства которого совпадает с Ej-спектром линейного порядка L. Другими словами, выполнено DgSp-jiSucc) = Spec^(L).

Так как Spec(L)v' = Spec(L)A° П Xq, то любой пример Д^-сиектра линейного порядка индуцирует пример спектра отношения соседства вычислимого линейного порядка.

В третьем параграфе четвертой главы устанавливается взаимосвязь между 0'"'-кодпрующими функционалами и вычислимой представимостью п-низких линейных порядков (предложения 4.3.3 и 4.3.4), которое изучалось во второй и третьей главах, а также Д^-спектрами линейных порядков (предложения 4.3.4 и 4.3.5).

Доказывается теорема 4.3.6, позволяющая вывести целый ряд О'-кодирую-щих теорем.

Теорема 4.3.6 Пусть т является вычислимым линейным порядком без наименьшего н наибольшего элементов. Если L является О'-вычислимым линейным порядком, то т ■ L имеет вычислимое представление.

В четвертом параграфе четвертой главы доказываются теоремы 4.4.1 и 4.4.7, позволяющие вывести целый ряд 0"-кодирующих теорем.

Теорема 4.4.1 Пусть г является О'-вычислнмым линейным порядком с О'-вычислимым отношением соседства, не имеющий сильно ^-схожего ни начального, ни финального сегментов. Если Ь является 0"-вычислимым линейным порядком, то т • Ь имеет низкое представление.

Теорема 4.4.7 Пусть т является О'-вычислимым к- к в аз и д и с к р ет н ы м т]-схожим линейным порядком с О'-вычислимым отношением соседства, не имеющий (к — 1)-квазидискретного ни начального, ни финального сегментов. Если Ь является 0"-вычнслимым линейным порядком, то т ■ Ь имеет низкое представление.

В качестве применения приведенных теорем можно отметить, что теорема 4.4.1 позволяет получить альтернативное более простое доказательство, использующее метод приоритета с конечными нарушениями, результатов Р. Ватника [51] н К. Эша и Дж. Найт [10]. оба полученных авторами с помощью сложного метода приоритета с бесконечными нарушениями.

Литература

¡1] Гончаров С.С., В.Д. Дзагоев Автоустойчивость моделей , / Алгебра и логика. - 1980. - Т.19. С.45-58.

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

[3] Мальцев А.И. Конструктивные алгебры. // / УМН, 16:3(99) (1961), 3-60

[4] Мальцев А.И. О рекурсивных абелевых группах // Доклады Акад. наук СССР, - 1962. - Т. 146, №5. - С.1009-1012.

[5] Новиков П.С. Об алгоритмической неразрешимости проблемы тождества // Докл. АН СССР. - 1952. - Т.85, №4. - С. 709-712.

[6] Перетятькнн М. Каждое рекурсивно перечисаимое расширение теории линейных порядков имеет конструктивную модель // Алгебра и логика, - 1973. - Т. 12, № 2. - С.211-219.

[7] Пинус А. Эффективные линейные порядки // Сиб. мат. жур., - 1975. -Т. 16. С.956-962.

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

[9] Ash C.J. A construction for recursive linear orderings // The Journal of Symbolic Logic, - 1991. - V.56, №2, - P.G73-683.

[10] Ash C.J., Knight J. Computable structures and the hyperarithmetical hierarchy. Studies in Logic and the Foundations of Mathematics, 144. North-Holland Publishing Co., Amsterdam, 2000. xvi+346 pp.

[11] Csima B.F., Franklin J.N.Y., Shore R.A. Degrees of categoricity and the hyperarithmetic hierarchy .// Notre Dame J. Formal Logic, - 2013. - V.54, №2. - P.215-231.

[12] Downey R.G. On presentations of algebraic structures, in Complexity, Logic, and Recursion Theory, ed. A. Sorbi, New York: Dekker, 1997, P. 157-205.

[13] Downey R.G. Cornputability theory and linear orders. In: Ershov, Yu.L., Goncharov. S.S., Nerode, A., Reinmel, J.B. (eds.) Handbook of Recursive Mathematics, 1998. V. 138 of Studies in Logic and the Foundations of Mathematics, chapter 14. Elsevier.

[14] Downey R.G., Jockusch C.G. Every low Boolean algebra is isomorphic to a recursive one // Proceedings of the American Mathematical Society. - 1994.

- V.122, №3. - P.871-880.

[15] Downey R.G., Knight J.F. Orderings with a-th jump degree 0(a) // Proceedings of tiie American Mathematical Society, - 1992. - V.114, №2.

- P.545-552.

[16] Downey R.G., Moses M.F. On choice sets and strongly nontrivial self-embeddings of recursive linear orderings // Zeitschrift. fur Matheinatische Logik und Grundlagen der Mathematik, - 1989. - V.35. - P.237-246.

[17] Downey R., Moses M. Recursive linear orders with incomplete successivities // Transactions of the American Mathematical Society, - 1991. - V.326. -P.653-668.

[18] Downey R., Remmel J.B. Questions in Computable Algebra and Combinatorics. Wellington, N.Z.: School of Mathematical and Computing Sciences, Victoria University of Wellington, 1999.

[19] Feiner. L.J. Orderings and Boolean Algebras not isomoprhic to recursive ones. Thesis, MIT, 1967.

[20] Feiner L.J. The strong homogeneity conjecture // J. Symb. Logic, - 1970. -V.35. - P.373-377.

[21] Fellner S. Recursive and finite axiomatizability of linear orderings. Ph. D. Thesis, Rutgers Univ., New Brundswick. NJ, 1976.

[22] Fokina E.B., Kalimullin I., Miller R. Degrees of categoricity of computable structures / Archive for Math. Logic, - 2010. - V.49, №1. - P.51-67.

[23] Fröhlich A., Shepherdson J. Effective procedure in field theory // Philos. Trans. Ros. Soc. London, Ser. A, - 1959. - V.248. - P.407-432.

[24] Goncharov S.S. Computability and Computable Models. Mathematical problems from applied logic. II. Logics for the XXIst century. Edited by Dov M. Gabbay. Sergey S. Goncharov and Michael Zakharyaschev. International Mathematical Series (New York), Springer, New York, 2007, P.99-216.

[25] Goncharov S.S., Harizanov V.S., Knight J.F., McCoy C., Miller R., Solomon R., Enumerations in computable structure theory // Ann. of Pure and Applied Log., - 2005. - V.136, №3. - P.219-246.

[26] Harizanov V. Degree Spectrum of a Recursive Relation on a Recursive Structure. PhD dissertation, University of Wisconsin: Madison, 1987.

[27] Harizanov V.S., Miller R. Spectra of structures and relations // Journal of Symbolic Logic, - 2007. - V.72. - P.324-348.

[28] Hirshfeldt D. Degree spectra of relations on computable structures in the presence of A" isomorphisms // J. Symbolic Logic, - 2002. - V.67. - P.697-720.

[29] Hirschfcldt D.R., Khoussainov B., Shore R.A., Slinko A.M. Degree spectra and computable dimensions in algebraic structures // Annals of Pure and Applied Logic, - 2002. V.115. - P.71-113.

[30] Jockusch C.G., Soare R.I. Degrees of orderings not isomorphic to recursive linear orderings /, Annales of Pure and Applied Logic, - 1991. - V.52. -P.39-61.

[31] Kach A., Montalban A. Cuts of linear orders // Order, - 2011. V.28. - P.593-600.

[32] Langford C.H. Theorems of deducibility // Ann. of Math., - 1927. - V.28. -P.459-471.

[33] McCoy Ch. Aq-Categoricity in Boolean algebras and linear orderings // Annals of Pure and Applied Logic, - 2003. - V.119. - P.85-120.

[34] Moses M.F. Recursive linear orders with recursive successivities // Ann. Pure and Appl. Logic, - 1984. - V.27. - P.253-264.

[35] Miller R. d-Computable categoricity for algebraic fields // The Journal of Symbolic Logic, - 2009. - V.74, №4. - P.1325-1351.

[36] Miller R. The Aj> spectrum of a linear ordering / The Journal of Symbolic Logic, - 2001. - V.66, №2. - P.470-486.

[37] Knight J.F. Degrees coded in jumps of orderings // Journal of Symbolic Logic, - 1986. - V.51. - P. 1034-1042.

[38] Knight J.F. Effective constructions of models, in Logic Colloquium, J. Paris, A. Wilkie and G. Wilmers eds., North-Holland, Amsterdam, 1986.

[39] Knight J.F., Stob M. Computable Boolean algebras // The Journal of Symbolic Logic, - 2000. - V.65, №4. - P.1605-1623.

[40] Lerman M. On recursive linear orderings '/ in: Logic Year 1979-1980, (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, CT, 1979/80), M. Lernian, J.H.Schmerl and R.I.Soare eds., Lecture Notes in Math., - 1981.

- V.859. - P.132-142.

[41] Rabin M.O. Effective computability of winning strategies // Contributions of the Theory of Games, v. 3, Princeton Univ. Press, Princeton, - 1957. -P.147-157.

[42] Remmel J.B. Recursively categorical linear orderings // Proc. Amer. Math. Soc., - 1981. - V.83. - P.379-386.

[43] Rice H. Recursive and recursively enumerable orders // Trans. Amer. Math. Soc, - 1956. - V.83. - P.277-300.

[44] Richter L.J. Degrees of structures /.' J. Symbolic Logic, - 1981. - V.46. -P.723-731.

[45] Rosenstein J.G. Linear orderings. Academic Press, New York. 1982. xvii + 487 pp.

[46] Slaman T. Relative to any nonrecursive set // Proceedings of the American Mathematical Society, - 1998. - V.126. - P.2117-2122.

[47] Soare R.I. Constructive order types on cuts // J. Synib. Logic, - 1969. -V.34. - P.285-289.

[48] Soskov I.N. Degree spectra and co-spectra of structures // Ann. Univ. Sofia,

- 2003. - V.96. - P.45-68

[49] Thurber J. Every I01U2 Boolean algebra has a recursive copy // Proceedings of the AMS, - 1995. - V.123, №12. - P.3859-3866.

[50] Vaught R.L. Sentences true in all constructive models //J. Symbolic Logic,

- 1960. - V.25, №1. - P.39-58.

[51] Watnick R. A generalization of Tcnnenbaum's theorem on effectively finite linear orderings // The Journal of Symbolic Logic, - 1984. - V.49, №2. -P.563-569.

[52] Wehner S. Enumeration, countable structure and Turing degrees // Proceedings of the American Mathematical Society, - 1998. - V.126. - P.2131-2139.

[53] Young D.R. Linear orderings under 1-1 reducibility // J. Symb. Logic, -1966. - V.31. - P.70-85.

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

Статьи из списка ВАК

[54] Алаев П., Тёрбер Дж. Вычислимость на линейных порядках, обогащенных предикатами // Алгебра, и Логика, - 2009. - Т.48, №5. - С.549-563.

[55] Фролов А.Н. Д§ копии линейных порядков // Алгебра и Логика, - 2006.

- Т.45, №3. - С.354-370.

[56] Фролов А.Н. Заметки о А ^-спектрах линейных порядков и спектрах отношения соседства на них // Известия вузов. Математика, - 2013. -№11. - С.74-78.

[57] Фролов А.Н. Линейные порядки низкой степени // Сибирский математический журнал, - 2010. - Т.51, №5. - С.1147-1162.

[58] Фролов А.Н. Линейные порядки. Теоремы кодирования // Учен. зап. Казан. ун-та. Сер. физ.-матем. науки, - 2012. - Т.154, №2. - С.142-151.

[59] Фролов А.Н. Ранги т)-функций rj-схожих линейных порядков // Известия вузов. Математика, - 2012. - №3. - С.96-99.

[60] Фролов А.Н. Представления отношения соседства вычислимого линейного порядка / Известия вузов. Математика. - 2010. - №7. - С.73-85.

[61] Chubb J., Frolov A., Harizanov V. Degree spectra of the successor relation of computable linear orderings // Archive for Mathematical Logic, - 2009. -V.48, №1. - P.7-13.

[62] Frolov A.N. Low linear orderings // Journal of Logic and Computation, -2012. - V.22, №4. - P.745-754.

[63] Frolov A., Harizanov V., Kalimullin I., Kudinov O., Miller R. Spectra ofhighn and nonlown degrees ,// Journal of Logic and Computation, - 2012. - V.22, №4. - P.755-777.

[64| Frolov A., Zubkov M., Increasing rj-represcntable degrees // Mathematical Logic Quarterly, - 2009. - V.55, №6. - P.G33-636.

[65] Frolov A. Scattered linear orderings with no computable presentation // Lobache.vskii Journal of Mathematics, - 2014. - V.35, №1. - P.19-22.

Тезисы конференций

[66] Zubkov M.V., Frolov A.N. Functions limitwise monotonic relative the Kleene's system of ordinal notations // International Conference

"MAL'TSEV MEETING"' dedicated to the 60th anniversary of Sergei Savostyanovich Goncliarov. October 11-14, - 2011. - P.114.

[67] Зубков M.B.. Фролов A.H. Предельно монотонные функции со значениями в множестве конструктивных ординалов // Алгебра п математическая логика: Материалы международной конференции, посвященной 100-летию со дня рождения профессора В.В. Морозова и молодежной школы конференции "Современные проблемы алгебры и математической логики": Казань, 25-30 сентября 2011. - Казань: КФУ, - 2011. -С.96-98.

[68] Frolov A.N. Low linear orderings // The Bulletin of Symbolic Logic, - 2010. - V.16, №1. - P.117.

[69] Фролов A.H. Алгоритмическая зависимость отношений соседства и блока вычислимых линейных порядков // Международная конференция "Мальцевские Чтения посвященная 70-летию Академика Юрия Леонидовича Ершова, 2-6 мая 2010г., - 2010. - С.54.

[70] Зубков М.В., Фролов А.Н. Примеры "с.аожных"г]-схожих линейных порядков, имеющих вычислимые копии // Международная конференция "Мальцевские Чтения посвященная 70-летию Академика Юрия Леонидовича Ершова, 2-6 мая 2010г., - 2010. - С.49.

[71] Фролов А.Н. Отношения на вычислилшх линейных порядках и иерархия Ершова / Международная конференция "Мальцевские Чтения посвященная 100-летию со дня рождения Анатолия Ивановича Мальцева, 24-28 августа 2009г., - 2009. - С. 204.

[72] Frolov A.N. A°t-categorical linear orderings // The Bulletin of Symbolic Logic, - 2008. - V.14, M. - P.140.

¡73] Фролов А.Н. Вычисилимо предапавимые квазидискретные линейные порядки ,// Международная конференция "Мальцевские чтения-2008". Электронная публикация: http://www.math.nsc.m/conference/malmeet/08/Abstracts/Frolov.pdf.

[74] Фролов А.Н. Спектр отношения соседства вычислимых линейных порядков // Международная конференция "Мальцевские чтения-2007". Электронная публикация: http://www.math.nsc.ru/conference/malmeet/07/Abstracts/frolov.pdf.

[75] Frolov A.N. Computable copies of distributive lattices with relative complements and linear orderings // The Bulletin of Symbolic Logic, - 2005. - V.2, №2. - P.275-276.

Подписано в печать 24.02.2014. Бумага офсетная. Печать ризографическая. Тираж 150 экз. Заказ 128/2

Отпечатано с готового оригинал-макета в типографии Издательства Казанского университета

420008, г. Казань, ул. Профессора Нужина, 1/37 тел. (843) 233-73-59, 233-73-28

Казанский (Приволжский) Федеральный Университет

ю?

О °

см 2 ю

На правах рукописи УДК 510.53+512.562

Фролов А.Н.

Счетные линейные порядки и их алгоритмическая сложность

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

ДИССЕРТАЦИЯ на соискание ученой степени доктора физико-математических наук

Казань - 2014

Содержание

Введение

о

Глава 1. Спектр отношения соседства ...............30

1.1. Замкнутость наверх в классе перечислимых степеней......33

1.2. Д^-С-пектры отношения соседства, образующие конусы.....46

1.3. А^-Спектры отношения соседства, содержащие 0 ........57

Глава 2. Низкие линейные порядки.................67

2.1. Описание низких представлений..................69

2.2. к-Квазидискретные линейные порядки ..............73

2.3. г/ Схожие линейные порядки....................82

2.4. Оценки изоморфизмов .......................94

Глава 3. 2-Низкие линейные порядки порядки..........109

3.1. Описание 2-низких представлений.................111

3.2. 1-Квазидискретные линейные порядки ..............116

3.3. Разреженные линейные порядки и контрпримеры........128

Глава 4. Спектры и Д^-спектры линейных порядков......136

4.1. Спектры линейных порядков....................138

4.2. Д^-спектры линейных порядков ..................144

4.3. Кодирующие теоремы. О'-Кодирование...............149

4.4. (^'-Кодирующие теоремы ......................156

Литература .................................163

Введение

Данная работа посвящена изучению алгоритмических свойств счетных линейных порядков па основе построения эффективных представлений этих структур на множестве натуральных чисел. Это направление исследований находится на стыке теории вычислимости и теории счетных линейных порядков. Счетные линейные порядки твердо заняли свое место в теории моделей — каждая счетная булева алгебра порождается некоторым счетным линейным порядком, а в теории групп особое место занимает направление исследований упорядоченных групп и прочее.

Основы теории вычислимых алгебраических структур и их моделей были заложены в работах 50-х годов прошлого века П.С. Новикова [5], О. Рабп-па |47], А. Фролиха и Дж. Шефердсона [27], Р. Воота [56], А.И. Мальцева [3] и [4] и с тех пор активно развивается. В качестве наиболее важных и современных источников можно указать книги С.С.Гончарова и Ю.Л.Ершова [2| и Дж. Пайт и К. Эша [11], а также большую обзорную работу 2007 года С.С. Гончарова [28].

Исследования в области вычислимых линейных порядков были начаты поч ти одновременно с зарождением теории вычислимых структур с работы 1956 года X. Райса [49], были продолжены в работах Д. Янга [59], Л. Фейпера [23] и [24], Р.Соара [53], М. Перетятькииа [О], А. Пин.уса [7], С. Фелнера [25] и с тех пор прочно заняли свое место в теории вычислимых структур. Так, парубеже веков выходит в свет обзорная работа Р. Доуни и Дж. Реммела [22] охватывающая все актуальные направления исследований и важные открытые вопросы в теории вычислимых структур, где теории вычислимых линейных посвящен отдельный раздел. В этом направлении наиболее важными и современными источниками являются книга Дж. Розеиштейиа [51] и обзорные работы Р. Доупи [16] и [15].

Все исследования в области вычислимых линейных порядков (и вычислимых алгебраических структур, в общем) можно условно разделить па три основных направления:

I. Исследование свойств вычислимых линейных порядков;

II. Описание достаточных (и необходимых) условий вычислимой представимости линейных порядков;

III. Описание спектров линейных порядков (то есть описание класса степеней представлений).

В представленной диссертации получены результаты по всем этим трем направлениям. Опишем их более подробно.

I) Исследование свойств вычислимых линейных порядков направлено на такие вопросы, как описание эффективной категоричности, разрешимости и n-разрешимости вычислимых линейных порядков, описание эффективных свойств отношений на них. Проще говоря, в этом направлении исследуются вычислимые линейные порядки на предмет дополнительных алгоритмических свойств.

С.С. Гончаровым и В.Д. Дзгоевым [1] и, независимо, Дж. Реммелом [48] было получено описание вычислимо категоричных вычислимых линейных порядков. (Вычислимый линейный порядок называется вычислимо категоричным, если любое его вычислимое представление ему вычислимо изоморфно.) А именно, ими было показано, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он содержит только лишь конечное число пар соседних элементов. (Два элемента линейного порядка называются парой соседних элементов, если между ними нет никакого другого элемента.) Другими словами, вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый из которых имеет тип п

или '//, где п обозначает конечный линейный порядок с п элементами (п £ М), а ?/ - тип естественного упорядочения рациональных чисел.

Ч. МакКой [38| получил описание относительно О'-вычислимо категоричных линейных порядков. (Вычислимый линейный порядок называется относительно О'-вычислимо категоричным, если любое его х-вычислимое представление ему х'-вычислимо изоморфно.) Он доказал, что вычислимый линейный порядок является относительно О'-вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый из которых имеет тип п, и, а/, £ или п'1Ь ГДО ш обозначает тип естественного упорядочения натуральных чисел, со* — целых отрицательных чисел, а £ — целых чисел, причем, каждый интервал п • ?/ имеет наибольший и наименьший элементы.

Последнее время все более популярными становятся исследования степеней категоричности алгебраических структур. Отметим в этом направлении работы И.Калимуллина, Р.Миллера и Е. Фокиной [26], Р.Миллера [411, Дж. Франклина, Б. Чимы и Р. Шора [14] и других. (Степенью категоричности некоторой вычислимой структуры называется наименьшая степень с! (если такая существует), что структура является (1-вычислимо категоричной.) Например, И. Кал и мулл ин, Р.Миллер и Е. Фокина [26] для произвольной 2-перечислимой степени (1 построили вычислимую алгебраическую структуру, степень категоричности которой есть с!. (Множество и содержащая его степень называются 2-неречислимыми, если это множество является разностью двух перечислимых множеств.)

М.Мозес [40] показал, что вычислимый линейный порядок является 1-разрешимым тогда и только тогда, когда его отношение соседства вычислимо. (Линейный порядок называется п-разрешимым, если его £„-формулы являются равномерно вычислимыми. Отношением соседства линейного порядка Ь называется бинарное отношение БиссгХ^^у), истинное в точности

па парах соседних элементов.) Отметим здесь результат К. Лэнгфорда |ЗС], который фактически означает, что дискретный линейный порядок является разрешимым тогда и только тогда, когда он является 1-разрешимым. (Линейный порядок называется разрешимым, если равномерно для всех п Е N все его Е„-формулы являются вычислимыми.)

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

Для исследования свойств отношений на вычислимых структурах В.Ха-рпзанова [30| ввела понятие спектра отношения, как класс степеней отношений различных вычислимых представлений заданной структуры. Таким образом, спектром отношения соседства вычислимого линейного порядка Ь называется класс Идвр^Зисс) — {ск^Т(3исси) \ Ь' = Ь & с\с^г(Ь') < 0}.

В выше упомянутой работе Р. Доуни и Дж. Реммела [22], опубликованной на рубеже веков, описывающей основные направления исследований и содержащей важные открытые вопросы по теории вычислимых линейных порядков, исследованию спектра отношения соседства уделяется особое внимание. Фундаментальный вопрос здесь сформулирован как вопрос об описании спектров отношения соседства вычислимых линейных порядков.

Так как отношение соседства вычислимого линейного порядка Ь задается П1-формулой в сигнатуре лииейпого порядка, то ИдБр^Зисс) содержит только перечислимые степени, то есть ВдЗрь(Зисс) С Е^.

Очевидно, что если линейный порядок Ь содержит только лишь конечное число пар соседних элементов, то Идвр^Зисс) = {0}. Такой линейный порядок и спектр его отношения соседства назовем тривиальными. Д. Хирш-фельдт [32] показал, что спектр отношения соседства нетривиального вычис-

лимого линейного порядка бесконечен, то есть если ОдБр^Бисс) ф {0}, то ОдБрь^исс) бесконечен. Р.Доуии и М.Мозес [21] построили вычислимый линейный порядок, спектр отношения соседства которого одноэлементный и равен {0'}.

Существование вычислимых линейных порядков, имеющих конечные спектры отношения соседства, подтолкнуло ряд исследователей к постановке следующих проблем, которые были опубликованы в работе Р. Доуии и Дж. Рем-мела [22] в 2000 году.

Проблема Существует ли вычислимый линейный порядок, спектр отношения соседства которого одноэлементный или хотя бы конечный, но не равный {0} и {0'} ?

Проблема Всегда ли спектр отношения соседства нетривиального вычислимого линейного порядка содержит степень О' ?

Нетрудно видеть, что вышеприведенные проблемы связаны со следующей проблемой, которая впервые была сформулирована в работе автора [07] (совместно с В.Харизаиовой и Дж.Чаб). А именно, положительное решение следующей проблемы влечет отрицательный ответ на первую из них и положительный ответ — на вторую.

Проблема Верно ли, что спектр отношения соседства вычислимого линейного порядка либо тривиальный, либо замкнут наверх в классе перечислимых степеней?

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

пои категоричности. Как показано автором диссертации (следствие 1.1.10), из положительного решения этой проблемы следует, что степенями категоричности относительно О'-вычислимо категоричного линейного порядка могут быть только лишь 0 и О'.

Перейдем к подробному описанию результатов диссертации по этому направлению исследований.

Первая глава диссертации посвящена исследованием свойств отношения соседства вычислимых линейных порядков и, в частности, решению выше поставленных проблем. А именно, в первом параграфе первой главы в теореме 1.1.3 получено положительное решение на последнюю из приведенных выше проблему и, следовательно, на первые две из них (следствия 1.1.4 и 1.1.5). Причем, теорема 1.1.3 позволяет для произвольной перечислимой степени х построить вычислимый линейный порядок, спектр отношения соседства которого образует главный конус перечислимых степеней с вершиной х (следствие 1.1.6). Другими словами, для каждой перечислимой степени х существует вычислимый линейный порядок Ь такой, что Цдвр^исс) = {у е Е? I у < х}. Также, как уже было сказано выше, из теоремы 1.1.3 выводится следствие 1.1.10, в которой доказывается, что степенями категоричности относительно О'-вычислимо категоричного линейного порядка могут быть только лишь 0 и О'.

Формально говоря, в теореме 1.1.3 показывается, что если вычислимый линейный порядок Ь не является тривиальным (ие имеет тривиальный спектр отношения соседства), то есть содержит бесконечное количество пар соседних элементов, то ОдБр^Бисс) является замкнутым наверх в классе перс-числимых степеней. Другими словами, если ОдБрь^исс) ф {0}, то для всех перечислпмых степеней а и Ь из того, что а £ ИдБрь^исс) и а < Ь, следует Ь е ОдБр^исс).

Отметим, что в теореме 1.1.3 доказано, что для каждого нетривиального

вычислимого линейного порядка Ь и перечислимого множества А >-/■ Биссь существует вычислимый линейный порядок Атакой, что В =до Ь и Биссц =т А. (Здесь запись В =до Ь означает, что существует функция / € А", являющаяся изоморфизмом порядков В, и Ь. В этом случае также пишем В =[ Ь.) Естественно возникает вопрос рассмотреть случай существования До- вместо ДЦ-вычислимого изоморфизма в формулировке выше.

Другими словами, выше приведенное наблюдение подталкивает рассмотреть Д^-спектры отношения соседства вычислимых линейных порядков. (Д^-Спектром отношения соседства вычислимого линейного порядка Ь называется класс Идвр^2(Бисс) = (с^^бмсся) | degТ(В) < 0&В=Ао £}.)

Во втором параграфе первой главы рассматриваются случаи, когда Д^-спектр отношения соседства замкнут наверх в классе перечислимых степеней. В теоремах 1.2.2 и 1.2.8 доказывается, что если вычислимый линейный порядок Ь либо не имеет пи наибольшего элемента, ни финального плотного

ДО

сегмента, либо является сильно //-схожим, то ОдЗрь2{Зисс) замкнут наверх в классе перечислимых степеней. (Линейный порядок называется сильно г/-схожим, если существует некоторый к такой, что каждый максимальный блок мощности не больше к.) Рассмотренные случаи позволяют так же, как это было сделано ранее, для произвольной перечислимой степени х построить вычислимый линейный порядок, Д^-спектр отношения соседства которого образует главный конус перечислимых степеней с вершиной х.

В третьем параграфе первой главы улучшен выше приведенный результат Д. Хиршфельдта, причем, в двух направлениях. Во-первых, результат получен для Д^-спектра вместо спектра отношения соседства. А, во-вторых, доказывается, что Д^-спектр отношения соседства нетривиального вычислимого линейного порядка не только бесконечен, по и совпадает со всем классом перечислимых степеней, то есть равен Е". А именно, доказывается теорема 1.3.1, которая утверждает, что для любого нетривиального

вычислимого линейного порядка Ь такого, что 0 £ Од8рь2(8исс), выполнено {висс) = Е".

Теорема 1.2.2, а также следствия 1.1.6, 1.2.3 и 1.2.6 опубликованы 15 работе автора |67] при неразрывном сотрудничестве с В. Харизановой и Дж.Чаб. Все остальные результаты данной главы опубликованы в собственной работе автора [66].

II) В одной из самых ранних работ по исследованию вычислимых свойств линейных порядков Л.Фейнер [24] построил О'-вычислимый линейный порядок, не имеющий вычислимого изоморфного представления. Этот результат естественным образом подталкивает к вопросу об исследовании достаточных условий вычислимой представимости линейных порядков и, более общо, к описанию вычислимо представимых линейных порядков. Последний более общий вопрос был сформулирован как фундаментальный вопрос теории вычислимых линейных порядков в уже выше упомянутой работе 2000 года Р. Доуни н Дж. Реммела [22].

А в 1998 году Р. Доуни [16] сформулировал программу исследования и описания достаточных условий вычислимой представимости линейных порядков. Эта программа является результатом целого ряда результатов. В теории вычислимости известны низкие множества, не являющиеся вычислимыми, в то же самое время низкие множества «близко расположены» к вычислимым множествам (см., например, книгу Р. Соара [8]). Естественно напрашивается предположение, что возможно некоторые низкие структуры имеют вычислимые представления. Действительно, Р. Доуни и К. Джокуш [17] доказали, что каждая низкая булева алгебра является вычислимо представимой.

Дж. Найт (неопубликовано) поставила вопрос о вычислимой представп-

мости низких линейных порядков. Однако, К. Джокуш и Р. Соар [34] дали отрицательный ответ па вопрос Дж.Пайт, показав, что не каждый низкий линейный порядок имеет вычислимое представление. Все же Р. Доуни и М. Мозес [20] доказали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. (Линейный порядок называется дискретным, если каждый его элемент имеет непосредственного соседа и слева, и справа.) Как уже было сказано выше, в результате всех перечисленных исследований Р. Доуни [16] сформулировал программу описания достаточных условий вычислимой представимости линейных порядков в виде проблемы описания порядковых свойств Р таких, что для любого низкого линейного порядка Ь из выполнимости Р(Ь) следует существование вычислимого представления.

С целью продолжения исследований в этом русле естественно обобщить выше приведенную проблему, заменив условие «иизкостп» па условие «п-низ-кости». Действительно, также, как и низкие множества, что было приведено выше, п-низкие множества «близко расположены» к вычислимым множествам. А также некоторые /¿-низкие структуры являются вычислимо пред-ставимыми. Например, Дж. Тёрбер [55] доказал, что каждая 2-низкая булева алгебра имеет вычислимое представление, а Дж.Пайт и М. Стоб [45] показали, что любая 3-пизкая и даже 4-низкая булева алгебра является вычислимо иродставимой.

Другими словами, естественно расширить проблему Р. Доуни. А именно, уделить внимание проблеме описания порядковых свойств Р7) таких, что для любого гг-низкого линейного порядка Ь из выполнимости Р„(Ь) следует существование вычислимого представления.

Первые исследования этой расширенной проблемы Р. Доуни были проведены в работе автора диссертации [61], ре