Верхние полурешётки арифметических нумераций и арифметических m-степеней

• Автор: Подзоров, Сергей Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 112 с.

Содержание

1 Определения и обозначения

1.1 Общие понятия теории вычислимости

1.2 Дистрибутивные полурешётки и предполурешётки .

1.3 Представления дистрибутивных полурешёток

1.4 77?-сводимость и то-степени

1.5 Нумерации

1.6 Каркасы и башни

2 Представления дистрибутивных полурешёток

2.1 Классы Г22,„+з п

2.2 Классы Лз>п и Пг.п+з

2.3 Конструктивные дистрибутивные решётки
2.4 Позитивные частичные порядки
2.5 Классы Пг.п и заключительные замечания
3 Полурешётки 7тг-степеней
3.1 Характеризация главных идеалов полурешётки
арифметических т-степеней
3.2 Доказательство теоремы 3.1.2 для случая п > 0 . .
3.3 Универсальные полурешётки
4 Полурешётки арифметических нумераций
4.1 Главные идеапы полурешёток Роджерса
4.2 Накрытия в полурешётках Роджерса

Введение
Диссертация содержит ряд результатов, касающихся таких объектов теории вычислимости, как m-степени и иолурешётки нумераций. Эти два понятия тесно переплетаются между собой. С одной стороны, 777-степени являются, по сути, частным случаем нумераций (нумерации двухэлементного множества). С другой стороны, значительная часть изложенных в этой диссертации результатов показывает, что методы, используемые при изучении ??7-степеней, могут с успехом применяться для изучения строения полурешёток арифметических нумераций. Более того, ряд теорем из четвёртой главы дают возможность установить изоморфизм между полурешёткамн 771-степеней и идеалами полурешёток нумераций, что позволяет сделать утверждение о большой степени схожести локального строения этих двух типов объектов.
Много-одно-еводимость и /»-степени являются традиционными объектами теории вычислимости. Впервые эти понятия были введены Постом в середине -10-ых годов XX столетия и с тех пор привлекали внимание многих исследователей. В той или иной степени эти понятия освещаются во всех солидных монографиях но теории вычислимости. Результаты, касающиеся ш-степеней, появлялись в сотнях публикаций, выходивших па протяжении десятилетий. Среди них можно выделить следующие четыре основных достижения:
1. В 1972 году Лахлан описал типы изоморфизма главных идеалов полурешётки вычислимо перечислимых ш-степеней;
2. В 1975 Ершов и Палютин дали описание иолурешётки всех т-степеней с точностью до изоморфизма в терминах с-универсальных полурешёток;
3. В 1978 Денисов дал характеризацию типа изоморфизма полурешётки всех вычислимо перечислимых ш-степеней;
4. В 1980 Нероуд и Шор показали, что теория первого порядка по-лурешётки ш-степеней вычислимо изоморфна арифметике второго порядка.
Работы, содержащие результаты из первого и третьего пунктов этого списка, дали основной толчок к части исследований автора, представленных во второй и третьей главах этой диссертации.

