Содержание к диссертации
Введение
Глава 1. Спектр отношения соседства 30
1.1. Замкнутость наверх в классе перечислимых степеней 33
1.2. А -Спектры отношения соседства, образующие конусы 46
1.3. А -Спектры отношения соседства, содержащие 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
Литература
- А -Спектры отношения соседства, содержащие
- Квазидискретные линейные порядки
- Квазидискретные линейные порядки
- А -спектры линейных порядков
Введение к работе
Актуальность работы. Данная работа посвящена изучению алгоритмических свойств счетных линейных порядков на основе построения эффективных представлений этих структур на множестве натуральных чисел. Это направление исследований находится на стыке теории вычислимости и теории счетных линейных порядков. Счетные линейные порядки твердо заняли свое место в теории моделей — каждая счетная булева алгебра порождается некоторым счетным линейным порядком, а в теории групп особое место занимает направление исследований упорядоченных групп и прочее.
Основы теории вычислимых алгебраических структур и их моделей были заложены в работах 50-х годов прошлого века П.С. Новикова [], О. Раби-на [41], А.Фролиха и Дж.Шефердсона [], Р.Воота [50], А.И. Мальцева [] и [] и с тех пор активно развивается. В качестве наиболее важных и современных источников можно указать книги С.С. Гончарова и Ю.Л.Ершова [2] и Дж. Найт и К.Эша [], а также большую обзорную работу 2007 года С.С. Гончарова [].
Исследования в области вычислимых линейных порядков были начаты почти одновременно с зарождением теории вычислимых структур с работы 1956 года Х.Райса [], были продолжены в работах Д.Янга [], Л.Фейнера [19] и [], Р. Соара [], М.Перетятькина [], А. Пинуса [], С. Фелнера [] и с тех пор прочно заняли свое место в теории вычислимых структур. Так, нарубеже веков выходит в свет обзорная работа Р.Доуни и Дж.Реммела [] охватывающая все актуальные направления исследований и важные открытые вопросы в теории вычислимых структур, где теории вычислимых линейных посвящен отдельный раздел. В этом направлении наиболее важными и современными источниками являются книга Дж. Розенштейна [] и обзорные работы Р. Доуни [] и [12].
Все исследования в области вычислимых линейных порядков (и вычислимых алгебраических структур, в общем) можно условно разделить на три основных направления:
I. Исследование свойств вычислимых линейных порядков;
II. Описание достаточных (и необходимых) условий вычислимой предста
вимости линейных порядков;
III. Описание спектров линейных порядков (то есть описание класса сте
пеней представлений).
В представленной диссертации получены результаты по всем этим трем направлениям. Опишем их более подробно.
I) Исследование свойств вычислимых линейных порядков направлено на такие вопросы, как описание эффективной категоричности, разрешимости и n-разрешимости вычислимых линейных порядков, описание эффективных свойств отношений на них. Проще говоря, в этом направлении исследуются вычислимые линейные порядки на предмет дополнительных алгоритмических свойств.
С.С.Гончаровым и В.Д.Дзгоевым [] и, независимо, Дж. Реммелом [] было получено описание вычислимо категоричных вычислимых линейных порядков. А именно, ими было показано, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он содержит только лишь конечное число пар соседних элементов.
Ч. МакКой [] получил описание относительно (У-вычислимо категоричных линейных порядков. Он доказал, что вычислимый линейный порядок является относительно (У-вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый из которых имеет тип n, и, и*, ( или п rj, где каждый интервал п г] имеет наибольший и наименьший элементы.
Последнее время все более популярными становятся исследования степеней категоричности алгебраических структур. Отметим в этом направлении работы И. Калимуллина, Р.Миллера и Е. Фокиной [], Р.Миллера [], Дж. Франклина, Б. Чимы и Р. Шора [] и других. Например, И. Калимуллин, Р. Миллер и Е. Фокина [] для произвольной 2-перечислимой степени d построили вычислимую алгебраическую структуру, степень категоричности которой есть d.
М. Мозес [] показал, что вычислимый линейный порядок является 1-раз-решимым тогда и только тогда, когда его отношение соседства вычислимо. Отметим здесь результат К.Лэнгфорда [], который фактически означает, что дискретный линейный порядок является разрешимым тогда и только тогда, когда он является 1-разрешимым.
Из вышеприведенных результатов видна связь между вопросами описания эффективно категоричных, разрешимых, n-разрешимых вычислимых линейных порядков и вопросом описания свойств отношения соседства вычислимых линейных порядков. В данной работе получены результаты, также указывающие на связи указанных вопросов.
Для исследования свойств отношений на вычислимых структурах В.Ха-ризанова [] ввела понятие спектра отношения, как класс степеней отношений различных вычислимых представлений заданной структуры. Таким образом, спектром отношения соседства вычислимого линейного порядка L называется класс DgSpL(Succ) = {degT(SucCu) \ V ^ L k degT(L/) < 0}.
В выше упомянутой работе Р. Доуни и Дж. Реммела [], опубликованной на рубеже веков, описывающей основные направления исследований и содержащей важные открытые вопросы по теории вычислимых линейных порядков, исследованию спектра отношения соседства уделяется особое внимание. Фундаментальный вопрос здесь сформулирован как вопрос об описании спектров отношения соседства вычислимых линейных порядков.
Так как отношение соседства вычислимого линейного порядка L задается Пі-формулой в сигнатуре линейного порядка, то DgSpL{Succ) содержит только перечислимые степени, то есть DgSpb(Succ) С Х^.
Очевидно, что если линейный порядок L содержит только лишь конечное число пар соседних элементов, то DgSpL{Succ) = {0}. Такой линейный порядок и спектр его отношения соседства назовем тривиальными. Д. Хирш-фельдт [] показал, что спектр отношения соседства нетривиального вычислимого линейного порядка бесконечен, то есть если DgSpb(Succ) ^ {0}, то DgSpb(Succ) бесконечен. Р.Доуни и М.Мозес [] построили вычислимый линейный порядок, спектр отношения соседства которого одноэлементный и равен {0'}.
Существование вычислимых линейных порядков, имеющих конечные спектры отношения соседства, подтолкнуло ряд исследователей к постановке следующих проблем, которые были опубликованы в работе Р.Доуни и Дж. Рем-мела [] в 2000 году.
Проблема Существует ли вычислимый линейный порядок, спектр отношения соседства которого одноэлементный или хотя бы конечный, но не равный {0} и {0'}?
Проблема Всегда ли спектр отношения соседства нетривиального вычислимого линейного порядка содержит степень 0'?
Нетрудно видеть, что вышеприведенные проблемы связаны со следующей проблемой, которая впервые была сформулирована в работе автора [] (совместно с В.Харизановой и Дж.Чаб). А именно, положительное решение следующей проблемы влечет отрицательный ответ на первую из них и положительный ответ — на вторую.
Проблема Верно ли, что спектр отношения соседства вычислимого линейного порядка либо тривиальный, либо замкнут наверх в классе перечислимых степеней?
В диссертационной работе получено положительное решение последней проблемы, которая также имеет применение в описании свойств эффективной категоричности. А именно, из положительного решения этой проблемы следует, что степенями категоричности относительно 0-вычислимо категоричного линейного порядка могут быть только лишь 0 и 0.
II) В одной из самых ранних работ по исследованию вычислимых свойств линейных порядков Л.Фейнер [] построил 0-вычислимый линейный порядок, не имеющий вычислимого изоморфного представления. Этот результат естественным образом подталкивает к вопросу об исследовании достаточных условий вычислимой представимости линейных порядков и, более общо, к описанию вычислимо представимых линейных порядков. Последний более общий вопрос был сформулирован как фундаментальный вопрос теории вычислимых линейных порядков в уже выше упомянутой работе 2000 года Р.Доуни и Дж.Реммела [].
А в 1998 году Р.Доуни [] сформулировал программу исследования и описания достаточных условий вычислимой представимости линейных порядков. Эта программа является результатом целого ряда результатов. В теории вычислимости известны низкие множества, не являющиеся вычислимыми, в то же самое время низкие множества «близко расположены» к вычислимым множествам (см., например, книгу Р.Соара []). Естественно напрашивается предположение, что возможно некоторые низкие структуры имеют вычислимые представления. Действительно, Р.Доуни и К.Джокуш [] дока-7
зали, что каждая низкая булева алгебра является вычислимо представимой.
Дж. Найт (неопубликовано) поставила вопрос о вычислимой представимости низких линейных порядков. Однако, К.Джокуш и Р.Соар [30] дали отрицательный ответ на вопрос Дж.Найт, показав, что не каждый низкий линейный порядок имеет вычислимое представление. Все же Р.Доуни и М.Мозес [] доказали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Как уже было сказано выше, в результате всех перечисленных исследований Р.Доуни [] сформулировал программу описания достаточных условий вычислимой представимости линейных порядков в виде проблемы описания порядковых свойств P таких, что для любого низкого линейного порядка L из выполнимости P(L) следует существование вычислимого представления.
С целью продолжения исследований в этом русле естественно обобщить выше приведенную проблему, заменив условие «низкости» на условие «n-низ-кости». Действительно, также, как и низкие множества, что было приведено выше, n-низкие множества «близко расположены» к вычислимым множествам. А также некоторые n-низкие структуры являются вычислимо пред-ставимыми. Например, Дж. Тёрбер [] доказал, что каждая 2-низкая булева алгебра имеет вычислимое представление, а Дж. Найт и М.Стоб [] показали, что любая 3-низкая и даже 4-низкая булева алгебра является вычислимо представимой.
Другими словами, естественно расширить проблему Р.Доуни. А именно, уделить внимание проблеме описания порядковых свойств Pn таких, что для любого n-низкого линейного порядка L из выполнимости Pn(L) следует существование вычислимого представления.
Первые исследования этой расширенной проблемы Р.Доуни были проведены в работе автора диссертации [55], результаты которой представлены ниже. Из прочих результатов приведем работу 2011 года, в которой Э.Кэч и
А.Монталбан [] опубликовали результат о том, что для любого натурального числа n каждый n-низкий линейный порядок L, имеющий только лишь конечное число разбиений на сумму двух непустых сегментов L = L1 + L2 таких, что L2 не имеет наименьшего элемента, является вычислимо предста-вимым. Они же отметили, что рассмотренный порядковый тип не является тривиальным. А именно, они доказали, что существует 0-вычислимый линейный порядок такого типа, не имеющий вычислимой копии.
Заметим, что выше описанный порядковый тип является разреженным. Это и некоторые другие наблюдения подтолкнули в той же работе Э.Кэча и А.Монталбана [] поставить следующую проблему о 2-низких разреженных линейных порядках.
Проблема Верно ли, что каждый 2-низкий разреженный линейный порядок имеет вычислимое представление?
В диссертационной работе описан широкие классы линейных порядков, для которых существование низких и, соответственно, 2-низких представлений следует вычислимая представимость. Также в работе получен ряд отрицательных результатов. В частности, получено отрицательное решение последней проблемы.
III) Описание спектров линейных порядков, как и произвольных структур, является сравнительно молодым направлением исследований, но естественно дополняет два выше перечисленных, и в последние годы становиться все более активно изучаемым. Поэтому описание спектров линейных порядков также, как и предыдущие направления исследований, не осталось без внимания в работе Р.Доуни и Дж.Реммела [], как уже говорилось выше, опубликованной на рубеже веков и содержащая самые актуальные вопро-9
сы по теории вычислимых линейных порядков. А именно, формулируется фундаментальный вопрос, заключающийся в описании спектров линейных порядков.
Понятие спектра степеней произвольной алгебраической структуры (не обязательно линейного порядка) было введено Л.Рихтер []. Спектром алгебраической структуры Л (и, в частности, линейного порядка) называется класс тьюринговых степеней представлений данной структуры, то есть Spec(A) = {degT(B) I В ^ Л}.
Несмотря на уже достаточно большое количество исследований по описанию спектров алгебраических структур, полное их описание еще далеко от своего завершения. Отметим исследования, в том числе и связанные с линейными порядками, таких авторов, как В.Харизанова и Р.Миллер [], А. Слинко, Д.Хиршфильтд, Б.Хусаинов и Р. Шор [], И. Сосков [].
Особо стоит отметить следующие работы. Дж. Найт [] показала, что спектр большинства (а именно, не являющихся автоморфно тривиальными) алгебраических структур и, в частности, линейных порядков, замкнут наверх.
Т. Сламан [] и С. Вейнер [] независимо друг от друга построили счетную алгебраическую структуру Л такую, что Spec(A) = D \ {0}, где D — класс всех тьюринговых степеней. Другими словами, построена алгебраическая структура, спектр которой состоит в точности из всех ненулевых степеней.
С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон [] построили для любого пЕш алгебраическую структуру ЛП, чей спектр содержит в точности всех степени, не являющиеся п-низкими, то есть, такую, что Spec(An) = NonLown, где NonLown - класс всех степеней, не являющихся п-низкими.
Изучение же спектров линейных порядков оказалась более трудной за-
дачей. Напомним, Дж. Найт [] показала, что спектр линейных порядков замкнут наверх (см. также Дж. Найт [] или К.Джокуш и Р. Соар [30]). Л. Рихтер [] доказала, что если спектр линейного порядка имеет наименьшую степень, то этой степенью может быть только степень 0.
В 1998 г. Р. Доуни [] поставил вопрос о существовании линейного порядка, спектр которого совпадает со спектром Сламана-Вейнера. А именно, он поставил следующую проблему.
Проблема Существует ли линейный порядок, спектр которого содержит в точности все ненулевые степени.
Р. Миллер [] с целью лучшего понимания строения спектров предложил изучить А^-спектры линейных порядков. А2- Спектром линейного порядка называется класс Spec^(L) = Spec(L) П А2. Изучение таких ограниченных спектров алгебраических структур (не обязательно линейных порядков) также вызывает самостоятельный интерес у исследователей.
Р. Миллер [] доказал, что существует такой линейный порядок L, что SpecA2(L) = А — {0}, то есть А^-спектр этого порядка состоит в точности из всех ненулевых А^-степеней. Позже было замечено, что построенный Р. Миллером линейный порядок имеет представления по крайней мере во всех гипериммунных степенях. Исследования этого порядка продолжаются и до сих пор.
Так как спектры линейных порядков замкнуты наверх, то естественно рассмотреть в качестве таких примеров известные замкнутые наверх классы степеней. В качестве таких классов, по аналогии с выше упомянутой работой С.Гончарова, В. Харизановой, Дж. Найт, К. МакКоя, Р.Миллера и Р.Соломона [], рассматриваются классы степеней, не являющихся n-низ-кими, (класс NonLown) и n-высоких степеней (класс High).
Среди методов, использованных при построении спектров и А^-спектров линейных порядков, стоит отметить метод кодирования множества или некоторого линейного порядка в другой. Интересно заметить, что этот метод используется не только в этом разделе исследований, но и в первых двух, озвученных выше.
Впервые метод кодирования множества в линейный порядок применил М. Лерман [], который доказал, что линейный порядок, являющийся сильным (-представлением множества А, имеет вычислимое представление тогда и только тогда, когда А является ИЦ-множеством. Линейный порядок, упорядоченный по типу C + a0 + C + ai + C + «2 + ---, называется сильным (-представлением множества А = {а0 < сц < а2 < }. Таким образом, если зафиксировать множество из класса Sj \ S3, то линейный порядок, являющийся сильным (-представлением этого множества, будет являться 0'-вы-числимым и не будет иметь вычислимого представления. Другими словами, спектр этого порядка содержит степень 0' и не содержит степень 0 (не является тривиальным). Так как множество и линейных порядок, в который это множество кодируется, «связаны» оракулом [], то такое кодирование называется ^-кодированием, а теорема М. Лермана - ^-кодирующей теоремой.
Следующая теорема, полученная Р. Доуни и Дж. Найт [], является примером кодирования одного линейного порядка в другой. Линейный порядок L имеет 0'-вычислимое представление тогда и только тогда, когда линейный порядок (г) + 2 + г}) L имеет вычислимое представление. По аналогии с теоремой М. Лермана, такие теоремы носят название 0'-кодирующих теорем, а функционал ФЩ = (ту + 2 + rj) L 0'-кодированием. Если в этой теореме вместо оракула 0' использовался бы оракул 0^, то, аналогично, такая теорема назвалась бы 0^ -кодирующей, а соответствующий функционал -0^-кодирующим.
В качестве примера 0'-кодирующей теоремы приведем результат Р. Ват-
ника []. Линейный порядок L имеет 0"-вычислимое представление тогда и только тогда, когда ( L имеет вычислимое представление. Еще одним примером 0"-кодирующей теоремы является результат К.Эша и Дж. Найт []. Линейный порядок L имеет 0"-вычислимое представление тогда и только тогда, когда ш L имеет вычислимое представление.
Заметим, что любая 0^-кодирующая теорема позволяет получить пример спектра линейного порядка с некоторым свойством. А именно, пусть Фп 0М-кодирующий функционал из 0^-кодирующей теоремы, тогда спектр линейного порядка Фп(L) является нетривиальным и содержит степень 0', где L — линейный порядок, построенный Л. Фейнером и релятивизованный относительно 0К В работе К. Эша [] приведены некоторые обобщения 0^-кодирующих теорем.
В диссертационной работе получен ряд новых свойств спектров линейных порядков, а также 0^-кодирующих теорем. Отметим, что оба вышеприведенных примера 0"-кодирующих теорем Р. Ватника и К. Эша-Дж. Найт доказываются с помощью так называемого метода приоритета с бесконечными нарушениями или, по-другому, метода 0"-приоритета. (С классификацией приоритетных методов можно познакомиться в книге Р. Соара [].) Все известные 0-кодирующие теоремы доказаны с помощью приоритетного метода с конечными нарушениями или, по-другому, метод 0-приоритета. Метод 0"-приоритета явно сложнее метода 0-приоритета. Имеющаяся картина кажется логичной. Однако, в диссертационной работе доказываются некоторые обобщения всех известных 0'-кодирующих теорем с использованием только лишь метода 0-приоритета, то есть более простым методом.
Цель диссертационной работы. Диссертационная работа направлена на исследование алгоритмических свойств счетных линейных порядков. Целями работы являются изучение спектров отношения соседства, описание
достаточных свойств вычислимой представимости и исследование спектров линейных порядков.
Научная новизна. Все результаты диссертации являются новыми и снабжены подробными доказательствами, все они опубликованы в научных журналах из перечня рекомендуемых ВАК ведущих рецензируемых научных журналах и изданиях.
Практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в дальнейших исследованиях по теории вычислимых линейных порядков в частности, и в теории вычислимых структур в общем. По полученным результатам диссертации были прочитаны специальные курсы в Казанском федеральном университете. Они также могут быть использованы при проведении семинаров, при подготовки курсовых, дипломных и диссертационных работ в различных вузах и исследовательских институтах России.
Результаты и положения, выносимые на защиту. На защиту выносятся следующие результаты:
1) Доказана замкнутость наверх нетривиального спектра отношения со
седства вычислимого линейного порядка в классе перечислимых степеней.
Этот результат дает исчерпывающие ответы на вопросы, поставленные в ра
боте Р.Доуни и Дж.Реммела []. А именно, на вопрос существования одно
элементного или хотя бы конечного спектра отношения соседства отличного
от 0 и 0 и на вопрос принадлежности степени 0 каждому нетривиальному
спектру отношения соседства вычислимого линейного порядка.
2) Проведено исследование по описанию порядковых типов линейных по
рядков, для которых существование низкого представления влечет существо-
14
вание вычислимого представления (вопрос Р. Доуни []). А именно, было
а) доказано, что каждый низкий &-квазидискретный линейный порядок
имеет вычислимое представление,
б) доказано, что каждый 2-низкий 1-квазидискретный линейный порядок
является вычислимо представимым,
в) построен 2-низкий разреженный линейный порядок, не имеющий вы
числимого представления (отрицательное решение проблемы Э. Кэча и А.
Монталбана []).
3) Проведено исследование вопроса описания спектров линейных порядков (вопрос Р. Доуни и Дж.Реммел []). А именно,
а) для каждого п > 1 построен линейный порядок, спектр которого в точ
ности состоит из всех степеней, не являющихся п-низкими (косвенное под
тверждение положительного решения проблемы Р. Доуни [] о существова
нии линейного порядка, спектр которого содержит в точности все ненулевые
степени),
б) для каждого п > 1 построен линейный порядок, спектр которого в
точности состоит из всех п-высоких степеней и доказано, что не существует
линейного порядка, спектр которого в точности содержит все 0-высокие или
1-высокие степени,
в) построены линейные порядки, Д^-спектры которых содержат в точно
сти все 0-высокие и 1-высокие О'-вычислимые степени, а также О'-вычисли-
мые степени, не являющиеся 1-низкими, соответственно.
Апробация работы. Результаты, изложенные в данной работе, докладывались на следующих международных конференциях с пленарными докладами:
1. Вычислимые модели и нумерации, Новосибирск, 2007, 6-11 августа;
-
Algebra and Logic, Theory and Applications, Красноярск, 2010, 19 – 27 июля;
-
Мальцевские чтения, Новосибирск, 2011, 11 – 14 октября;
-
Современные проблемы алгебры и математической логики, Казань, 2011, 22 сентября – 3 октября;
-
Workshop on Computability 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 Computability, Complexity and Randomness (Москва, 2012).
а также на научных семинарах по математической логике в Казанском федеральном университете, Новосибирском государственном университете, институте математики им. С.Л.Соболева (Новосибирск), Омском государственном университете, Технологическом институте природы и интеллекта Чунцина (Китай, Чунцинь).
Публикации. Все основные результаты диссертации опубликованы в работах []–[], из них работы []–[] опубликованы в журналах, входящих в перечень ВАК рецензируемых научных журналов, в которых должны быть
опубликованы основные научные результаты диссертации на соискание ученых степеней доктора и кандидата наук.
Личный вклад автора. Работа [] получена совместно с П.Алаевым и Дж.Тёрбером, работа [] — с В.Харизановой и Дж. Чаб, работа [] — с И.Калимуллиным, О.Кудиновым, Р.Миллером и В.Харизановой, работа [] — с М.Зубковым. Во всех этих работах результаты получены в неразрывном сотрудничестве с соавторами при равном участии обеих сторон. Все остальные работы [55]–[], [] и [] получены автором лично.
Структура и объем диссертации. Диссертационная работа изложена на 172 страницах и состоит из введения, четырех глав, включающих параграфы, и библиографического списка использованных источников, содержащих 81 наименований.
А -Спектры отношения соседства, содержащие
В этой главе исследуется вопрос описания достаточных условий вычислимой представимости линейных порядков. В 1998 году Р. Доуни [16] сформулировал программу этих исследований, поставив вопрос об описании порядковых свойств Р таких, что для любого низкого линейного порядка L из выполнимости Р(Ь) следует существование вычислимого представления. Во второй главе получен ряд результатов в данном направлении.
В первом параграфе этой главы приводится описание линейных порядков, имеющих низкое представление — теорема 2.1.1, а именно доказывается, что линейный порядок (L, x) имеет низкое представление тогда и только тогда, когда структура (\L\, L,SUCCL), полученная путем обогащения сигнатуры линейного порядка его отношением соседства, имеет О -вычислимое представление. Помимо всего прочего это описание удобно для построения низких линейных порядков с различными заданными свойствами, что будет продемонстрировано ниже в теоремах 2.4.1, 2.4.3, 2.4.4 и 2.4.10. В этом же параграфе приводится носящая технический характер теорема 2.1.4, которая позволяет строить вычислимые представления для заданных линейных порядков, применение которой будет продемонстрировано в основной теореме следующего параграфа.
Во втором параграфе доказывается теорема 2.2.5, из которой следует, что каждый низкий линейный порядок, являющийся сильно - -схожим, &-ДИСК-ретным или /с-квазидискретным, соответственно 0 -, 0"- или (У -изоморфен некоторому вычислимому линейному порядку. (Линейный порядок называется /с-квазидискретным (/ -дискретным), если каждый максимальный блок либо мощности не больше к: либо бесконечен (имеет тип , соответственно). Линейный порядок называется сильно - -схожим, если существует некоторый к такой, что каждый максимальный блок мощности не больше к.) В следующей главе будет показано (предложение 3.3.4), что все приведенные результаты не могут быть обобщены на случай «2-низких» порядков вместо «низких».
В третьем параграфе доказывается (следствие 2.3.9), что каждый низкий линейный порядок, фактор-порядок которого есть г] и который не содержит бесконечного сильно ту-схожего интервала, (У -изоморфен некоторому вычислимому представлению (отношение блока которого является П -вычис-лимым). В следующей главе будет показано (теорема 3.3.5), что данный результат также не может быть обобщен на случай «2-низких» порядков вместо «низких».
В четвертом параграфе строятся контрпримеры ко всем выше приведенным случаям, показывающие невозможность улучшения алгоритмической сложности изоморфизмов в арифметической иерархии. А именно, строятся низкие сильно - -схожий, дискретный, О-квазидискретный линейные порядки, а также линейный порядок, фактор-порядок которого есть ц и который не содержит бесконечного сильно ту-схожего интервала, которые соответственно не являются вычислимо, 0 -, О"- и (У-изоморфными никакому вычислимому линейному порядку (теоремы 2.4.1, 2.4.3, 2.4.4 и 2.4.10, соответственно).
Теорема 2.3.8 и следствие 2.3.9 опубликованы в работе автора [68]. Теорема 2.3.4 и, соответственно, следствие 2.3.5 в первоначальной своей версии были опубликованы в работе автора [61], а в переработанной и улучшенной версии (в частности, с более простым доказательством и с дополнительными свойствами), которая здесь представлена — в работе [70], полученной при неразрывном сотрудничестве с М. Зубковым. Все остальные результаты этой главы опубликованы в работе [63]. 2.1. Описание низких представлений
Ясно, что если линейный порядок L имеет низкую степень, то сам порядок L и отношение соседства SUCCL ЯВЛЯЮТСЯ О -ВЫЧИСЛИМЫМИ. Таким образом, структура (L, , SUCCL) является О -вычислимой. На самом деле верно и обратное.
Квазидискретные линейные порядки
Покажем сначала, что фактор-порядки L/FL И R/FR изоморфны. Пусть a,i является наименьшим натуральным числом а Є \L\ таким, что -iFx(a,t) для любого t Є {dj \ j і} (если і = 0, то это множество пусто и 2о это просто наименьшее число из L). Пусть теперь bi = f{di): A = {di \ і Є си} и В = {ЬІ \ і Є си}. Теперь из условий 1 и 2 непосредственно следует, что (A, L) И (В, Д) ЯВЛЯЮТСЯ некоторыми Х-вычислимыми представлениями для фактор-порядков L/FL И R/FR И (А} L) =J ( , L).
Построим другие Х-вычислимые представления фактор-порядков L/FL и R/FR. Предположим, что выполнено ЕР {а/). Тогда выберем а Є L, удовлетворяющий условиям F a ai) и PL (a rl). Если ЕР (а , но ЕР (а , то выберем а , для которого выполнено F a di) и Р (а г1). Если же ЕР(а и -iEP(ai), то положим а = а . Определим теперь Ло = {а і Є а;}. Точно также, полностью аналогичными построениями, определим Во = Щ \ і Є си}. Понятно, что (Ао, ь) и (-Во, ь) являются Х-вычислимыми представлениями порядков L/FL И R/FR. Также ясно, что существует Х-вычислимый изоморфизм д : (Л0, ь) - {В0, L).
Построим теперь Х-вычислимый изоморфизм порядков L и R. Зафикси руем х Є \L\. Найдем такой а , что (ж,а )- Выберем у Є Л, что [ж,а ] = [у,6 ]д и ж І й 4 / д 6 . Положим д(ж) = у. Непосредственной провер кой нетрудно убедиться, что д является искомым изоморфизмом. 2.2. к-Квазидискретные линейные порядки Определение 2.2.1. Максимальным блоком линейного порядка L называется класс [X]L = {у Є \L\ : \[х,у]ь\ +оо& \[у, X]L\ +оо}; т.е. это класс эквивалентности, который порожден отношением блока.
Определение 2.2.2. Линейный порядок L называется /с-квазидискрет ным, если \\X\L\ к или \[х]ь\ = +оо для всех х Є \L\. Определение 2.2.3. Линейный порядок L называется к-дискретным, если если \[X]L\ к или [X]L = ( для всех х Є \L\.
Дискретный линейный порядок называется просто дискретным. Определение 2.2.4. Бесконечный линейный порядок L без наибольшего и наименьшего элементов называется сильно 7-схожим; если существует некоторый к такой, что каждый максимальный блок имеет мощность не более к, то есть \[x]i\ к для всех х Є \L\.
Теорема 2.2.5. Для любого натурального числа к, для каждого О -вычислимого k-квазидискретного линейного порядка L, отношение соседства которого также О -вычислимо, существует вычислимый линейный порядок R и О -вычислимая функция вложения f : L — R, для которых верны условия 1 и 2 теоремы 2.1.4 Прежде чем перейти к доказательству этой теоремы, покажем как из нее следуют все основные результаты данного параграфа.
Следствие 2.2.6. Для каждого к Є N любой низкий к-квазидискретный порядок 0" -изоморфен некоторому вычислимому порядку. Доказательство. Отношение соседства любого низкого или вычислимого ли нейного порядка является 0 . Следовательно, все отношения S: F, Р , Р+, ЕР , ЕР+ на этих порядках вычислимы относительно 0//;. Теперь справед ливость следствия непосредственно вытекает из теорем 2.2.5 и 2.1.4. Следствие 2.2.7. Для каждого к Є N любой низкий k-дискретный порядок О"-изоморфен некоторому вычислимому порядку.
Доказательство. Отношение соседства любого низкого или вычислимого линейного порядка является 0 . Следовательно, все отношения S: F, Р , Р+ на этих порядках вычислимы относительно 0". Так как линейный порядок является к-дискретным, то отношения ЕР и ЕР+ на нем также являются 0"-вы-числимыми. Действительно, для фиксированного СІ равномерно эффективно относительно оракула О" можно либо найти такой Q+I, что S(ci,Ci+i): либо определить истинность Р+(СІ). Следовательно, для фиксированного х можно построить (У -вычислимую последовательность (конечную или бесконечную) Со, Сі,..., где Со = х и S(ci, С{+\). Если эта последовательность содержит более, чем к элементов, то из /с-дискретности данного порядка следует ЕР+(х). В противном случае имеем - ЕР+(х). Аналогично для ЕР .
Теперь справедливость следствия непосредственно вытекает из теорем 2.2.5 и 2.1.4. Следствие 2.2.8. Каждый низкий сильно ц-схожий линейный порядок (У-изоморфен некоторому вычислимому порядку. Доказательство. Отношение соседства любого низкого или вычислимого ли нейного порядка является 0 . Так как сильно ту-схожие линейные порядки не содержат бесконечных блоков, то функция, построенная в теореме 2.2.5, явля ется (У-изоморфизмом между низким сильно - -схожим линейным порядком L и вычислимым порядком R.
Квазидискретные линейные порядки
Определение 3.2.1. Любую структуру вида (L, , SUCCL} ...), полученную обогащением линейного порядка L = (L, ) тем или иным набором предикатов назовем, чтобы упростить терминологию, обогащенным линейным порядком, каждый раз в явном виде указывая тот язык, с которым работаем.
Теорема 3.2.2. Пусть L = (L, , SUCCL} Р, Р }driL} FL) является 0 -вычислимым обогащенным линейным порядком. Тогда существует вычислимый обогащенный линейный порядок R = (\R\, R,SUCCR) и 0 -вычислимое вложение f : \L\ -й \R\ такие, что (1) если ж,у Є \L\ и Succi{x y), то интервал [f(x),f(y)]ii конечен; (2) если с Є \R\ \ rang(f), то найдутся ж, у Є \L\ такие, что Suce(x,y) и f(x) Rc Rf(y). Прежде чем приступать к доказательству теоремы, получим из нее все основные результаты этого параграфа, а также докажем несколько вспомогательных лемм. Следствие 3.2.3. Пусть L = (\L\} L) является 1-квазидискретным линейным порядком. Порядок L обладает вычислимым представлением тогда и только тогда, когда обогащенный порядок (L, , SUCCL} Р, Р }driL} FL) обладает 0"-представлением.
Причем, если (\L\, L,SUCCL,PL, Р,dnL,Fi) является 0"-вычислимым таким, что L = (\L\} L) является 1-квазидискретным (1-дискретным) линейным порядком, то L является 0 "-изоморфным (0"-изоморфным, соответственно) некоторому вычислимому порядку.
Доказательство. Пусть (\L\, , SUCCL} Р} Р }driL} FL) является (У -вычис-лимым таким, что L = (L, L) является 1-квазидискретным (1-дискретным) линейным порядком. Так как L является 1-квазидискретным (1-дискретным), то предикат dn пустой (предикаты Р: Р , ЕР, ЕР пустые, соответственно) и, следовательно, (У -вычислимые. Тогда по теоремам 2.1.4 и 3.2.2 существует О -вычис-лимый линейный порядок R =д L такой, что SUCCR также является О -вы-числимым, где изоморфизм д (по теореме 2.1.4) является (У-вычислимым ((У-вычислимым).
По теореме 2.1.1 порядок R имеет низкое представление, причем, посред ством О -вычислимого изоморфизма. По следствию 2.2.6 (следствию 2.2.7, соответственно) R (и, следовательно, L) является (У -изоморфным ((У-изо морфным, соответственно) некоторому порядку. П Из предыдущего следствия непосредственно вытекают следствия ниже. Следствие 3.2.4. Каждый 2-низкий 1-квазидискретный (1-дискретный) линейный порядок (У -изоморфен (0"-изоморфен, соответственно) некоторому вычислимому порядку.
Следствие 3.2.5. Если L = (L, , SUCCL) является низким обогащенным линейным порядком таким, что (\L\, L) является 1-квазидискретным (1-дискретным), то L 0 " -изоморфен (0"-изоморфен, соответственно) некоторому вычислимому обогащенному порядку.
Отметим, что смысл этих определений очень прост — если ( ,) или (Л, Е ) — корректная структура, то она всегда может быть расширена до линейного порядка, в котором предикаты соответствуют своему изначальному определению. Наоборот, если есть линейный порядок с предикатами Succ ..., то любая его конечная подструктура будет удовлетворять условиям (1)-(6) и всегда может быть расширена до корректной структуры.
Два элемента ж, у из корректной структуры назовём связанными, если либо х = у, либо х у и существует конечный набор zo,... ,Zk такой, что ZQ = х, Zk = у и Suce(zi,Zi+i) при і к, либо у х и верен естественный аналог предыдущего случая. Обозначим это отношение как х у; ясно, что это отношение эквивалентности.
Доказательство. Лемма почти очевидна — небольшой комментарий может потребоваться только для пункта (е). Переход (= ) в нём тоже очевиден, покажем ( =). Пусть х,у Є AQ И /(Ж) f(y)- Если в Л между х = ZQ И у = Zk появились какие-то новые элементы z\ ... Zk-i, то всё равно будет выполняться /() f(zi+i) для всех і к. Следовательно, будет верно Succ(zi,Zi+i), а отсюда F(x,y) в Л и в AQ. Последнее влечет Succ(x,y). П
Доказательство следующей леммы будет использовано и в анализе основной конструкции, которая описана ниже, поэтому распишем его подробно.
Лемма 3.2.10. Пусть (Л,Е ); ( ,) — две корректные структуры, f : (Л,Е ) — ( ,) — корректное вложение и (А, ) — подструктура в другой корректной структуре (Лі,Е ). Тогда существуют ( i,S) (-B,S) и /і / такие, что f\ : (Лі,Е ) — ( i,S) является корректным вложением.
Доказательство. Выберем ж, у Є Л такие, что ж у и не существует zG Л, для которого х z у. Ясно, что достаточно описать, какие элементы будут добавлены в В в интервале [/(ж), /(у)] и как будет определена /і на { єЛіж 2 у}, так как понятие корректности является в некотором смысле локальным. Если [ж,у] 1 = {ж, у}, то эта пара не требует внимания: считаем, что [/(х),/(у)]в1 = [/(х),/(у)]в- Допустим, что существует z Є А\ такой, что х z у. Заметим, что тогда -iSucc(x,y) и неверно, что f(x)
Обозначим все элементы А\, лежащие между ж, у, как zo, , zn: х = ZQ Z\ ... zn-\ zn = у, при этом п 2. Пусть a = f(x) и b = f(y). Предположим сначала, что dn(x,y). Этот случай — самый простой. Пусть с = min{ci Є В а с\ Ь}. Добавим к В элементы ei,...,en_i, где а е\ ... en_i с, и положим fi(zi) = Є{ при 1 г п.
Пусть -idn(x,y). Тогда существует к п такое, что dn(zk,Zk+i) — зафиксируем одно из таких к (например, наименьшее). Заметим сначала, что всегда можно добавить к В несколько новых элементов так, чтобы свести задачу к одному из двух случаев:
Если, например, не существует с Є В такого, что Succ(a, с) или Suce(c, b), то случай (А) нужно получать так: пусть {с Є В \ а с Ь] равно с0,..., d. Если для какого-то і р - Succ(di}di+l), то добавим к В новый элемент d-, где di d[ di+1, и положим Succ(di}d-) и Succ(d-, di+1). Тем самым мы соединим все dj в один класс связанности. Если же Succ(a, с) для некоторого с, то точно так же нужно связать с а все элементы, кроме тех, которые связаны с 6, и получить случай (В). Это можно сделать, так как а и Ъ не связаны друг с другом. Поскольку такие преобразования не портят корректность /, будем далее считать, что верно либо (А), либо (В).
Далее конечные подструктуры в (N, Е ) будем обозначать не (А,Е ), а просто, для краткости, как (А, Е ). То же самое относится к подструктурам в (N, Е ). Будем считать, что ({0,1}, Е ) = ({0,1}, Е ) для всех s, то есть на {0,1} все предикаты определены корректно с самого начала. Пусть {DM}M =N — стандартная нумерация всех конечных подмножеств N.
А -спектры линейных порядков
Если на некотором шаге s появляется новый элемент і Є AtiS и х і у — соседние элементы в AtiS, то добавляем в R новый блок Li между блоками Lx и Ly. Если же некоторый j выходит из AtiSi на некотором шаге s : то соответствующий блок Lj присоединяем к одному из соседних блоков в R. Если соседний только один, то присоединяем к нему. Если есть соседний и слева — La: и справа — L&, то выбираем наименьшее из а и Ъ (наименьшее как натуральное число) и присоединяем блок Lj к блоку с выбранным номером. Можно считать, что L не пустой, так как иначе теорема очевидна, поэтому можно считать, что хотя бы один соседний блок имеется.
Далее, на каждом шаге в каждом блоке кладем новые элементы, строя копию т. Заметим, что присоединение блоков и справа, и слева не портит наше построение копии г, так как г не имеет наибольшего и наименьшего элементов. Описание конструкции R завершено. Пусть R = 2iGiLi. Ясно, что R является вычислимым линейным порядком. Пусть s = s(t) такой шаг, что для любого s s выполнено At = AtyS : тогда после этого шага никакой блок Li для і Є At не будет присоединен к другому, а только может быть некоторые другие будут присоединены к нему слева или справа, но, как уже говорилось выше, это не портит построение
Определение 4.3.11. Пусть линейный порядок является г]-схожим, то есть его можно представить в виде J f(q) для некоторой функции f : Q — N такой, что 0 . rang(f). В этом случае, функция f называется ц-функцией линейного порядка L.
Теорема 4.3.12. Пусть f — произвольная X-вычислимая ц-функция с неодноэлементным рангом. Тогда существует X 0 0" -вычислимая ц-функция g такая, что rang(g) = rang(f) и 9Ія) не имеет вычислимой копии. При-чем, если f имеет конечный ранг или хотя бы degT(f) 0", то функция д может быть выбрана 0" -вычислимой.
Таким образом, доказано, что для конечного множества D такого, что О ф D и \D\ 1, существует (У -вычислимая 77_ФУНКЦИЯ /, чт0 линейный порядок 2 f(q) не имеет вычислимого представления при rang(f) = D.
Пусть теперь / — произвольная ту-функция с бесконечным рангом. Построим новую функцию д: имеющую тот же самый ранг, что и /, но g(q) не имеет вычислимой копии. Зафиксируем конечное множество D С rang(f): 0 -Ои) 1.Из доказанного выше следует, что существует (У -вычислимая ту-функция /, причем rang(f) = DH f(q) не имеет вычислимого пред-ставлення. Пусть Q\ и ( — два плотных линейных порядка без концевых точек. Имеем вычислимые изоморфизмы cpi : Q — Qi, 2 : Q — Q2 и (/9 : Q — Qi + 1 + Q i- Зафиксируем произвольный элемент 2о из rang(f). Построим новую функцию д: Е м- E )+o+ E ) = E /( (9))+«» + E /(1)) = Ел«)+a + E/(") Так как линейный порядок /(g) не имеет вычислимого представления, линейный порядок 2 g{q) также не имеет вычислимого представления. На-конец, очевидно, rang(g) = rang(f). Таким образом, теорема доказана. 4.4. О"-Кодирующие теоремы
Тогда если L является О -вычислимым линейным порядком, то т L имеет вычислимое представление, обладающее вычислимым отношением соседства.
Прежде, чем переходить к доказательству этой теоремы, покажем, как из нее следует один из основных результатов данного параграфа и ряд следствий, первые два из которых были известны, но доказывались более сложным методом, а другие ранее были неизвестными и требовали собственного доказательства. Причем, нетрудно понять, что этим списком следствия этой теоремы не ограничиваются.
Для этого обозначим класс линейных порядков, которые либо имеют вычислимые представления, либо не имеют низкого представления, как Li. Другими словами, если L — низкий линейный порядок и L Є Li, то L имеет вычислимое представление. В этом обозначении вопрос Р. Доуни [16], изучаемый во второй главе, эквивалентен вопросу описания класса Li.
Следствие 4.4.2. Пусть т является О -вычислимым с О -вычислимым отношением соседства и удовлетворяет условию (1) и условию (2) теоремы 4-4-1 и такой, что т L Є Li для любого линейного порядка L. Тогда если линейный порядок L имеет 0" -вычислимое представление, то т L имеет вычислимое представление.
Доказательство. Пусть г является (У-вычислимым с (У-вычислимым отношением соседства и удовлетворяет условиям (1) и (2) теоремы 4.4.1. И пусть L является (У-вычислимым. По теореме 4.4.1, релятивизованной относительно О , линейный порядок г L имеет (У-вычислимое представление с (У-вычислимым отношением соседства.