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

• Бикмухаметов, Равиль Ильдарович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Бикмухаметов, Равиль Ильдарович

Содержание

Введение

Глава 1. Основные определения и обозначения

§1.1. Теория вычислимости

§1.2. Теория линейных порядков

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

§2.1. Естественные отношения

§2.2. Отношения предельности

§2.3. Алгоритмическая независимость естественных отношений

Глава 3. Начальные сегменты и естественные отношения

§3.1. Начальные сегменты с вычислимыми естественными отношениями

§3.2. Е^-начальные сегменты

§3.3. Доказательство теоремы 3.2.1

Заключение

Литература

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

Введение

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

Более обще, теория вычислимых моделей занимается изучением вопросов эффективности алгебраических структур и моделей. История изучения подобных структур обширна и берет начало с работ Д. Гильберта и М. Дена. Отечественные исследования в этом направление и становление вычислимой теории моделей как самостоятельного направления современной математической логики обязаны трудам выдающегося математика академика А. И. Мальцева [5], [6]. Одним таким классическим примером изучаемым в рамках этой теории являются вычислимые линейные порядки. Вычислимые линейные порядки широко исследовались многими авторами такими, как Р. Ганди [32], Р. Доуни[21, 22], Р. Доуни и Дж. Найт [25], Р. Доуни и М. Мозес [24], М. Мозес [37-39] X. Райе [42], Л. Фейнер [27, 29], А. Н. Фролов [9-13, 30], Дж. Харрисон [33], Чен [17], Дж. Чи-шолм и М. Мозес [18], К. Эш [16] и др.

На протяжение истории изучения линейных порядков формировался круг наиболее естественных отношений на них, а именно, отношения соседства 5, блока плотности с1п, предельности справа Р+, предельности слева Р~. Данные отношения исследовались многими авторами при изучении линейных порядков, их структурных свойств и классификации. М. Мозес [37, 38] показал, что линейный порядок имеет 1-разрешимое представление тогда и только тогда, когда он имеет вычислимое представление с вычислимым отношением соседства. С. С. Гончаров и В. Д. Дзгоев[3] и Дж. Реммел [44] показали, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он имеет только лишь конечное число соседних элементов. А. Фролов [13] показал, что линейный порядок является низким тогда и только тогда, когда он имеет 0'-вычислимое представление с 0'-вычислимым отношением со-

седства. Г. Ву, Р. Доуни, Ш. Лемпп [26] и А. Фролов [9] в совокупности показали, что спектр отношения соседства либо тривиален, либо замкнут наверх в в.п. степенях.

Отношение блока исследовались, например, в работах М. Мозеса [37, 38], где было показано, что отношение блока вычислимо категоричного 1-разрешимого линейного порядка является вычислимым. Введенные выше отношения использовались в работе Дж. Тёрбера[46], который исследовал 2-низкие булевы алгебры, порожденные линейными порядками. Также данные отношения использовались в работе П. Е. Алаева, Дж. Тёрбера, А. Н. Фролова [1] для исследования 2-низких квазидискретных линейных порядков. М. Зубков [4] исследовал отношения соседства и блока на начальных сегментах вычислимых линейных порядков, что позволило ему получить более простое доказательство теоремы Коулза-Доуни-Хусаинова [19] о существовании вычислимого линейного порядка с неконструктивизируемым ПЦ-начальным сегментом. Отношения соседства, предельности справа и предельности слева использовались в работе А. Фролова [30] для описания 2-низких линейных порядков. А именно, им было показано, что 0"-вычислимость структуры (М, <£, Бс, С}с, Рс)у гДе £ = <с) — линейный порядок, влечёт существование 2-низкого представления порядка С. Этот результат для специальных классов линейных порядков имеет более простой вид: если С = (М, <с) ~ дискретный или разреженный линейный порядок, то 0"-вычислимость структуры (М, <£, Р^} влечет суще-

ствование 2-низкого представления порядка С. Если же С = (М, <с) — квазидискретный линейный порядок, то из 0"-вычислимости структуры (М, <£, Б с, Рс, (1п£, Р£. Р^) следует, что С имеет 2-низкое представление. Изучению арифметической сложности всех введенных выше отношений также посвящена недавняя магистерская работа У. П. Тёрнера[47]. Из последних результатов видно, что отношения соседства 5", блока Р, плотности «¿п. предельности справа Р+, предельности слева Р~ играют важную роль в иссле-

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

