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

Диссертация содержит ряд результатов, касающихся таких объектов теории вычислимости, как т-степени и полурешётки нумераций. Эти два понятия тесно переплетаются между собой. С одной стороны, 777-сгепс-ни являются, по с. ути, частным случаем нумераций (нумерации двухэлементного множества). С другой стороны, значительная часть изложенных в этой диссертации результатов показывает, что методы, используемые при изучении 777-стспенсй, могут с успехом применяться для изучения строения полурешёток арифметических нумераций. Более того, ряд теорем из четвёртой главы дают возможность установить изоморфизм между полурешётками 771-степеней и идеалами полурешёток нумераций, что позволяет сделать утверждение о большой степени схожести локального строения этих двух типов объектов.

Много-одно-своднмость и /"-степени являются традиционными объектами теории вычислимости. Впервые эти понятия были введены Постом в середине 10-ых годов XX столетия и с тех пор привлекали внимание многих исследователей. В той или иной степени эти понятия освещаются во всех солидных монографиях по теории вычислимости. Результаты, касающиеся т-степеней, появлялись в сотнях публикаций, выходивших на протяжении десятилетий. Среди них можно выделить следующие четыре основных достижения:

1. В 1972 году Лахлан описал типы изоморфизма главных идеалов полурешётки вычислимо перечислимых т-степеней;

2. В 1975 Ершов и Палютин дали описание полурешётки всех т-степеней с точностью до изоморфизма в терминах с-универсальных полурешёток;

3. В 1978 Денисов дал характеризацию типа изоморфизма полурешётки всех вычислимо перечислимых т-степеней;

4. В 1980 Нероуд и Шор показали, что теория первого порядка ио-лурешётки т-степеней вычислимо изоморфна арифметике второго порядка.

Работы, содержащие результаты из первого и третьего пунктов этого списка, дали основной толчок к части исследований автора, представленных во второй и третьей главах этой диссертации. 3.

Характеризации типов изоморфизма, полученные Лахланом и Денисовым, существенно опирались на понятие лахлановекой полурешётки. Это понятие имеет довольно сложное определение, состоящее из многих пунктов. В связи с этим с конца 1970;х годов внимание исследователей привлекал вопрос о том, возможно ли описать класс лахлановских полурешёток более коротким и ''естественным" способом. С одной стороны. легко заметить, что каждая лахлановская полурешётка представляет из себя ограниченную дистрибутивную полурешётку, имеющую представление. С другой стороны, было сразу замечено, что для таких естественных классов ограниченных дистрибутивных полурешёток с Ео-представлениями, как решётки и конструктивные полурешётки, справедливо обратное и все полурешётки из этих классов являются лахла-новскими. В связи с этими наблюдениями возникла естественная гипотеза о том, что лахлановекмн полурешётки — это, в точности, ограниченные дистрибутивные полурешётки с^{-представлениями.} Вопрос о том, верна ли гипотеза, долгое время оставался открытым.

Во второй главе настоящей диссертации автор доказывает эту гипотезу и даёт положительный ответ на этот вопрос. Более того, устанавливается, что каждое Ез-представление полурешётки сводится к некоторому лахлановскому представлению и, значит, в конструкциях, использующих технику Лахлана и Денисова, можно оперировать с Ез-представ-лениями полурешёток вместо лахлановских представлений. Результат обобщается на нолурешётки с любыми арифметическими представлениямикроме того, исследуется ряд представлений, близких к двум указанным.

Другой естественный вопрос, вставший перед автором после прочтения работы Лахлана, заключался в возможности обобщения результата Лахлана на произвольные уровни арифметической иерархии. Раз главными идеалами ш-степеней в классе Ермпожеств оказались в точности ограниченные дистрибутивные полурешётки с Ез-представлениями, то логично было предположить, что главными идеалами т-степеней в классе Е^+1-множеств являются в точности ограниченные дистрибутивные полурешётки, имеющие^{-представление.} В свяли с полученными чуть ранее результатами о главных идеалах полурешёток Роджерса арифметических нумерации этот вопрос приобрёл важное прикладное значение. Положительный ответ на него даётся в третьей главе.

Соответствующая теорема третьей главы доказана в усиленной форме: для каждой полурешётки с Е°+3-представлением строится главный идеал, порождающее множество которого обладает дополнительным свойством гипериммунности. Усиление требуется для дальнейших приложений в теории нумераций, однако сама возможность такого усиления напела автора на ряд мыслей, приведших к результатам третьего параграфа третьей главы. Легко заметить, что простые и гиперпростые ш-степени (то есть т-стспени, содержащие простое (гиперпростое) либо вычислимое множество) образуют идеалы в полурешётке вычислимо перечислимых т-степеней В связи с возможностью усиления оказывается, что эти идеалы локально изоморфны полурешётке вычислимо перечислимых т-степеней без наибольшего элемента п нолуретётке О'-вычпс-лимых т-степеней. Буду г ли упомянутые полурешётки просто изоморфны? Последний параграф третьей главы (технически наиболее сложный и занимающий наибольший объём по сравнению с другими параграфами) даёт положительный ответ на этот вопрос.