Характеризации типов изоморфизма, полученные Лахланом и Денисовым, существенно опирались на понятие лахлановской полурешётки. Это понятие имеет довольно сложное определение, состоящее из многих пунктов. В связи с этим с конца 1970-х годов внимание исследователей привлекал вопрос о том, возможно ли описать класс лахлановских полурешёток более коротким и '’естественным” способом. С одной стороны. легко заметить, что каждая л ахл айовская полу решётка представляет из себя ограниченную дистрибутивную полуретётку, имеющую £3-представление. С другой стороны, было сразу замечено, что для таких естественных классов ограниченных дистрибутивных полурешёток с £3-представлениями, как решётки и конструктивные полурешётки, справедливо обратное и все полурешётки из этих классов являются лахла-новскими. В связи с этими наблюдениями возникла естественная гипотеза о том, что лахлановскмн полурешетки — это, в точности, ограниченные дистрибутивные полурешётки с ^-представлениями. Вопрос о том, верна ли гипотеза, долгое время оставался открытым.
Во второй главе настоящей диссертации автор доказывает эту гипотезу и даёт положительный ответ на этот вопрос. Более того, устанавливается, что каждое ^-представление полурешётки сводится к некоторому лахлановскому представлению и, значит, в конструкциях, использующих технику Лахлана и Денисова, можно оперировать с £з-представ-ленпями полурешёток вместо лахлановских представлений. Результат обобщается на полурешётки с любыми арифметическими представлениями; кроме того, исследуется ряд представлений, близких к двум указанным.
Другой естественный вопрос, вставший перед автором после прочтения работы Лахлана, заключался в возможности обобщения результата Лахлана на произвольные уровни арифметической иерархии. Раз главными идеалами т-степеней в классе ^-множеств оказались в точности ограниченные дистрибутивные полурешётки с £з-представлениями, то логично было предположить, что главными идеалами т-степеней в классе £^+1-множеств являются в точности ограниченные дистрибутивные полурешётки, имеющие £®+з-представлсние. В связи с полученными чуть ранее результатами о главных идеалах полурешёток Роджерса арифметических нумераций этот вопрос приобрёл важное прикладное значение. Положительный ответ на него даётся в третьей главе.
Соответствующая теорема третьей главы доказана в усиленной форме: для каждой полурешётки с £®+3-представлением строится главный идеал, порождающее множество которого обладает дополнительным свойством гипериммунности. Усиление требуется для дальнейших при-

2. для а еТі ірг+1 (а,(а)) = іРі(а):
3. (Ті , : Vі, Лг) — дистрибутивная предрегиётка с наименьшим эле-
ментом <*о,г (A)(0)) и наибольшим элементом ao,i (A)(1))/
4- для а, 6 € Ті из а Ъ следует <т*(а) c*i(b) и аі(а Vі b) ^[+l at(a) Vz+1 di{b);
5. для a, b Є Ті vitj(a) Kj ai,j(b);
где и (pi — ограничения на Ті отношения ^ и функции <р соответственно, а для а,Ь Є Ті запись a =J h означает, что а bub а.
Доказательство. Пусть их ^ vy <=ï 3uRf(x,y,v), где R' — вычислимый предикат. Можно считать, что R'(x, х, 0), І?'(0, х, 0) и R’{x, 1,0) для всех
х G N. Зададим предикаты Ru Е при помощи следующих эквивалентностей: R{x.y, и) <=> (3v < u)R'(x,y,v) и Е(х,у,и) <=> R(x,y,u) Sz R(y, .г, и).
Будем по шагам определять отношение ^Т и функцию (р, задавая на шаге t их части и (pt. Попутно будем определять последовательность натуральных чисел По < п < ..базовую (см. параграф 1.3) последовательность КОНеЧНЫХ ДИСТрибутИВНЫХ ПреДрешётОК {T>i = {Dl, и
последовательность функций {щ : задавая на шаге t чис-
ло щ, предрешётку T>t и функцию щ. Определённые на тнаге t объекты будут обладать следующими свойствами: (pt(Tt) С A, p>t индуцирует решёточный гомоморфизм Tt в T>t, щ представляет операцию взятия точной верхней грани на А, для а,Ь Є Tt а b <=> <£г(а) Шаг 0. Полагаем Dq = {0,1}, но(0,0) = 0 и по(0,1) = ио(1,0) = мо(1,1) = 1. Выберем число ?2о так> чтобы для всех х,у Є Dq было выполнено
Е(и(х, у),ио(х: у), По). Пусть Х У & Щ%,У,по) ДЛЯ любых х,у є Dq. Полагаем щ равным единственному отображению из То в Dq, такому что <£0 (A)(0)) = 0, (ро (A)(1)) = 1 и ip о является решёточным гомоморфизмом 7о в Д). Наконец, зададим при помощи эквивалентности а ь ** ¥>о(<0 То{Ь)-
Шаг t + 1. Ищем число п > nt, конечное подмножество натурального ряда D D Dt U Qt+i и функцию и' : D2 —> D, такие что для отношения
на D, задаваемого эквивалентностью х у <=> R{x,y,n), V = (D,
; и') — дистрибутивная предрешётка, для всех х,у Є Dt Е(щ(х, у), и'(х, у),