Классический результат [21] о существование вычислимого, но не 1-вычи-слимого линейного порядка является непосредственным следствием теоремы о существовании вычислимого линейного порядка С, имеющего порядковый тип и, такого, что отношение соседства Бс невычислимо. Нетрудно видеть, однако, что отношения (¿П£, Р£ вычислимы. Следовательно, вычислимость

отношений блока плотности дпс1 предельности справа Р£ и предельности слева Рвычислимого линейного порядка С не влечет вычислимости отношения соседства Б с- В первом параграфе второй главы устанавливается, что из вычислимости любого набора вышеприведенных отношений вычислимого линейного порядка не следует вычислимость остальных отношений из этого списка. Это означает, что естественные отношения Б с, дпс-, Р£, Р£ вычислимого линейного порядка С являются алгоритмически независимыми. Второй параграф посвящен изучению отношений, которые связаны естественным образом с отношениями предельности слева и предельности справа, а именно, отношений Р^, Р^ и Р^. Показано, что данные отношения алгоритмически зависимы и получено полное описание их алгоритмической зависимости.

Естественным продолжением исследования является изучение алгоритмической зависимости этих отношений на вычислимых представлениях линейных порядков в смысле следующего определения:

Определение 1. Набор отношений назовем алгоритмически зависимым на вычислимых представлениях линейных порядков от набора отношений 7*2, если для любого линейного порядка вычислимость отношений из в некотором его вычислимом представлении влечет существование такого его вычислимого представления, что на нем вычислимы все отношения из набора Р\.

Первый результат в этом направлении был получен М. Мозесом [37], который показал, что вычислимость отношения блока Рд в некоторой вычислимой

копии Л произвольного порядка С влечет существование такого его вычислимого представления В, что отношение соседства вычислимо. Таким образом, отношение блока и соседства являются алгоритмически зависимыми в вышеуказанном смысле, а именно, если Т>\ = {5} и Я2 Э то VI алгоритмически зависит от V2 на вычислимых представлениях линейных порядков. Дж. Ремме-лом и С. С. Гончаровым было показано, что существует вычислимый линейный порядок С такой, что в любой его вычислимой копии отношение соседства Б с невычислимо. Можно заметить, что (см., например [21]) этот результат также доказывается кодированием 0'-вычислимого линейного порядка С, не имеющего вычислимого представления, в вычислимый линейный порядок С имеющий порядковый тип (77 + 2 + 77) - С. Нетрудно видеть, что порядок С является искомым. Подобные конструкции кодирования линейных порядков играют важную роль в теории. К примеру, первый пример нетривиального, то есть невычислимого линейного порядка, был построен Фейнером [27, 29], который показал, что для любого бесконечного Ед-множества М, не содержащего 0, существует вычислимый линейный порядок типа

С + По + С + п>1 + ■ ■ ■,

где по, П1, • • • перечисление М в порядке возрастания. Здесь £ обозначает тип естественного порядка целых чисел Линейный порядок такого типа называется сильным представлением множества М. Ясно, что данное кодирование допускает релятивизацию. Тогда, взяв в качестве М произвольное Е®-множество, не являющееся Ед-множеством, получаем, что сильное представление множества М имеет 0'-вычислимое представление и не изоморфно никакому вычислимому линейному порядку. В третьем параграфе второй главы получено полное описание возможных вариантов алгоритмической зависимости естественных отношений на вычислимых представлениях линейных порядков. А именно, доказано, что нет других зависимостей, кроме той, ко-

торую установил М. Мозес. Для этого были получены следующие варианты 0/-кодировок: линейный порядок С, имеет 0'-вычислимое представление тогда и только тогда, когда:

(1) линейный порядок + + + + имеет вычислимое представление С с вычислимыми отношениями соседства блока Р^, предельности слева Р^ и справа

(2) линейный порядок (С2 + ^ + С2) ' £ имеет вычислимое представление С с вычислимыми отношениями соседства и блока

аналогично,

(3) линейный порядок (С\2 + со* + (2) ■ С имеет вычислимое представление С с вычислимыми отношениями соседства Бц и блока

Третья глава посвящена изучению начальных сегментов линейных порядков. Начальные сегменты вычислимых линейных являются классическим примером подструктуры линейного порядка и предметом многочисленных исследований [4, 15, 19, 32, 43]. Отметим, что сложность начального сегмента вычислимого линейного порядка может быть очень высокой. Согласно результатам Р. Ганди [32] и Дж. Харрисона [33], существует вычислимый линейный порядок с начальным сегментом, изоморфным — наименьшему неконструктивному ординалу. М. Роу [43] показал, что П^-начальный сегмент вычислимого линейного порядка имеет вычислимое представление. С другой стороны, им был построен пример вычислимого линейного порядка с неконструктивизируе-мым Пз-начальным сегментом. Р. Коулз, Р. Доуни и Б. Хусаинов [19] показали, что существует вычислимый линейный порядок с П^-начальным сегментом, не изоморфным никакому вычислимому линейному порядку. Заметим, что доказательство последнего результата использует метод приоритета с бесконечными нарушениями. Более простое доказательство, использующее только лишь

приоритет с конечными нарушениями, получено М. В. Зубковым [4]. Для этого им были рассмотрены линейные порядки с добавленными предикатами — отношением соседства и блока. Другими словами, такие структуры (Ь, <£, Бс) и (I/, <£, ^с), где С — {Ь, <с) — линейный порядок. В частности, им были построены вычислимые структуры (Ь, <£, Бс) и {Ь, <£, содержащие неконструктивизируемые П^-начальные сегменты. В первом параграфе третьей главы рассмотрены оставшиеся случаи для отношений плотности ¿п, предельности справа Р+ и предельности слева . Доказано существование таких вычислимых структур (Ь, <£, с1пс), {Ь, <£, Р£) и (Ь, <£, Р), что их П®-начальные сегменты неизоморфны никаким вычислимым линейным порядкам с вычислимыми отношениями плотности, предельности справа и предельности слева, соответственно.

В совместной работе К. Амбос - Шпис, С. Б. Купер и С. Лемпп [15] показали, противоположно результату Р. Коулза, Р. Доуни и Б. Хусаинова, что каждый Е^-начальный сегмент любого вычислимого линейного порядка имеет вычислимую копию. В заключительном параграфе третьей главы, в дополнением к этому результату, установлено, что для любого вычислимого линейного порядок С без наибольшего элемента и любой Е^-степени а существует вычислимый линейный порядок Л такой, что его Е^-начальный сегмент изоморфен С и его тьюрингова степень есть а. Ясно, что если вычислимый линейный порядок имеет наибольший элемент, то он может быть только вычислимым (т.е. Ео-) начальным сегментом. Таким образом, доказано, что Е^-начальные сегменты вычислимых линейных порядков исчерпывают в совокупности все вычислимые линейные порядки без наибольших элементов и все Е^-степени.

Цели и задачи исследование. Целями настоящей работы являются:

I. исследование алгоритмической зависимости естественных отношений соседства блока Р, плотности с1п, предельности справа Р+ и предельности

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

II. исследование алгоритмической сложности начальных сегментов вычислимых линейных порядков с добавленными отношениями плотности с/п, предельности справа Р+ и предельности слева Р~, соответственно, и начальных сегментов, принадлежащих арифметическому уровню сложности иерархии множеств.

Следующие задачи исследования можно выделить в качестве основных:

1. получить описание алгоритмической зависимости естественных отношений соседства 5, блока Р, плотности с1п, предельности справа Р+ и предельности слева Р~ на вычислимых линейных порядках и на вычислимых представлениях линейных порядков;

2. построить вычислимые линейные порядки с добавленными отношениями плотности с1п, предельности справа Р+ и предельности слева Р~, соответственно, начальные сегменты которых не имеют вычислимых представлений с вычислимыми отношениями плотности с1п, предельности справа Р+ и предельности слева Р~\

3. доказать, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной ЕЦ-степени некоторого вычислимого линейного порядка.

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

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

ка Р, плотности ¿¿п, предельности справа Р+ и предельности слева Р на вычислимых линейных порядках;

2. получено описание алгоритмической зависимости естественных отношений соседства 5, блока .Р, плотности а?п, предельности справа Р+ и предельности слева Р~ на вычислимых представлениях линейных порядков, а именно, доказано, что нет других зависимостей, кроме той, которую установил М. Мозес [37].

3. построены вычислимые линейные порядки с добавленными отношениями плотности сЬг, предельности справа Р+ и предельности слева Р~, соответственно, такие, что их П^-начальные сегменты не имеют вычислимых представлений с вычислимыми отношениями плотности ¿п, предельности справа Р+ и предельности слева Р~]

4. доказано, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной ЕЦ-степени некоторого вычислимого линейного порядка.

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

Методология и методы исследования. В настоящей работе использованы методы теории вычислимости и теории счетных линейных порядков. Среди них можно особо выделить технику приоритета с бесконечными нарушениями и технику приоритета в комбинации с 0'-оракульной конструкцией.

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

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

Степень достоверности и апробация работы. Все основные результаты диссертации опубликованы в 9 работах [49]-[51], [53]—[58], из них 3 работы [49]—[51] опубликованы в журналах, входящих в перечень ВАК рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученых степеней доктора и кандидата наук.

Результаты диссертации докладывались на молодежных научных школах-конференциях «Лобачевские чтения - 2013» и «Лобачевские чтения - 2014» (Россия, Казань), на международных конференциях «Мальцевские чтения -2013» и «Мальцевские чтения - 2014» (Россия, Новосибирск) на международной научной конференции «Алгебра и математическая логика: теория и приложения» (Россия, Казань, 2014), на международной научной конференции «Logic Colloquium 2014» (Австрия, Вена), а также на научных семинарах по математической логике в Казанском федеральном университете.

Автор выражает глубокую признательность научному руководителю Андрею Николаевичу Фролову за постановку задач, поддержку в работе и интерес к исследованиям автора, Марату Мирзаевичу Арсланову, Искандеру Ша-гитовичу Калимуллину, Максиму Витальевичу Зубкову и Марату Хайдаровичу Файзрахманову за внимание к исследованиям автора и активное и плодотворное обсуждение.

Глава 1

Основные определения и обозначения

§1.1. Теория вычислимости

Нашей целью является изучение алгоритмической сложности естественных отношений на вычислимых линейных порядках. Для этого мы используем формализацию понятия вычислимости (вычислимости относительно оракула) посредством «машин Тьюринга» (машин Тьюринга с оракулом), которое можно найти, например, в [7]. Известно множество других точных математических формулировок класса вычислимых функций таких, как схемы Клини, А-исчис-ления и др., но поскольку все они описывают один и тот же класс функций, не имеет значения, какое из этих определений выбрано.

Множества, рассматриваемые ниже, являются подмножествами множества натуральных чисел вместе с нулем N = {0,1,2,..}. У функций, рассматриваемых ниже, если специально не оговорено другое, область определения и область значения являются подмножествами N. Греческими буквами ф, ф,... и малыми латинскими буквами /, д,... обозначаются функции, большими латинскими буквами обозначаются множества и характеристические функции этих множеств, т.е. если А С М, то А(х) или ха{х) обозначает следующую функцию:

1, если хеЛ,

ХА{х) = А{х) = <

I 0, если х £ А.

Если АСМ,тоАиМ-Л обозначают дополнение множества А до N. Если А, В С ^ то через А — В обозначается разность А \ В.

Образ пары (ж, у) относительно стандартной функции пары |(ж2 + 2ху + у2 + Зх + у) обозначается как (х,у)] запись (х\,х2,хз) означает ((х\, Х2),.хз)\

аналогично определяется (х1, Ж2, ■ ■ ■, хп). Определим проекции 7Го, 7Т\ относительно функции пары, полагая щ((х,у)) = х и 7Г1((ж,у)) = у. Для множества А обозначаем А^ = {(у, г) : (у, г) 6 А}. Если функция / в точке х определена, то пишем /(ж) в противном случае пишем /(ж) Область определения функции f обозначается через ¿от(/), область ее значений — через гапд(/) = {ж | (Зу € <*от(/))[/(у) = ж]}.

Тьюринговый функционал с гёделевым номером е обозначим через Фе. Для оракула В используем запись Ф^(ж). В случае частично вычислимых функций от одного аргумента используем запись фе вместо Ф®.

Определение 1.1.1. Множество А вычислимо относительно множества В (сводится по Тьюрингу (или Т-сводится) к множеству В или В-вычислимо) (А <г Б), если (Зе)(Уж)[Л(ж) = Фf (ж)].

Отношение <т рефлексивно и транзитивно, поэтому относительно неё можно определить отношение эквивалентности множеств: говорим, что множества А и В Т-эквивалентны (А =т В), если А <т В я В <т А. Для каждого множества А определим его Т-степень:

<1едт{А) = {В С =т А}.

Степени обозначаются полужирными латинскими буквами. Степень пустого множества обозначается 0.

Определение 1.1.2. Множество А вычислимо перечислимо (вычислимо перечислимо относительно множества В или В-вычислимо перечислимо), если А является областью определения некоторой частично вычислимой функции (Б-частично вычислимой функции). Обозначим е-ое в.п. (Б-в.п.) множество как

\¥е = (Iот{фе) {Ш? = <1от{Ф^)

и

= йот{фе,в) (\УеВ = <1от{Ф* )),

где фе^(х) = у (Ф* (ж) = у), если е,х,у < в и у является значением функции фе(х) (фВ(х)), полученным за < й шагов работы машины Тьюринга (машины Тьюринга с оракулом В) с номером е.

Последовательность (И/е15)5ек ((^ё^вем) называется вычислимым перечислением (вычислимым перечислением относительно множества В) множества (1У

Определение 1.1.3. Пусть КА = {ж : ФА{х) 4-} = {х : х £ Множество

КА называется скачком множества А и обозначается А'. п-последовательным применением операции взятия скачка получаем п-й скачок А, обозначается А^п\

Следующее предложение [8] определяет основные свойства оператора скачка.

Предложение 1.1.4. 1) Скачок А' множества А вычислимо перечислим относительно А.

2) А <Т А', но N А.

3) Если А =т В, то А' =Т В'.

Пусть а' = с1ед(А'), если А Е а. В силу предложения 1.1.4 скачок корректно определен на степенях. Если А есть пустое множество, обозначим степень его п-го скачка через Таким образом, мы имеем бесконечную иерархию

степеней 0 < 0' < 0" < ••• < < ••• Заметим, степень 0' = с1ед(К), где К = К0 = {х : х € Ж®}, называется степенью проблемы остановки, а само множество К — проблемой остановки. Множество К занимает центральное место в теории вычислимости, как первый пример вычислимо перечислимого, но невычислимого множества.

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

Определение 1.1.5. Множество А принадлежит классу Е^ (или является множеством) для п > 0, если существует такое вычислимое отношение Я(х,у\, 2/2, •■■,Уп)) что

где (3 является квантором 3, если п нечетно, и квантором V, если п четно. Множество А принадлежит классу если N — А принадлежит классу Множество А принадлежит классу , если А £ Е® П П®.

Следующая фундаментальная теорема (см., например [8]) связывает арифметическую иерархию множеств с иерархией степеней, определенной ранее при помощи оператора скачка.

Теорема 1.1.6. Для любого п > 0 справедливо

1) А 6 Е® -фф А в.п. относительно некоторого П® -множества А в.п. относительно некоторого Е®-множества;

2) А е Е°+1 А в.п. относительно 0(п);