Что касается нумераций, то интересующие нас + (-вычислимые нумерации подразделяются на «классический» случай п = 0и «неклассический» случай п > 0. «Классический» случай изучался начиная с 60-ых годов XX столетияпо нему вышли десятки статей и монография Ю. Л. Ершова. «Неклаееттческий» случай привлёк внимание исследователей в середине 90-ых годов XX столетия.

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

Автор диссертации в одной из своих первых статей по теории нумераций решил этот вопрос. Попутно им было доказано, что в любую нетривиальную «неклассическую» полурешётку в качестве идеала можно вложить главный идеал т-степеней, порождённый иммунным Д°+2~множествомПосле этого возник вполне закономерный интерес к ///-степеням и на протяжении нескольких лет активно изучались вопросы их локального строения. Однако после того, как эти работы были завершены, они тут же нашли непосредственное применение Iтеории нумераций. Следствием основных теорем, доказанных во второй, третьей и нервом параграфе четвертой главы, стал следующий результат: каждая нетривиальная полурешётка 72.^+2[У7) содержит идеал, изоморфный произвольной ограниченной дистрибутивной полурешётке с^{-представлением.} Следствием этого стали, в свою очередь, полученная автором локальныя характеризация полурешёток +2 для конечных семейств Ои утверждение о том, что все нетривиальные полурешётки и при т > п + 2 не изоморфны (что значительно усиливало результаты, полученные ранее в нескольких работах других авторов).

Последний параграф четвёртой главы посвящен вопросам о минимальных накрытиях и, в частности, вопросу о предельности наибольшего элемента, в полуротпётках которые также активно изучались. Были достигнуты значительные успехи, получен ряд довольно сильных достаточных условий. Полностью вопросы о минимальных накрытиях и о предельности были решены для полурешёток С-^) — У которых конечно или имеет наименьший по включению элемент.

Автор выражает глубокую признательность: Сергею Савостьяновичу Гончарову за всестороннюю помощь и поддержку, а также за постановку задач, инициировавших представленные здесь исследованияЮрию Леонидовичу Ершову за ряд ценных идей, которые помогли ему в доказательстве полученных результатовСерикжану Лгыбаевичу Бадаеву и Андреа Сорби, помогавшим автору в создании плодотворной рабочей обстановки и проявлявшим интерес к обсуждаемым здесь проблемам. Отдельную благодарность автор выражает Виталию Геннадьевичу Ше-лиховскому за всестороннюю помощь и интерес, проявленный к работе. 6.

1. Badaev S. A., Goncharov S. S., Sorbi A. Completeness and Universality of Arithmetical Numberings. / / in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 11 — 44.

2. Badaev S. A., Goncharov S. S., Sorbi A. Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings. // in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 79 91.

3. Badaev S. A., Goncharov S. S. Theory of Numbering: open problems. // Contemporary Mathematics (AMS). 2000. vol. 257, pp. 23 38.

4. Badaev S. A., Goncharov S. S. Computability and Numberings. // New Computational Paradigms, Changing Conceptions of what is Computable, ed.: S. B. Cooper, B. Lowe, A. Sorbi. Springer Science + Business Media, LLC, New York. 2008. pp. 19 34.

5. Goncharov S. S., Harizanov V., Knight J., McCoy Ch., Millar R., Solomon R. Enumerations in computable structure theory. // Annals of Pure and Applied Logic. 2005. vol. 136, №. 3, pp. 219 246.

6. Goncharov S. S. Chisholm J., Fokina E., Harizanov V., Knight J., Miller S. Intrinsic bounds on complexity and definability at limit levels. // Journal of Symbolic Logic. 2009. vol. 74, №. 3, pp. 1047 1060.

7. Lachlan Л H. Two theorems on many-one degrees of recursively enumerable sets // Алгебра и Логика. 1972. Т. 11, j°. 2, С. 216 229.

8. Lachlan А. Н. Recursively enumerable many-one degrees // Алгебра и логика. 1972. Т. 11, № 3. С. 326 358.

9. Odifreddi P. Classical recursion theory, volume II. Elsivier, Amsterdam, 1999.109.

10. Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и Логика. 2001. Т. 40, №. 5, С. 507−522.

11. Бадаев С. А., Гончаров С. С., Сорби Л. Об элементарных теориях полурешёток Роджерса. // Алгебра и логика. 2005. Т. 44, № 3. С. 261 268.

