Вычислимые линейные порядки и η-представимость тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Зубков, Максим Витальевич

• Зубков, Максим Витальевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Зубков, Максим Витальевич

Введение

Глава 1. Предельно монотонные функции и г/-схожие линейные порядки

§1.1. Некоторые свойства предельно монотонных функций.

§1.2. 77-схожие линейные порядки

Глава 2. Сильно 77-представимые множества и степени

§2.1. Объединение Е®— и П®—множеств.

§2.2. Множества и степени сильно ту-представимые и т/-представимые по неубыванию.

§2.3. Сильно 77-представимые степени в разностной иерархии

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

§3.1. П^ начальные сегменты.

§3.2. П® начальные сегменты.

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

В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Рабина и других математиков и с тех пор активно развивается.

Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел понятие степени типа изоморфизма структуры Л, как наименьшую из степеней, содержащих представление структуры Л. Применительно к линейным порядкам это определение оказалось не очень полезным. Л. Рихтер [30] установила, что если Л — порядковый тип имеющий степень, то эта степень вычислима, и если Л — подпоря-док С^, то существует такой подпорядок В = Л, что нижняя грань степеней Л и В есть 0. Техника доказательства этих утверждний может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках. Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки [30].

Естественным вопросом является проблема существования вычислимой структуры, изоморфной дайной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например, Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно пеизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характеризация вычислимо представимых вполне упорядоченных типов не представляет большой сложности. В самом деле, если Л какое-либо вполне упорядоченное арифметическое подмножество С}, тогда порядковый тип А есть вычислимый ординал, следовательно, вычислимо представим [29], [31].