3) А е Д°+1 ^ А <Т 0(п).

Эти определения, а также основные результаты, касающиеся теории вычислимости, могут быть найдены в книгах [2], [7], [8], [14], [40].

§1.2. Теория линейных порядков

Алгебраическая структура С = (Ь\ <с) с единственным бинарными отношением <£ называется линейным порядком, если выполнены следующие свойства:

1. X <£с Х\

2. Если х <с у к у <с z, то х <с г;

3. Если х ^-у, тогда либо х <£ у, либо у <с х.

Пусть С = {Ь; <с) и Л4 = (М; <х) — линейные порядки такие, что МСЬ. Порядок Л4 называется подпорядком порядка С, если

{Ух,у £ М)[х <мУ^х<с у].

Определение 1.2.1. Линейный порядок С = (Ь, <с} называется вычислимым (вычислимым относительно множества В или В-вычислимым), если основное множество Ь и отношение порядка <с вычислимы [В-вычислимы).

Пусть дан линейный порядок С. Порядок Л4 называется вычислимым (вычислимым относительно множества В или В-вычислимым) представлением С, если С = Л4 и Л4 вычислимый (В-вычислимый) порядок.

Если два линейных порядка изоморфны, будем говорить, что они имеют одинаковый порядковый тип. Нетрудно видеть, что отношение иметь одинаковый порядковый тип является эквивалентностью на классе всех линейных порядков. Будем предполагать, что из каждого класса эквивалентности мы выбрали по одному конкретному линейному порядку и назначили его представлять свой класс. Таких представителей будем обозначать малыми греческими буквами г], р, г,...