12. Бадаев С. А., Гончаров С. С., Сорби А. Типы изоморфизма полурешёток Роджерса семейств из различных уровней арифметической иерархии // Алгебра и логика. 2006. Т. 45, № 6. С. 637 654.

13. Въюгип В. В. Сегменты рекурсивно перечислимых ш-степеней. // Алгебра и Логика. 1974. Т. 13, №. 6, С. 635 654.

14. Вьюгин В. В. О верхних полурешетках нумераций. // Докл. АН СССР. 1974. Т. 217, №. 4, С. 749 751.

15. Грегпцер Г. Общая теория решёток. М.: Мир, 1982.

16. Гончаров С. С. Счётные булевы алгебры и разрешимость. Научная книга, Новосибирск, 1996.

17. Гончаров С. С., Сорби А. Обобщенно вычислимые нумерации и нетривиальные полурешетки Роджерса. // Алгебра и Логика. 1997. Т. 36, №. 6, 621 641.

18. Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Научная книга, Новосибирск, 1999.

19. Денисов С. Д. Строение верхней полурешётки рекурсивно перечне-лимых т-степеней и смежные вопросы. 1 // Алгебра и логика. 1978. Т. 17, № 6. С. 643 683.

20. Дёгтев А. II. Рекурсивно перечислимые множества и сводимости табличного типа. Наука, Физматлит, Москва, 1998.

21. Ершов Ю. Л. Гипергиперпростые т-степени. // Алгебра и Логика. 1969. Т. 8, №. 5, С. 523 552.

22. Ершов Ю. Л. Теория нумераций. М.: Паука, 1977.

23. Ершов Ю. Л. Необходимые условия изоморфизма полурешеток Роджерса конечных частично упорядоченных множеств. // Алгебра и Логика. 2003. Т. 42, №. 4, С. 413 421.110.

24. Ершов Ю. Л. Полурешётки Роджерса конечных частично упорядоченных множеств. // Алгебра и логика. 2006. Т. 45, № 1. С. 44 — 84.

25. Ершов Ю. Л., Лавров И. А. Верхняя полурешетка Ь (&-). Алгебра и Логика. // 1973. Т. 12, №. 2, С. 167 189.

26. Ершов 10. Л. Верхняя полурешетка нумераций конечного множества. // Алгебра и Логика. 1975. Т. 14, №. 3, С. 258 284.

27. Мальцев А. И., Конструктивные алгебры, 1. // Успехи Мат. Наук. 1961. Т. 16, №. 3, С. 3 60.

28. Палютин Е. А. Дополнение к статье Ю. Л. Ершова «Верхняя полурешётка нумераций конечного множества». // Алгебра и логика. 1975. Т. 14, № 3. С. 284 287.

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

30. Соар Р. И. Вычислимо перечислимые множества и степени. «Казанское математическое общество», Казань, 2000.

31. Успенский В. Л., Лекции о вычислимых функциях. Физматгиз, М., 1960.

32. Хуторецкий А. Б. О мощности верхней полурешетки вычислимых нумераций. // Алгебра и Логика. 1971. Т. 10, №. 5, С. 561 569.Работы автора по теме диссертации.

33. Бадаев С. А., Подзоров С. Ю. Минимальные накрытия в полурешетках Роджерсавычислимых нумераций. // Сиб. Мат. Ж. 2002. Т. 43, №. 4, С. 769 778.

34. Подзоров С. Ю. Начальные сегменты в полурешетках Роджерса вычислимых нумераций. // Алгебра и Логика. 2003. Т. 42, №. 2, С. 211 225.

35. Badacv S. A., Goncharov S. S., Podzorov S. Yu., Sorbi A. Algebraic properties of Rogers semilattices of arithmetical numberings. // in: Computability and Models. 2003. Kluwer Academic/Plenum Publishers, P. 45 77.1.l.

36. Подзоров С. Ю. О предельности наибольшего элемента полурешетки Роджерса. // Матем. Труды. 2004. Т. 7, №. 2, С. 98 108.

37. Подзоров С. Ю. Об определении лахлановской полурешетки. // Сиб. Мат. Ж. 2006. Т. 47, №. 2, С. 383 393.

38. Podzorov S. Yu. Numbered distributive semilattices. // Siberian Adv. in Math. 2007. vol. 17, №. 3, pp. 171 185. (пер. Подзоров С. Ю. Нумерованные дистрибутивные полурешётки. // Матем. Труды. 2006. Т. 9, №. 2, С. 109 — 132.).

39. Подзоров С. Ю. Арифметические m-степени. // Сиб. Мат. Ж. 2008. Т. 19, №. 6, С. 1391 1410.