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

• Фролов, Андрей Николаевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Фролов, Андрей Николаевич

Содержание

Введение

о

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Введение диссертации (часть автореферата) на тему «Счетные линейные порядки и их алгоритмическая сложность»

Введение

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

Основы теории вычислимых алгебраических структур и их моделей были заложены в работах 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], результаты которой представлены ниже. Из прочих результатов приведем работу 2011 года, в которой Э.Кэч и А. Монталбан [35] опубликовали результат о том, что для любого натураль-

иого числа п каждый п-низкий линейный порядок Ь, имеющий только лишь конечное число разбиений па сумму двух непустых сегментов Ь = Ь\ + таких, что £¿2 не имеет наименьшего элемента, является вычислимо предста-вимым. Они же отметили, что рассмотренный порядковый тип не является тривиальным. А именно, они доказали, что существует О'-вычислимый линейный порядок такого типа, не имеющий вычислимой копии.

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

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

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

Вторая глава диссертации посвящена проблеме Р. Доуни, а третья глава — расширенной проблеме Р. Доуни. В частности, в третьей главе получено отрицательное решение проблемы Э. Кэча и А. Монталбана. Перейдем к подробному изложению результатов диссертации по этому направлению исследований.

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

тогда, когда структура (|Ц, <£, Зисс^), полученная путем обогащения сигнатуры линейного порядка его отношением соседства, имеет О'-вычислимое представление. Помимо всего прочего это описание удобно для построения низких линейных порядков с различными заданными свойствами, что будет продемонстрировано в четвертом параграфе этой же главы в георемах 2.4.1, 2.4.3, 2.4.4 и 2.4.10. В первом же параграфе приводится теорема 2.1.4, носящая технический характер, которая позволяет строить вычислимые представления для заданных линейных порядков, одно из применений продемонстрировано в теореме 2.2.5.

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

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

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

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

В первом параграфе третьей главы получено описание линейных порядков, имеющих 2-низкое представление (следствие 3.1.2). А именно, доказывается, что если пара Ь = (|Ь|,<^) является линейным порядком таким, что (\Ь\, </,, Биссь, Р[ , , (¿ь) является 0"-вычислимой структурой, то Ь имеет 2-низкое представление. Здесь (¿¿(п^х^у) (х <ь у) ^^(Зх',у' : х </, * <ь у' <ьук\\:1',у'}ь\=п).

Во втором параграфе третьей главы доказывается (следствие 3.2.4), что каждый 2-низкий 1-квазидискретный (1-дискретпый) линейный порядок 0"'-изоморфен (0"-изоморфен, соответственно) некоторому вычислимому порядку. (Напомним, что линейный порядок называется 1-коазидискретпным (1-дискретным), если каждый его максимальный блок является либо бесконечным (изоморфным С, соответственно), либо одноэлементным.) Заметим, что из выше доказанных теорем 2.4.3 и 2.4.4 следует, что алгоритмические оценки изоморфизма последнего результата (следствие 3.2.4) не могут быть улучшены. Также этот результат не верен для «З-низких» вместо «2-пизких» порядков, подробное ниже, что будет доказано в третьем параграфе этой главы (предложение 3.3.6).

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

Построен 2-низкий сильно ту-схожий линейный порядок, не имеющий вычислимого представления (предложение 3.3.4). Этот результат показывает, что следствие 2.2.8 и, следовательно, следствия 2.2.7 и 2.2.6 также не могут

быть обобщены па случай «2-низких» порядков вместо «низких».

Построен 2-низкий 77-схожий линейный порядок, не имеющий бесконечного сильно ?;-схожего интервала, не являющийся вычислимо нредставимым. Этот результат показывает, что следствие 2.3.9 не может быть обобщено на случай «2-низких» порядков вместо «низких».

В предложении 3.3.6 построен 3-низкий дискретный линейный порядок, не имеющий вычислимого представления. Этот результат показывает, что следствие 3.2.4 не может быть обобщено на случай «3-низких» порядков вместо «2-низких».

Теорема 2.3.8 и следствие 2.3.9 опубликованы в работе автора [68]. Теорема 2.3.4 и, соответственно, следствие 2.3.5 в первоначальной своей версии были опубликованы в работе автора [61], а в переработанной и улучшенной версии (в частности, с более простым доказательством и с дополнительными свойствами), которая представлена в диссертации — в работе [70], полученной при неразрывном сотрудничестве с М.Зубковым. Все остальные результаты второй главы опубликованы в работе [63].

Все результаты первого параграфа третьей главы опубликованы в работе [68], второго параграфа — в работе [60] (полученной в неразрывном сотрудничестве с П. Алаевым и Дж. Тёрбером). В третьем параграфе теорема 3.3.3 опубликована в работе [71], теорема 3.3.5 — в работе [68], предложения 3.3.4 и 3.3.6 — в работе [61].

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

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

Понятие спектра степеней произвольной алгебраической структуры (не обязательно линейного порядка) было введено Л.Рихтер [50]. Спектром алгебраической структуры Л (и, в частности, линейного порядка) называет ся класс тыоринговых степеней представлений данной структуры, то есть 5рес(Л) = {с1сgт{B) | В = Л}.

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

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

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

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

Я13 Л Я Ю111,11ХСЯ п-II из к и м и.

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

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

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

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

Список литературы диссертационного исследования кандидат наук Фролов, Андрей Николаевич, 2014 год

Литература

[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] Хисамиев Н.Г. Арифметическая иерархия абелевых групп // Сиб.мат.жур., - 1988. Т.29, №6. - С.144-159.

[10] Ash С.Л. A construction for recursive linear orderinys // The Journal of Symbolic Logic, - 1991. V.56, №2, - P.673-683.

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

[12| Ash C.J., Jockusch C.G., Knight J.F. Jumps of orderings // Transactions of the AMS, - 1990. - V.319, №2. - P.573-599.

[13] Coles R.J., Downey R., Khoussainov B. On initial segments of computable linear orders // Order, - 1997/98. - V.14. - P.107-124.

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

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

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

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

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

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

- P.545-552.

[19] Downey R., Lempp S., Wu G. On the complexity of the successivity relation

in computable linear orderings, Journal of Mathematical Logic, - 2010. -V.83, №10. - P.83-99.

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

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

[22] 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.

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

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

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

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

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

[28] Goncharov S.S. Computability and Computable Models. Mathematical problems from applied logic. II. Logics for the XXIst century. Edited by Dov

M. G abb ay, Sergey S. Goncharov and Michael Zakharyaschev. International Mathematical Series (New York), Springer, New York, 2007, P.99-216.

129] Goncharov S.S., Ilarizanov 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.

f30] Ilarizanov V. Degree Spectrum of a Recursive Relation on a Recursive Structure. PhD dissertation, University of Wisconsin: Madison, 1987.

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

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