Определение 1.2.2. Говорят, что линейный порядок С имеет порядковый тип т, если т является представителем класса эквивалентности порядка С.

В частности, ш, £ и г] обозначают порядковые типы М, Ъ и О, соответственно.

Определение 1.2.3. Говорят, что линейный порядок £ = (Ь, <с) имеет наименьший элемент, если существует I Е Ь такой, что

(V I' еЬ)[1<1']. 16

Говорят, что линейный порядок С = (Ь, <с) имеет наибольший элемент, если существует I £ Ь такой, что

(VI' еь)[1>1'}.

Пусть С. = (Ь; <с) и Л4 = (М; <м) ~~ линейные порядки. Предположим, что Ь П М = 0, тогда определен линейный порядок С + Л4 = (Ь и М; <с+м), гДе отношение <с+м определяется следующим образом:

ж <с+м У (х £ Ь, у £ М)У

\/(ж, у £ Ькх <£ у) V (ж, у £ М&ж <Л4 у)-

Линейный порядок £ + .А// называется суммой порядков С и Л4.

Определение 1.2.4. Пусть даны линейные порядки I = (/; <х) и С = (Ь; <с). Пусть для каждого г £ I порядок Сг = [Ьг] <сг) изоморфен порядку С = (Ь; </;). Тогда произведением С на X (обозначается С • X) называется следующий линейный порядок V — (Р; <-р), где Р = и(Ьг|г£/}и