Для другого естественного типа линейных порядков — дискретного линейного порядка, Р. Ватником [32] было показано, что (р имеет вычислимое представление тогда и только тогда, когда р имеет П® представление (ясно, что любой дискретный линейный порядок представим в виде (р, где С — тип естественного упорядочения целых чисел).

Доказательство этой теоремы предоставляет важный метод построения вычислимых представлений различных порядковых типов. М. Лерман [25], используя конструкцию, похожую на конструкцию в доказательстве теоремы Ватника, методом приоритета с бесконечными нарушениями на деревьях получил, что если А бесконечное Ед-множество, то существует вычислимый линейный порядок, имеющий порядковый тип:

С + п0 + С + п1 + • • • где по, щ, . — перечисление А в порядке возрастания. (Здесь предполагается, что 0 £ А).

Линейный порядок такого типа называется сильным (-представлением множества А. Если перечисление множества А берется не обязательно в порядке возрастания и, возможно, с повторениями, то такой порядок называется просто ("-представимым. С помощью алгоритма Тарского-Куратовского и результата М. Лермана легко проверить, что множество А имеет вычислимое ("-представление тогда и только тогда, когда имеет вычислимое сильное 4 ("-представление, тогда и только тогда, когда А е

Дж. Розенштейном [31] были рассмотрены г)-схожие линейные порядки. Линейный порядок называется 77-схожим, если он не содержит бесконечных 5 блоков (по определению, что элементы лежат в одном блоке, если между ними не более конечного числа различных элементов). Дж. Розенштейн доказал, что если С вычислимый ^-схожий линейный порядок, то существует такая Д§-фупкция Г : <9 —> ДО, что С, = ^ ^(о)- Используя технику, аналогичную доказательству теоремы Ватника, в частности, представление П^-множеств на деревьях, С. Феллнер [16] показал, что если ^ является П^-функцией, то линейный порядок ^ -^((7) имеет вычислимое представление. Аналогичный результат имеет место и для Е^-функций. Возникает естественный вопрос, можно ли эти результаты распространить на ДЦ-уровень арифметической иерархии? М. Лерман и Дж. Розенштейн [26] построили такую Дз-функцию, что порядок ^ не имеет вычислимой копии. Более того, Р. Доуни [14] показал, что при этом функция / может иметь конечное число значений.

Эти результаты оставляют открытым следующий вопрос: если С — вычислимый ^-схожий линейный порядок, то существует ли такая ПЦ-функция ДО, что С, = ^{ч)^ Этот вопрос ставился в нескольких работах [31], [26], [14]. В работе [8], фактически, было показано, что если £ некоторый 77-схожий линейный порядок, мощность блоков которого ограничена некоторым числом, то С имеет вычислимую копию тогда и только тогда, когда существует такая функция ^ : —> ДО, что £ = ^ Р{ч) и ергдг(Р) Е ПЦ.

Аналогично определению £-представимых и сильно ("-представимых множеств, можно определить 77-представимые и сильно г^-представимые множества, соответственно заменив в исходных определениях С на г] — тип упорядочения рациональных чисел. Как видно из определения, 77-представления являются г/-схожи ми линейными порядками. Нетрудно доказать, что 77-предста-вимые множества (то есть множества, имеющие вычислимые ^-представления) принадлежат £3 уровню арифметической иерархии [15]. Дж. Розенштейн [31] и С. Феллнер [16], соответственно, показали, что любое £[>- или

П^-множество является сильно ту-представимым. С другой стороны, М. Лер-ман [25] построил Д^-множество, не имеющее вычислимого ^-представления. Он также дал полное описание ту-представимых степеней. А именно, он доказал, что каждая Ед-степень 77-представима. Дж. Розенштейн [31] показал, что любое сильно 77-представимое множество лежит в классе А®. Он доказал, фактически, что каждое 77-представимое по неубыванию множество лежит в классе ДЦ (множество 77-представимо по неубыванию, если оно имеет вычислимое 77-представление, для некоторого неубывающего перечисления данного множества).

В связи с этими результатами Р. Доуни [13] поставил вопрос об описании сильно ?7-представимых степеней и, в частности, спросил, верно ли, что каждая ДЦ-степень содержит сильно 77-представимые множества? К. Харрис [18] построил такую Дд-степень, что она не содержит сильно 77-представимых множеств, получив, таким образом, отрицательный ответ на второй вопрос.

Н. Г. Хисамиевым [9], при исследовании конструктивизируемости абеле-вых групп специального вида, были введены предельно монотонные функции. В настоящее время они играют важную роль в изучении (с точки зрения теории вычислимости) различных структур, в том числе линейных порядков [12], [20], [24], [23]. К. Харрисом [18] была получена характеризация 77-представимых множеств в терминах предельно монотонных функций. Он доказал, что множество является 77-представимым тогда и только тогда, когда оно является множеством значений некоторой О'-предельно монотонной функции. Однако, пока не удалось получить подобного критерия для сильно 77-представимых множеств. Так К. Харрис [18] построил пример сильно 77-представимого множества, которое не является областью значений никакой возрастающей О'-предельно монотонной функции, определенной на ал В работе А. Каца и Д. Турецкого [22] было предложено рассматривать функции, определенные на множестве рациональных чисел и возрастающие не на всей области определения, а на своем носителе. В данной работе предложенные функции нашли применение при описании сильно 77-представимых степеней.

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

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

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

Предложение 1.1.12. Пусть f : (Q х и —у ш такая, что

1) для любого q € Q существует конечный предел lim /(g, s); s—>00

2) множество {lim f(q, s) | q € Q} бесконечно; s—»00

3) ({q e Q I lim f(q, s) > 1}; <Q) (ш; <>; s—>00

4) для любого s € ш функция /(•, s) псевдовозрастающая (псевдонеубывающая) на <Q.

Тогда функция F, определяемая равенством F(q) = lim f(q, s), таксисе s—> 00 псевдовозрастающая (псевдонеубывающая) на Q.

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

Теорема 1.2.2. Пусть С есть г]-схожий линейный порядок. Тогда следующие условия эквивалентны:

1) С имеет А^-копию с А®-отношениями соседства и блока;

2) С имеет А^-копию с А ^-отношением блока;

3) С ^ X) здесь Р-Ч —и ергдг(Г) Е П°;

4) С ^ £ Ня), здесь р ■ ^ —" ^ и Р{ч) = Лял любого <7 Е <1^ и некоторой вычислимой функции f;

5) С имеет вычислимую копию с И\-отношением блока.

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

