Содержание
1 Определения и обозначения 1
1.1 Общие понятия теории вычислимости............... 1
1.2 Дистрибутивные нолуретттётки и предполурешётки . 2
1.3 Представления дистрибутивных полурешёток .... 7
1.4 777-СВОДИМОСТЬ и га-стенеии..................... 9
1.5 Нумерации....................................... 14
1.6 Каркасы и башни................................. 18
2 Представления дистрибутивных полурешёток 28
2.1 Классы Пг.п+з н Л1,„............................ 28
2.2 Классы Аз,п и Пг.гн-з........................... 34
2.3 Конструктивные дистрибутивные решётки........... 35
2.4 Позитивные частичные порядки ...................... 39
2.5 Классы П3|П. П2,п и заключительные замечания ... 43
3 Пол у решётки т-стененей 45
3.1 Характеризация главных идеалов полурешётки
арифметических т-степенсй.......................... 45
3.2 Доказательство теоремы 3.1.2 для случая п > 0 . . 40
3.3 Универсальные полурешётки....................... 58
4 Полу решётки арифметических нумераций 89
4.1 Главные идеалы полурешёток Роджерса............. 89
4.2 Накрытия в полу решётках Роджерса............... 97
V
Введение
Диссертация содержит ряд результатом, касающихся таких объектом теории вычислимости, как m-степени и полурешётки нумераций. Эти два понятия тесно переплетаются между собой. С ОДНОЙ СТО]ЮИЫ, т-егспе-ни являются, по сути, частным случаем нумераций (нумерации двухэлементного множества). С другой с то j юны, значительная часть изложенных в этой диссертации результатов показывает, что методы, используемые при изучении ш-степеней, могут с успехом применяться для изучения строения полурешёток арифметических нумераций. Более того, ряд теорем из четвёртой главы даю т возможность установить изоморфизм между нолурешёткамп гл-степеней и идеалами полурешёток нумераций, что позволяет сделать утверждение о большой степени схожести локального строения этих двух типов объектов.
Много-одно-своднмсхть и /н-етеисни являются традиционными объектами теории вычисли мости. Впервые эти понятия были введены Постом в середине Ю-ых годов XX столетия и с тех пор привлекали внимание многих исследователей. В той или иной степени эти понятия освещаются во всех солидных монографиях по теории вычислимости. Результаты, касающиеся /«-степеней, появлялись в сотнях публикаций, выходивших на протяжении десятилетий. Среди них можно выделить следующие четыре основных достижения:
1. В 1972 году Л ах л ян описал типы изоморфизма главных идеалов полурешётки вычислимо перечислимых т-степеней;
2. В 1975 Ершов и Палютин дали описание полурешётки всех /«-степеней с точностью до изоморфизма в терминах с-универсальных полурешёток;
3. В 1978 Денисов дал характеризацию типа изоморфизма полурешётки Всех ВЫЧИСЛИМО НереЧИСЛИМЫХ 7И-СТСНСНСЙ;
1. В 1980 Нероуд и Шор показали, что теория первого порядка полурешётки m-степеисй вычислимо изоморфна арифметике второго порядка.
Работы, содержащие результаты из первого и третьего пунктов этого списка, дали основной толчок к части исследований автора, представленных во второй и третьей главах этой диссертации.
3
Характеризации типов изоморфизма, полученные Лахланом и Денисовым. существенно опирались на понятие лахланонской полурешётки. Это понятие имеет довольно сложное определение, состоящее из многих пунктов. В связи с этим с конца 1970-х годов внимание исследователей привлекал вон {юс о том, иозможно ли описать класс лахлановских иолурешеток более К01ЮТКИМ и ''естественным" способом. С одной стороны. легко заметить, что каждая лахлановская иолурешётка представляет из себя ограниченную дистрибутивную иолурешётку, имеющую Е3-представлеиие. С другой стороны, было сразу замечено, что для таких естественных классов ограниченных дистрибутивных иолурешёток с Ед-представлсниями, как решётки и конструктивные полурешётки, справедливо обратное и все полуретпетки из этих классов являются лахла-иовскими. В связи с этими наблюдениями возникла естественная гипотеза о том, что лахлановекми полурешетки — это, в точности, ограниченные дистрибутивные полурешётки с ЕЦ-нредстанлеииями. Вопрос о том, верна ли гипотеза, долгое время оставался открытым.
Во второй главе настоящей диссертации автор доказывает эту гипотезу и даёт положительный ответ на этот вопрос. Более того, устанавливается, что каждое Ез-представление полурешётки сводится к некоторому лахлановскому представлению и, значит, в конструкциях, использующих технику Лахллна и Денисова, можно оперировать с Е3-представ-лениями пол у решеток вместо лахлановских представлений. Результат обобщается на полурешётки с любыми арифметическими представлениями; кроме того, исследуется ряд представлений, близких к двум указанным.
Другой естественный вопрос, вставший перед автором после прочтения работы Лахллна, заключался в возможности обобщения результата Лахлаиа на произвольные уровни арифметической иерархии. Раз главными идеалами т-стененей в классе Е1)-множеств оказались в точности ограниченные дистрибутивные полурешётки с Ед-представлениями, 'го логично было предположить, что главными идеалами т-степеней в классе Е^+1-множеств являются в точности ограниченные дистрибутивные полурешетки, имеющие Е^+3-представлсиие. В связи с полученными чуть ранее результатами о главных идеалах иолурешёток Роджерса арифметических нумераций этот вопрос приобрёл важное прикладное значение. Положительный отпо.т на него дастся в третьей главе.
Соответствующая теорема третьей главы доказала в усиленной форме: для каждой полурешётки с Е° .^-представлением строится главный идеал, порождающее множество которого обладает дополнительным свойством гинернммунности. Усиление требуется для дальнейших при-
У
ложен и К н теории нумераций, однако сама возможность такого усиления и алела автора на ряд мыслей, приведших к результатам третьего параграфа третьей главы. Легко заметить, что простые и гипсрпростые т-степени (то есть т-степени, содержащие простое (гипсрпростое) либо вычислимое множество) образуют идеалы н полурешётке вычислимо перечислимых ШгстепенеП В связи с возможностью усиления оказывается, что эти идеалы локально изоморфны нолурегаётке вычислимо перечислимых т-степенсй без наибольшего элемента и полурешётке О'-вычислимых т-степенеи. Буду г ли упомянутые иолурешетки просто нзомор<}>-пы? Последний наріїграф третьей главы (технически наиболее сложный и занимающий наибольший объём но сравнению с другими параграфами) даёт положительный ответ па этот вопрос.
Что касается нумераций, то интересующие нас 2^.,-вычислимые нумерации подразделяются на "классический" случай п = 0 и "иекласси-ческнй” случай п > 0. "Классический” случай изучался начиная с 60-ых годов XX столетия; по нему вышли десятки статей и монография Ю. Л. Ершова. "Нек л логический” случай привлёк внимание исследователей в середине 90-ых годов XX столетия.
Первые исследования различных авторов, изучавших иолурешетки Роджерса 2^ р вы числимых нумераций в неклассическом случае, касались их локального строения. Довольно быстро было доказано, что каждая нетривиальная полурешётка нз этого класса имеет бесконечно много минимальных элементов, однако после этого дело застопорилось. Долгое время не удавалось доказать даже существование безатомных элементов в общем случае.
Автор диссертации в одной из своих первых статей по теории нумераций решил этот вопрос. Попутно им было доказано, что и любую нетривиальную ’Ъеклассическую” полурешётку Яп+2(-^) в качестве идеала можно вложить главный идеал т-степеней, порождённый иммунным Д?1+2-множеством. После этого возник вполне закономерный иите-1>ес к /п-степеням и па протяжении нескольких лет активно изучались вопросы их локального строения. Однако после того, как эти работы были завершены, они тут же нашли непосредственное применение в теории нумераций. Следствием основных теорем, доказанных во второй, третьей и первом параграфе четвертой главы, стал следующий результат: каждая нетривиальная полурешётка содержит идеал, изоморфный
произвольной ограниченной дистрибутивной полурешётке с +з“пред-
ставлением. Следствием этого стали, в свою очере.дь, полученная автором локальный характеризация полурошёток Для конечных
семейств Т и утверждение о том, что все нетривиальные полурешёткн
Г
и ^т-кг(^) при т > п + 2 не изоморфны (что значительно усиливало результаты, полученные ранее в нескольких работах других авторов).
Последний параграф четвёртой главы посвящен вопросам о минимальных накрытиях и, в частности, вопросу о предельности наибольшего элемента, в иолурсптстках которые также активно изу-
чались. Были достигнуты значительные успехи, получен ряд довольно сильных достаточных условий. Полностью вопросы о минимальных накрытиях и о предельности были решены для полу решёток 72^2 (.^), у которых Т конечно или имеет наименьший но включению элемент.
Автор выражает глубокую признательность: Сергею Савостьяновичу Гончарову за всестороннюю помощь и поддержку, а также за постановку задач, инициировавших представленные здесь исследования; Юрию Леонидовичу Ершову за ряд ценных идей, которые помогли ему в доказательстве полученных результатов; Серикжану Агыбаевичу Бадаеву и Андреа Сорби, помогавшим автору в создании плодотворной рабочей обстановки и проявлявшим инте|кч: к обсуждаемым здесь проблемам. Отдельную благодарность автор выражает Виталию Геннадьевичу Ше-лпховскому за всестороннюю помощь и интерес, проявленный к работе.
1 Определения и обозначения
1.1 Общие понятия теории вычислимости
Основные понятия теории вычислимости (вычислимая функция, вычислимо перечислимое множество, арифметическая иерархия, скачок, простота, креативность и т. и.) и теории конструктивных моделей можно найти в книгах (19, 30, 31]. Мы предполагаем, что читателю известны содержащиеся в этих книгах базовые определения, связанные с ними классические результаты, а также стандартные обозначения. Ниже мы введём лишь то, что способно вызвать непонимание либо непосредственно связано с узкой темой настоящей работы.
Множество всех натуральных чисел мы обозначаем стандартным символом N и считаем, что натуральный ряд начинается с нуля, то есть
N = {0,1,2,...}.
Если X - произвольное множество, то Р(ЛГ) обозначает множество всех подмножеств множества Л'. Мощность множества X обозначаем |Л'(. Для произвольных множеств X. У через X СУ обозначается включение X в У. а через Л С У — строгое включение (подразумевающее наличие н У элементов, не принадлежащих .V).
Термин тючтпи Ома всех, означает ’для всех, за исключением конечного числа”.
Иод функцией из X и У мы понимаем отображение первого множества во второе, определённое на всех элементах X. В случае, когда допускается неопределенность на некоторых аргументах, мы употребляем термин частинная функция. Если / — частичная функция, то через 5/ мы обозначаем сё область определения, а через р/ — область значений.
В качестве аргументов и значений вычислимых функций мы допускаем произвольные объекты, имеющие конструктивное задание. При желании каждая ’’однородная” совокупность таких объектов может быть снабжена некоторой гёделевской нумерацией, позволяющей отождествлять сами объекты с натуральными числами. Однако эти нумерации о явном виде нигде не употребляются, хотя, возможно, в отдельных местах можно усмотреть намёк на их использование.
Стандартную вычислимую биекцию № на N мы обозначаем с(х, у), а обратные к пей функции — /(г) и г(х) (с(£(х),г(х)) = х для всех х Є Г^). Мы считаем, что с(х,у) возрастает цо обоим аргументам.
Через 6і(х) мы обозначаем 2-х местную частично вычислимую функцию, универсальную для класса всех частично вычислимых функций из N п N. Для определённости можно считать, что — функция, вычисли-
мая на машине Тьюринга с гёделевским номером і. Запись 0$(х) означает конечный фрагмент этой функции; значение 0*(х) определено, если х ^ I и 0.(х) вычислимо па машине с номером і не более чем за I шагов.
Запись обозначает универсальную вычислимую последова-
тельность всех вычислимо перечислимых подмножеств М, а IV/ — ’’конечная часть” множества IV,, состоящая из перечисленных за £ шагов элементов в некоей равномерной но і процедуре перечисления. Опять же для определённости можно положить — <50, и IV/ — 60*, хотя конкретно этот выбор не столь пршіцнпнаїен.
Последовательность конечных подмножеств N мы называем сильно вычислимая, если равномерно по номеру множества из этой последовательности можно за конечное время установить количество его элементов и выписать их полный список. Другими словами, если по номеру множества можно эффективно найти канонический индекс этого множества, определенный в [30]. Термин вычислимая последовательность зарезервирован д:я случая, когда но номеру множества можно лишь запустить процедуру его перечисления, причем наличие эффективной оценки для количества тагов этого перечисления не подразумевается. Другими словами, этот термин зарезервирован для случая, когда последовательность удовлетворяет классическому определению вычислимой нумерации. Через {Ріи,,},,^« обозначем сильно вычислимую последовательность всех конечных подмножеств N.
Через £ обозначается совокупность всех вычислимо перечислимых подмножеств натурального ряда, которая часто рассматривается как дистрибутивная решётка с теорстнко-мпожсствспнымп операциями объединения и пересечения. Символ £* обозначает фактор этой решётки по модулю конечных множеств. Запись А =* В означает равенство множеств А и В и о модулю конечных множеств, А С* В — включение по модулю конечных множеств.
Под эквивалентностью, если не оговорено противное, обычно понимается отношение эквивалентности на N. Если и С N и є — эквивалентность, то запись [и)£ обозначает множество {х Є N : (Зт< 6 £/)((«,я) Є с}. Мы говорим, что є согласована с [/, если [і/]£ = Сг, то есть если классы эквивален тности £ либо целиком состоят из элементов и, либо не имеют С и общих элементов.
1.2 Дистрибутивные полуретттётки и предполурешётки
Относительно общих понятий, касающихся решеток и полурешеток, мы придерживаемся общепринятых соглашений, принятых в монографії-
ях (16, 23]. Так, решёткой мы называем частично упорядоченное множество с бинарными операциями взятия супремума (объединения) и ии-фимума (пересечения). Эти операции мы, как правила обозначаем V и А. возможно, с индексами, указывающими на то, в какой структуре рассматриваются эти операции. Верхняя полурешапка — это частично упорядоченной множество с единственной бинарной операцией супремума (объединения). В дальнейшем верхние иолурешётки мы часто называем просто полуретстками, поскольку нижние полурешётки })ассма гривач ьей не будут.
Понятие дистрибутивной решётки хорошо известно (16| и мы предполагаем, что читатель с ним знаком. Это понятие распространяется также на полурешетки. Верхняя помурешёгкд {£, <; V) называется дистрибутивной, если для любых а, Ь, с € I, таких что а ^ Ь V е, существуют элементы </, е € Ь, для которых д ^ 0, е^сиая й V г.
Ь V с
(її 1е
Известно [16, 23]. что произвольная решётка дистрибутивна как решётка тогда н только тогда, когда она дистрибутивна как верхняя і юлу решётка (э тим, в частности, оправдывается термин ’’дистрибутивность” в применении к системе с одной операцией). Кроме того, известно [16, 23|, что для произвольной верхней полурешётки С = <£, V) следующие 4 условия эквивалентны.
1. С дистрибутивна;
2. для любого конечного Р С Ь существует конечное множество Ст, такое что Р С С С Ь. (7 замкнуто относительно операции объединения и является дистрибутивной решеткой (с теми же порядком и объединениями, что и в С).
3. £ изоморфна прямому пределу семейства конечных дистрибутивных решёток, рассматриваемых как верхние иолурешётки (то есть гомоморфизмы, фигурирующие в определении прямого предела, сохраняют объединения, но могут не сохранять пересечения);
4. множество (непустых) идеалов иолурешётки £, рассматриваемое относительно включения, является дистрибутивной решёткой.
- Киев+380960830922