х <р у (Зг £ /[ж £ Ьг А у £ А ж <£г у])У

У(3г,7 £ / [ж £ Ьг А у £ ^ А г <х з]). Пусть т\ и 72 — порядковые типы £ и .М, соответственно. Определим тх +72 и Г1 • Г2 как порядковые типы С + Л4 и £ • Л4, соответственно.

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

Определение 1.2.5. Для произвольного линейного порядка С — (Ь, <с) обозначим через С* линейный порядок такой, что Ь* = Ь и

х <с* у О у <сх

для всех ж, у.

Тогда т* соответствует порядковому типу С*, где порядок С имеет порядковый тип т. Например, и* обозначает порядковый тип —N.

Определение 1.2.6. Линейный порядок С = (Ь, <с) называется счетным, если основное множество Ь счетно, или несчетным, в противном случае.

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

Определение 1.2.7. Линейный порядок £ = {Ь, <с) называется плотным, если

(\/я, у е Ь)(3г е Ь) [х <с у -> х <с г <с у).

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

Теорема 1.2.8. Пусть С — счетный плотный линейный порядок без наибольшего и наименьшего элементов. Тогда любой произвольный счетный линейный порядок изоморфен некоторому подпорядку порядка С.

На первый взгляд может показаться, что существует множество различных счетных плотных линейных порядков без наибольшего и наименьшего элементов. Например, кроме рациональных чисел (ф, которые имеют порядковый тип г}, можно определить (р) + (ф, (ф • 0> и {<? £ <0>|д < 0 или q > 1}, которые имеют порядковые типы г] + г], г]-Т1иг]-\-1 + г], соответственно. Тем не менее, следующий результат, который также принадлежит Кантору, показывает, что в действительно все они соответствует одному и тому же порядковому типу г].