Вторая глава посвящена, в основном, исследованию сильно ту-представимых множеств.

Определение 2.1.1. Пусть {ао, а2 .} ~ перечисление, возможно с повторениями, множества АС. ш. Тогда порядок С типа

77 + а0 + 77 + а\ + г) + а2 + 77 + . называется г/-представлением множества А. Если ао < ец < а2., то С называется г]-представлением по неубыванию. Если же ао < а\ < а2 ■ ■., то С называется сильным г]-представлением.

Мнооюество А называется г/-представимым (г}-представимым по неубыванию, сильно г]-представимым), если существует вычислимое ^-представление (соответственно, г]-представление по неубыванию, сильное Г)-представление) множества А.

Обобщаются приведенные ранее результаты Дж. Розенштейна и С. Фелл-нера о сильной 77-представимости £[>- и П^-множеств, что является продвижением описания сильно 77-представимых множеств и, следовательно, степеней в арифметической иерархии. Основным результатом первого параграфа является доказательство следующей теоремы.

Теорема 2.1.3. Пусть А = В и С бесконечное множество, где В € Е® и С € П^. Тогда А сильно г)-представимо. 9

Пусть А = BUC, где В G Е§, С <= П§. Тогда А = СПБ - С-В, то есть дополнение А можно представить в виде разности двух Е^-множеств. Таким образом, имеет место следующее следствие.

Следствие 2.1.8. Если А = А\ — Ач, где Ai Е то существует сильно ■ц-представимое множество В =т А.

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

Теорема 2.2.1. Пусть А € ДЦ. Тогда А®и) множество г]-представимое по неубыванию. Так как А®ш А, каогсдая А^-степень содержит rf-npedcma-вимое по неубыванию множество .

Учитывая результат К. Харриса [18] о существовании Ад-степени, не содержащей сильно 77-представимых множеств, получаем, что существует 77-представимое по неубыванию множество, не имеющее вычислимого сильного 77-представления. Более того, оно не является Т-эквивалентным ни какому сильно 77-представимому множеству. Таким образом, как классы сильно 77-представимых множеств и множеств 77-нредставимых по неубыванию, так и классы соответствующих степеней, различны.

Другим результатом этого параграфа является описание сильно 77-представимых степеней в терминах предельно монотонных псевдовозрастающих на Q функций, что является ответом на вопрос Р. Доуни. А именно, доказана следующая теорема.

Теорема 2.2.11. Если А сильно г]-представимое множество, то существует такая 0'-предельно монотонная псевдовозрастающая на (Q функция Н, что rang(H) =т А.

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