133] 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.

[34] 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.

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

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

[37] Lcrman M., Rosenstein J.R. Recursive linear orderings // in: Patras

Logic Symposion (Proc. Logic Sympos. Patras, Greece, Aug. 18-22, 1980). G. Metakides (ed.), Stud. Logic Found. Math., - 1982. - V.109. - P.123-136.

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

[39 j Montalban A. Notes on the jump of a structure // Mathematical Theory and Computational Practice, - 2009. - P.372-378.

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

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

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

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

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

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

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

V.859. - P. 132-142.

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

|48] Rcinmel J.B. Recursively categorical linear orderings // Proc. Amer. Math. Soc., 1981. - V.83. - P.379-386.

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

[50| Richtcr L.J. Degrees of structures // J. Symbolic Logic, - 1981. - V.46. -P.723-731.

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

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

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

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

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

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

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

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

[57| Wat nick R. A generalization of Tennenbaum's theorem on effectively finite linear orderings // The Journal of Symbolic Logic, - 1984. - V.49, №2. -P. 563-569.

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

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

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

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

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

[61] Фролов А.Н. Д[] копии линейных порядков // Алгебра и Логика, - 2006. Т.45, №3. - С.354-370.

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

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

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

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

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

[67] 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.

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

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

[70] Frolov A., Zubkov M., Increasing r]-representable degrees // Mathematical Logic Quarterly, - 2009. - V.55, №6. - P.633-636.

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

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

[72] 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 Goncharov, October 11-14, - 2011. - P.114.

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

с:кой логики": Казань, 25-30 сентября 2011. - Казань: КФУ, - 2011. -С.96-98.

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

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

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

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

[78] Frolov A.N. А®-categorical linea,г orderings // The Bulletin of Symbolic Logic, - 2008. - V.14, Ш. - P.140.

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

[80] Фролов А.Н. Спектр отношения соседства вычислимых линейных порядков / / Международная конферен-

ция "Мальцевские чтения-2007". Элекггронная публикация: littp://www.math.nsc.ru/conference/malmeet/07/Abstracts/frolov.pdf.

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