Теорема 1.2.9. Пусть С и Л4 —- счетные плотные линейные порядки без наибольшего и наименьшего элементов. Тогда С = ЛЛ.

Данная теорема имеет важное следствие, а именно

Теорема 1.2.10. Каждый счетный плотный линейный порядок имеет либо порядковый тип 1, либо г], либо 1 + г), либо ту + 1, либо 1 + г) + 1.

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

Список литературы диссертационного исследования кандидат наук Бикмухаметов, Равиль Ильдарович, 2014 год

Литература

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

[2] Арсланов М. М. Рекурсивно перечислимые множества и степени неразрешимости. - Казань: изд-во КГУ. - 1986. - 206 с.

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

[4] Зубков М. В. О начальных сегментах вычислимых линейных порядков с дополнительными вычислимыми предикатами // Алгебра и логика. -2009. - Т. 48, - № 5. - С. 564-579.

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

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

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

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

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

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

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

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

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

[14] Шенфилд Дж. Степени неразрешимости. - Москва: Наука, 1977. - 192

[15] Ambos-Spies К., Cooper S. В., Lempp S. Initial Segments of Recursive Linear Orders // Order. - 1997. - V. 14, - №. 2. - P. 101-105.

[16] Ash C. J. Categoricity in the hyperanthmetical degrees // Annals of pure and applied logic. - 1987. - V. 34, - P. 1-34.