В третьем параграфе продолжается изучение вопроса, частично затронутого в параграфе 1, а именно, уровней в разностной иерархии степеней (реля-тивизованной относительно 0') содержащих сильно ту-представимые множества. В первом параграфе было получено, что каждая степень, содержащая множество уровня 2, содержит сильно ?у-представимое множество. Однако это построение не удается естественным образом продолжить на более высокие уровни. Нами предложена новая конструкция, которая позволяет доказать следующую теорему, которая имеет важные следствия.

Теорема 2.3.7. Пусть h : и х и —> {0, 1} и п : со —> ш такие X-вычислимые функции, что для любого х выполняется неравенство |{s € ш | h(x, s) ^ h(x, s -f 1)}| < n(x).

Тогда существует такая X-предельно монотонная псевдовозрастающая на Q функция F, что rang(F) =т graph(H) ф graph(n), где функция Н определяется равенством Н{х) = lim h(x, s). s—> 00

Если otce n — вычислимая функция, то rang(F) =m graph(H)®graph(n).

Эта теорема дает следующие следствия.

Следствие 2.3.11. Каждое таблично сводящееся к 0" множество т-экви-валентно некоторому сильно 7]-представимому множеству.

В частности, все степени из конечных уровней разностной иерархии Е®-множеств содержат сильно ту-представимые множества.

Следствие 2.3.12. Любая п-в.п. относительно 0' т-степенъ содержит сильно г]-представимое множество.

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

В третьей главе рассматриваются линейные порядки с добавленными предикатами — отношением соседства и блока. Другими словами, такие структуры (Ц <£, вс) и (Ц <£, Ее), где {Ь\ <с) — линейный порядок. Начальный сегмент порядка С с индуцированным отношением соседства или отношением называется начальным сегментом структуры (Ь; <£, ¿х) или (Ц <£, Ее), соответственно. Таким образом, сигнатуры исходной структуры и ее начального сегмента совпадают. Сложность начального сегмента вычислимого линейного порядка может быть очень высокой. Например, согласно результатам Р. Ганди [17] и Дж. Харрисона [19], существует вычислимый линейный порядок с начальным сегментом, изоморфным и>1К — наименьшему неконструктивному ординалу. М. Роу [28] показал, что если отношение соседства в вычислимом линейном порядке вычислимо, то любой П? начальный сегмент имеет вычислимую копию. С другой стороны, им был построен вычислимый линейный порядок с П3 начальным сегментом, не имеющим вычислимой копии. Первый результат М. Роу был обобщен К. Амбос-Шписом, Б. Купером и С. Лемппом [10]. Они доказали, что любой Е® начальный сегмент вычислимого линейного порядка имеет вычислимую копию. Р. Доуни, Р. Коулз и Б. Хусаинов [13] построили вычислимый линейный порядок с П® начальным сегментом, не имеющим вычислимой копии, тем самым получив полное описание начальных сегментов вычислимых линейных порядков, имеющих вычислимую копию.

В первом параграфе третьей главы построены вычислимые структуры

Ь; <£, Бс) и (Ь\ <£, Рс), содержащие П® неконструктивизируемые начальные сегменты. С другой стороны, нетрудно показать, что каждый X® начальный сегмент (Ь\ <£, Б^} или (£-; <£, имеет вычислимую копию, то есть изоморфен некоторому вычислимому линейному порядку с вычислимым отношением соседства или блока, соответственно. Во втором параграфе получено более простое доказательство вышеупомянутого результата Доуни, Коулза и Хусаинова.

Такая постановка вопроса и формулировка результатов не предусматривают ограничений на тип ни самого линейного порядка, ни его начального сегмента, но, фактически, упомянутые начальные сегменты суть 77-схожие линейные порядки. Более того, при несущественных дополнительных условиях они будут 77-представлениями некоторых множеств (однако мы не будем на этом останавливаться). Естественно, что техника построения таких порядков близка к методам и подходам предыдущих глав, и здесь важную роль играют предельно монотонные функции. Итак, в первом параграфе основными являются следующие теоремы.

Теорема 3.1.5. Для любого непустого множества М Е не содержащего 07 существует такой вычислимый линейный порядок £ = И. + ш* с вычислимым предикатом Б с, что Л — г]-схожий и Б (А) = М.

Следствие 3.1.8. Существуют вычислимая структура (Ь; <£, Яс) и П^ начальный сегмент X данной структуры, что X не имеет вычислимой копии.

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

Теорема 3.1.9. Существуют вычислимая структура {Ь\ <£, и начальный сегмент X данной структуры такие, что X не имеет вычислимой копии.

Во втором параграфе основной является следующая теорема.

Теорема 3.2.2. Пусть С = А + ои* — О-вычислимый линейный порядок с О!-вычислимым предикатом соседства Б с- Тогда существует вычислимый линейный порядок С! — В + со* такой, что в (А) = Б (В). Здесь А и В — г]-схожие линейные порядки.

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

Следствие 3.2.7. Существует такой вычислимый порядок С, что £/Рц = 7] и никакая его А^-копия не имеет Д^-вычислимого отношения блока.

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

14 правило из начала алфавита) обозначаются множества. Если А множество, то ха(х) обозначает его характеристическую функцию, а именно:

Если А, В С со, то А (или со—А) и А—В (или А\В) обозначают теоретико-множественные операции дополнения и разности, соответственно. Пусть А © В = {2х \ х £ А} + 1 | х 6 В}. Мощность множества А обозначается через |Л|.

Квантор 3! является сокращенной записью формулы "существует и единственный", то есть для любого предиката Р полагаем (3!:с)[Р(а;)] тогда и только тогда, когда (3x)(Vy)[P(x)Sz((P(y) —> у = я)]. Квантор 3°° является сокращенной записью формулы "существует бесконечно много", то есть, для любого предиката Р, если х е со, полагаем (3°°ж)[Р(ж)] тогда и только тогда, когда (уу)(За; > у)[Р(х)].

Двухместная функция (х, у), определенная как (х, у) := +^х+у для х, у € со и осуществляющая биективное отображение и2 на со, называется канторовской нумерующей функцией. Через I и г обозначаются однозначно определенные функции такие, что для всех х, у £ и, (1(х),г(х)) = х, 1((х, у}) — х,г((х, у}) = у, n-местная функция (xi, ., хп) при п > 2 определяется так: (xi, ., хп) = ((. (xi, хг), %з), •., хп). Если функция ip определена на аргументе х, то пишем ср(х) J., в противном случае пишем (р(х) Область определения функции / обозначается через dom(f) = {х \ f(x) j.}, область ее значений — через rang(f) = {х | (Зг/ € dom(f))[f(y) = ж]}. Положим f(A) = {/(ж) | х G Andom(f)}. Аналогично, для п множеств и функции п аргументов. Если / функция от двух аргументов, то запись /(-, s) обозначает функцию от одного аргумента, получаемую из / подстановкой вместо

О, если х ^ А.

1, если х Е А, второго аргумента фиксированного значения s. Запись х —у обозначает ограниченную разность, а именно, х—у = х — у, если х > у, и х — у = 0, в противном случае. Пусть f : Ахи —> ш, тогда lim f(x, s) определен и конечен, есs—>оо ли существует такое число ах, что (3s0)(Vs > so)[f(x, s) = аж]. В этом случае lim f(x, s) = ах. Не трудно видеть, что если f(x, s) для некоторого х моно

S—>00 тонна по s и ограничена, то существует конечный предел lim /(ж, s). Кроме s—»оо того, liminf/(ж, s) = ах, если (3s0)(Vs > s0)[f(x, s) > ах] и (3°°s)[f(x, s) == ах]. Обозначим / функцию, задаваемую равенством /(ж) = liminf/(ж, s). s—»oo

Пусть Фо,ФьФ2,. — некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций. Множество А сводится по Тьюрингу (или Т-сводится) к множеству В {А <т В), если (Зп)(Ух)[А(х) = Ф^(ж)], где Ф^ — некоторая вычислимая относительно В функция.

Множество А много-одно сводится (или га-сводится) к множеству В (обозначается А <т В), если существует такая вычислимая функция /, что (Уж)[ж <Е А <—► /(ж) Е В].

Множество А принадлежит классу Е^ (или является Е^-множеством) для п > 0, если существует такое вычислимое отношение R(x, у\, у2,., уп), что х е А тогда и только тогда, когда (3yi)(Vy2)(3y3).(Qyn)[R(x, уъ ., уп)], где Q является квантором 3, если п нечетно, и квантором V, если п четно. Множество А принадлежит классу П®, если ш — А принадлежит классу Е°. Множество А принадлежит классу А®, если А е П П®.

Множество А называется n-вычислимо-перечислимым (п-в. п.) множеством (или принадлежит классу Е"1) для некоторого п > 1, если существует такая вычислимая функция / : и х и —> {0,1}, что для каждого х выполняется:

1) /(ж, 0) = 0;

2) Ха{х) = lim f(x,s)) s—»00

3) \{s\f(x, 5)^/(ж,5 + 1)}|<П.

Пусть <r — любая из вышеперечисленных сводимостей, тогда <г является рефлексивным и транзитивным отношением, поэтому для каждой такой сводимости можно определить отношение эквивалентности множеств относительно этой сводимости: говорим, что множества А и В г-эквивалентны (А =г В), если А <г В и В <г А. Для каждого множества А определим его r-степень: degr(A) = {В С и | В =г А}.