[17] Chen К. H. Recursive well founded linear ordermgs // Annals of mathematical logic. - 1978. - V. 13. - P. 117-147.

[18] Chisholm J., Moses M. Undecidable linear ordermgs that are nrecurswe for each n: to appear.

[19] Coles R. J., Downey R. G., Khoussainov В On Initial Segments of Computable Linear Orders // Order. - 1997. - V. 14, - № 2 - P. 107-124.

[20] S. B. Cooper. Partial Degrees and the Density Problem. Part 2: The Enumeration Degrees of the S® Sets are Dense // The Journal of Symbolic Logic. - 1984. - V. 49, - № 2. - P. 503-513.

[21] Downey R. G. Computabihty theory and linear ordermgs // Handbook of recursive mathematics. - North-Holland, Amsterdam, 1998. - V. 2. - P. 823976.

[22] Downey R. G. On presentations of algebraic structures: to appear in the proceedings of the EC COLORET network, Marcel Dekker.

[23] Downey R. G., Jockusch C. G. Every low Boolean algebra is isomorphic to a recursive one // Proc. Am. Math. Soc. - 1994. - V. 122, - № 3. - P. 871-888.

[24] Downey R. G., Moses M. Recursive linear orderings with incomplete successivities // Trans. Amer. Math. Soc. - 1991. - V. 326. - P. 653-668.

[25] Downey R. G., Knight J. F. Orderings with a-th jump degree // Proc. Amer. Math. Soc. - 1992. - V. 14. - P. 545-552.

[26] Downey R. G., Lempp S., Wu G. On the complexity of the successivity relation in computable linear orderings // Journal of Mathematical Logic. - 2010. -V. 10, № 1-2. - P. 83-99.

[27] Feiner L. J. Orderings and Boolean Algebras not isomorphic to recursive ones: Ph.D. Thesis. - MIT, Cambridge, MA, 1967, 89 p.

[28] Feiner L. J. Hierarchies of Boolean algebras // J. Symb. Logic. - 1970.- V. 35, - № 3. - C. 365-374.

[29] Feiner L. J. The strong homogeneity conjecture //J. Symb. Logic. - 1970-V. 35, - № 3. - C. 373-377.

[30] Frolov A. N. Low linear orderings // Journal of Logic and Computation. -2010. - V. 22, - No 4. - P. 745-754.

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

[32] Gandy R. O. General recursive of finite type and hierarchies of functions // Ann. Fac. Sci. Univ. Clemmont-Ferrand. - 1967. - V. 35, - No. 4. - P. 5-24.

[33] Harrison J. Recursive pseudo-well orderings // Trans. AMS. - 1968. - V. 131.