Степень а называется n-вычислимо-перечислимой степенью для n > 1, если она содержит п-в. п. множество, и она называется собственно п-в. п. степенью, если она содержит п-в. п. множество, но не содержит т-в. п. множеств для т < п.

Линейный порядок С — это алгебраическая система (L; <с) с одним бинарными отношением, обладающим свойствами антирефлексивности, антисимметричности, транзитивности и для любых ж, у Е L либо х <с У, либо у <£ х (где, х <су^ х = у V х <су). Если С — (L; — линейный порядок, то С* определяется следующим образом £* — (L;<£*), где (Va;)(\/у)[ж <£* у <—> у <с х]. Линейный порядок (М; <м) называется под-порядком (Ц <с), если М С L и (Ух € M)(V?/ € М)[х <м У *—> % <с у]-В этом случае также будем писать Л4 = (М; <с)- Замкнутым интервалом в линейном порядке С с концами хну называется множество [ж, у]с = {z € L | х <с z <с у}. Открытым интервалом в линейном порядке £ с концами х и у называется множество (х, у)с — {z 6 L | х <£ z <ц у]. Интервал относительно естественного порядка на и обозначается [ж, у]. Множество R С L называется сегментом линейного порядка если (Vx)(Vy)(Vz)[(x <с z <с укх € Rky е R)—

Линейные порядки С = (L; <с) и М = (М; <м) называются изоморфными (£ = Л4), если существует такая биекция ip : L —> М, что (Va; 6 L)(\fy € L)[x <с у ^ ip(x) <м <р(у)]- Если два линейных порядка изоморфны, будем говорить, что они имеют одинаковый порядковый тип.

Стандартное отношение порядка на и) обозначается "<". Символами 14 и (1^ будем обозначать множество натуральных и множество рациональных чисел, соответственно, а также, для удобства, естественные линейные порядки на них определенные. Кроме множества неотрицательных целых чисел, символ со, также обозначает естественный линейный порядок на нем и тип этого порядка. Каждый раз из контекста будет ясно о чем идет речь. Тип рациональных чисел обозначается г], тип целых чисел —

Пусть М. = (М; <м) и £г = (£>г> <с{) € М) — линейные порядки. Предположим, что Ьг П М = 0 (г £ М) и Ьг П = 0 для любых г ф з г, 2 ^ М), тогда определен линейный порядок С — ]Г) где Ь — и Ь{, гем ¿ем а отношение "<£" задается следующим образом: если х Е Ьг, у Е Ь^, то х <£ у тогда и только тогда, когда (г <м з) V (г = г/). Если £7 = то по определению £.М = А- Вообще говоря, умножение гем определено не однозначно для данных линейных порядков С, Л4 и зависит от выбора последовательности £{. Однако, не трудно видеть, что если = С! ^ и М = М', то С,г = и) следовательно, если С = /У и Л4 = гбМ гбМ' то = СМ.'. Таким образом, эти две операции корректно и однозначно определены для порядковых типов.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Зубков, Максим Витальевич, 2009 год

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

2. Арсланов М. М. Иерархия Ершова. Спецкурс для студентов мехмата. -Казань: Казанский государственный университет. 2007. - 86 с.

3. Ершов Ю. JI. Об одной иерархии множеств, I // Алгебра и Логика. -1968. Т. 7. - №3. - С. 47-75.

4. Ершов Ю. JI. Об одной иерархии множеств, II // Алгебра и Логика. -1968. Т. 7. -т. - С. 15-48.

5. Ершов Ю. Л. Об одной иерархии множеств, III // Алгебра и Логика.- 1970. Т. 9. - т. - С. 34-52.

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

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

8. Фролов А. Н. ДЦ копии линейных порядоков // Алгебра и логика. — 2006.- Т. 45. С. 354-370.

9. Хисамиев Н. Г. Критерий конструктивизируемости прямой суммы циклических р-групп // Изв. АН Каз. ССР., сер. физ.-мат. 1981. - Т. 98. -т.- С. 51-55.

10. Ambos-Spies К., Cooper S. В., Lempp S. Initial segments of recursive linear orders // Order. 1997. - V. 14. - P. 101-105.

11. Ash C. J., Jockusch C. G., Knight J. F. Jumps of orderings// Trans. AMS. 1990. - V. 319. - P. 573-599.

12. Csima B. F., Hirshfeldt D. R., Knight J. F., Soare R. I. Bounding prime models // Journal of Symbolic Logic. 2004. - V. 69 - №4. - P. 1117-1142.

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

14. Downey R. G. Computability theory and linear orderings // Handbook of computable algebra. Amsterdam: Elsevier. - 1998. - V. 2. - P. 823-976.

15. Feiner L. J. Hierarchies of Boolean algebras // Journal of Symbolic Logic. -1970. V. 35. - P. 365-374.

16. Fellner S. Recursive and Finite Axiomatizability of Linear Orderings // Ph.D. Thesis. Rutgers Univsity. - 1976.

17. Gandy R. O. General recursive of finite type and hierarchies of functions // Ann. Fac. Sci. Univ. Clemmont-Ferrand. 1967. - V. 35. - P. 5-24.

18. Harris K. r]-Represetation of Sets and Degrees // Journal of Symbolic Logic- 2008. V. 73. - P. 1097-1121.

19. Harrison J. Recursive pseudo-well orderings // Trans. AMS. 1968. -V. 131.- P. 526-543.

20. Hirshfeldt D., Miller R., Podzorov S. Order-computable sets // Notre Dam Journal of Formal Logic. 2007. - V. 48. - №3. - P. 317-347.

21. Kach A. M. Computable shuffle sums of ordinals // Archive for Mathematical Logic. 2008. - V. 47. - №3. - P. 211-219.

22. Kach A. M., Turetsky D. Limitwise Monotonic Functions, Sets and Degrees on Computable Domaine // Journal of Symbolic Logic, принято к печати.

23. Khoussainov В., Nies A., Shore R. Computable models of theories with few models // Notre Dam Journal of Formal Logic. 1997. - V.38. - №2. -P. 165-178.

24. Khisamiev N. G. Constructive abelian groups // Handbook of computable algebra. Amsterdam: Elsevier, 1998. - V. 2. - P. 1177-1231.

25. Lerman M. On recursive linear orderings // Lecture Notes in Mathematics.- Berlin: Springer-Verlag. 1981. - V. 859. - P. 132-142.

26. Lerman M., Rosenstein J. G. Recursive linear orderings // Stud. Logic Found. Math. 1982. - V. 109. - P. 132-142.

27. Odifreddi P. Classical recursion theory. Amsterdam: North-Holland. - 1989.- 610 P.

28. Raw M. J. S. Complexity of automorphisms of recursive lienar orders. -Ph. D. Thesis. University of Wisconsin-Madison. - 1995.

29. Rice H. G. Recursive and recursively enumerable orders // Trans. AMS. -1956. V. 83. - P. 713-746.

30. Richter L. J. Degrees of Unsolvability of Models. Ph.D. Thesis. - Urbana: University of Illinois at Urbana-Champaing. - 1997.

31. Rosenstein J. Linear orderings. New York: Academic Press. - 1982. - 487 P.

32. Watnik R. A generalization of Tennenbaum's Theorem on effectively finite recursive linear orderings // Journal of Symbolic Logic. 1966. - V. 31. -P. 159-168.

33. Зубков М. В. Сильно т]-представимые множества // Труды математического центра им. Н. И. Лобачевского. 2006. - Т. 34. - с. 111-112.

34. Zubkov М. V. Strongly rj-representable sets // Bulletin of Symbolic Logic. -2007. V. 13. - P. 292-293.

35. Zubkov M. On eta-representable sets // Bulletin of Symbolic Logic. 2009. - V.15. - P. 131.

36. Зубков M. В. Одна теорема о сильно rj-представимых множествах // Известия вузов. Математика. 2009. - №7 - с. 77-81.

37. Frolov A. N., Zubkov М. V. Increasing rj-representable degrees // Mathematical Logic Quarterly. 2009. - V. 55. - №6. - P. 561-564.

38. Зубков M. В. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами // Алгебра и логика, принято к печати.