- P. 526-543.

[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, - No 3.

- P. 593-600.

[36] Kaye R. Models of Peano Arithmetic, Volume 15 of Oxford Logic Guides, Oxford University Press, New York, 1991.

[37] Moses M. Recursive Properties of Isomophism Types: Ph.D. Thesis. - Monash Univ., Clayton, Victoria, Australia, 1983.

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

[39] Moses M. n-recursive linear orderings without n + 1 -recursive copies //In Logical methods, (Ed. J. Crossley, J. Remmel, R. A. Shore and M. Sweedler).

- Birkhduser, 1993. - P. 572-592.

[40] Odifreddi P. Classical recursion theory. - Amsterdam: North-Holland. - 1989.

- 610 p.

[41] Knight J. F., Stob M. Computable Boolean algebras // J. Symb. Logic. - 2000. - V. 65, - No 4. - P. 1605-1623.

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

[43] Raw M. J. S. Complexity of automorphisms of recursive linear orders: Ph.D. Thesis. University of Wisconsin-Madison, 1995.

[44] Remmel J. В. Recursively categorical linear orderings // Proc. Amer. Math. Soc. - 1981. - V. 83. - P. 387-391.

[45] Rosenstein J. Linear orderings. - New York: Academic Press, 1982. - 487 p.

[46] Thurber J. J. Every I0W2 Boolean algebra has a recursive copy // Proc. Am. Math. Soc. - 1995. - V. 123, - No. 12. - P. 3859-3866.

[47] Turner W. P. Computable linear orders and Turing reductions: Master's Thesis.

- University of Connecticut, 2012.

[48] Watnick R. A generalization of Tennenbaum's Theorem on effectively finite recursive linear orderings // Journal of Symbolic Logic. - 1984. - V.49. -P. 563-569.

Публикации автора по теме диссертации

[49] Бикмухаметов Р. И. Алгоритмическая независимость естественных отношений на вычислимых линейных порядках // Учён. зап. Казан, гос. унта. Сер. Физ.-матем. науки. - 2013. - Т. 155, - № 3. - С. 80-90.

[50] Бикмухаметов Р. И. О Т^-начальных сегментах вычислимых линейных порядков // Алгебра и логика - 2014. - Т. 53, - № 3. - С. 413-415.

[51] Bikmukhametov R. I. Codings on Linear Orders and Algorithmic Independence of Natural Relations // Lobachevskii Journal of Mathematics. - 2014. - T. 35,

- № 4. - C. 326-331.

[52] Бикмухаметов P. И. Начальные сегменты вычислимых линейных порядков с вычислимыми естественными отношениями // Известия высших учебных заведений. Математика, принято в печать.

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

[53] Бикмухаметов Р. И. О -начальных сегментах вычислимых линеиных порядков // Тр. Матем. центра им. Н. И. Лобачевского. - Казань: Изд-во Казан, матем. об-ва. - 2013. - Т. 47. - С. 22-23.

[54] Бикмухаметов Р. И. О Т^-начальных сегментах вычислимых линейных порядков // Электронный сборник тезисов докладов международной конференции «Мальцевские Чтения». - Новосибирск: Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук. - 2013. -С. 66-67.

[55] Бикмухаметов Р.И. Вычислимые линейные порядки и естественные отношения на них / / Тр. Матем. центра им. Н. И. Лобачевского. - Казань: Изд-во К азан.матем. об-ва. - 2014. - Т. 50. - С. 27-29.

[56] Bikmukhametov R. I. On initial segments of computable linear orders // Abstract Booklet of Logic Colloquium and Logic, Algebra and Truth Degrees.

- Vienna, Austria. - 2014. - P. 37-38.

[57] Бикмухаметов P. И. О Т^-начальных сегментах вычислимых линейных порядков // Материалы международной конференции «Алгебра и математическая логика: теория и приложения». - Казань: КФУ. - 2014. - С. 44-45.

[58] Бикмухаметов Р.И. Вычислимые линейные порядки и естественные отношения на них // Электронный сборник тезисов докладов международной конференции «Мальцевские Чтения». - Новосибирск: Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук - 2014.

- С. 39-40.