Тьюринговые скачки в иерархии Ершова тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Файзрахманов, Марат Хайдарович

• Файзрахманов, Марат Хайдарович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Файзрахманов, Марат Хайдарович

Введение

Глава 1. Тьюринговые скачки в иерархии Ершова

§1.1. Иерархия Ершова, конструктивные ординалы и системы обозначений

§1.2. Уровни иерархии Ершова, содержащие тыорипговые скачки

§1.3. Вычислимые нумерации семейств низких множеств.

Глава 2. Элементарные теории алгебраических систем, порожденных низкими степенями

§2.1. Полурешетка, порожденная супернизкими в.п. степенями

§2.2. Низкие в.п. и низкие 2-в.п. степени не элементарно эквивалентны

Глава 3. .Е-скачки в иерархии Ершова

§3.1. Сводимость по перечислимости и е-степени

§3.2. Уровни иерархии Ершова, содержащие е-скачки.

§3.3. Дополнения низких П^-е-степеней.

Введение диссертации (часть автореферата) на тему «Тьюринговые скачки в иерархии Ершова»

Одттим из важных понятий в теории вычислимости является понятие низкого множества, которое, интуитивно, выражает, что множество слабо вычислимо. Это связано с тем, что при изучении алгоритмических свойств множеств натуральных чисел часто возникает вопрос, при отсутствии подходящего вычислимого множества, о нахождении низкого множества, удовлетворяющего данному свойству. Например, согласно с теоремой Джоку-ша и Соара о низком базисе [34], каждый непустой П®-класс содержит низкое множество; по теореме Амбос-Шпииса, Джокуша и других [15], каждая быстро простая степень имеет низкое дополнение наверх. С другой стороны, существует большое количество литературы, посвященной низким множествам и их свойствам, которые напоминают свойства вычислимых множеств. Например, Соар установил [46], что решетка вычислимо перечислимых (в.п.) надмножеств низкого в.п. множества изоморфна решетке всех в.п. множеств; согласно с теоремой Робинсона [41], теорема Сакса о разложении справедлива в верхнем конусе любой низкой в.п. степени.

Множество А называется низким, если А' =т 0'- Таким образом, оператор скачка по, может различать вычислимые и низкие множества. В известной работе Бикфорда и Миллса [17] введено понятие суперпизких множеств, которое естественным образом усиливает понятие низких множеств: множество А называется супернизким, если А' =и 0'- Стандартное построение низкого простого в.п. множества с сохранением вычисления скачка уже дает супернизкое множество (как и теорема о низком базисе). Однако не каждое низкое множество является супернизким. Одним из следствий теоремы Сакса о разложении [43] является существование таких низких в.п. множеств Ао. А\, что Ао П А\ = 0 и Ао и А\ = 0'. Согласно с результатом Бикфорда. и Миллса [17], одно из таких множеств Ао, А\ не супернизкое.

Более того, упорядоченные множества низких п.п. и супернизких п.п. степеней не элементарно эквивалентны (см. Доуней, Гринберг и Вебер [29|).

В работах Ершова [5][6][7] построена иерархия множеств А ^т 0', получившая в литературе название "иерархия Ершова". Как оказалось, возникающая иерархия исчерпывает весь класс множеств А 0'- Каждый следующий уровень иерархии содержит все предыдущие и не совпадает пи с одним из них. В представленной работе изучаются новые усиленные понятия низких множеств, а именно множества, тыоринговые скачки которых лежат в фиксированных бесконечных уровнях иерархии Ершова. По результату Карстенса [18], множества А из первого бесконечного (А"1-) уровня иерархии Ершова характеризуются условием А ^и 0'. Поэтому первым уровнем такой иерархии скачков будет класс супернизких множеств.

Первый, естественно возникающий, вопрос при изучении иерархии Ершова для скачков - будет ли каждый уровень содержать скачки, не ле-•жащие в меньших уровнях. Легко проверить, что для конечных уровней это не верно, то есть, если А' п-в.п., тогда А' в.п. В первой главе устанавливается, что и бесконечные уровни могут не содержать тыоринговые скачки. Более того, если дан ординал а < и2 и А' € А"1, тогда А супернизкое (в частности, если А' 6 тогда А' Е А"1). Вторая часть первой главы носвящена вопросу о существовании А^-вычислимых нумераций классов скачков. Впервые этот вопрос был изучен Ниисом. В работе [39] оп ввел понятие мпоэюеегпва с 7про,ссирусмым скачком и установил, что для в.п. множеств этот класс совпадает с классом суперпизких множеств. Класс множеств с трассируем скачком будем обозначать «7Т. Индексное множество в.п. множеств из <7Т принадлежит Ед-уровню арифметической иерархии. Следовательно, класс всех суперпизких в.п. множеств имеет вычислимую нумерацию. Однако, в общем случае множества с трассируемым скачком могут не быть супернизкими. Тем не менее в § 2 устанавливается, что каждый уровень иерархии скачков (в частности, семейство всех супернизких множеств) имеет А^-вычислимую нумерацию.

В последние годы с развитием алгоритмической теории случайности особое внимание стало уделяться изучению структурных свойств классов низких степеней, особенно, супернизких степеней. Даймондстоуном ¡24] было установлено существование быстро простой степени, не имеющей относительных супернизких дополнений наверх. Доунсй, Гринберг и Вебер установили [29}, что все суперпизкие в.п. степени не ограничивают критических троек, в то время как существует низкая копия конечной решетки М5. Вторая глава посвящена изучению структурных свойств тыоринговых степеней множеств, скачки которых лежат в фиксированных уровнях иерархии Ершова. По теорема Сакса о разложении полурешетка в.п. степеней порождается низкими в.п. степенями относительно операции взятия наименьшей верхней грани. Обозначим эту полурешетку через С. Аналогичным образом можно определить полурешетку J, порожденную супернизкими в.п. степенями. Очевидно, что 0 Е 3. Бикфорд и Миллс [17| установили, что О' Е 3. Основной результат первого параграфа второй главы заключается в различии полурешеток С и О". Более того, найденное различие является элементарным. Второй параграф посвящен вопросу о различии элементарных теорий упорядоченных множеств низких в.и. (обозначается и низких 2-в.п. (обозначается И1™") степеней. Впервые, различие элементарных теорий структур Их и 02 (в.п. и 2-в.п. степеней соответственно) было установлено Арслановым |2|: каждая 2-в.п. степень имеет относительное 2-в.п. дополнение наверх. Однако, пи одно из известных элементарных различий между П\ и И2 (см. [23][25]) не будет элементарным различием между В1^". Искомое элементарное различие получается из следующего предложения: для каждого обозначения конструктивного ординала существует низкая 2-в.п. степень, не являющаяся разложимой па две меньшие 1

2-в.п. степени, скачки которых принадлежат А-уровню иерархии Ершова, соответствующему этому обозначению. Согласно с теоремой Велша [49]. полурешетка в.п. степеней порождется двумя главными идеалами из низких в.п. степеней. Следовательно И1™" ф П1.™" (также этот результат другими методами независимо получил Ямалеев [14]).

Естественным обобщением понятия тыорингового скачка является понятие скачка по перечислимости, введенное Купером [21]: множество

К {А) = в2(А)} называется скачком по перечислимости множества А, где ©, - это оператор перечисления с геделевским номером г. Легко видеть, что К (А® А) =1 А1. Поэтому каждый уровень иерархии Ершова, содержащий тьюринговый скачок, содержит также скачок по перечислимости. Однако поведение скачков по перечислимости отличается от поведения тыоринговых скачков: в третьей главе, совместно с И.Ш. Калимуллиным, установлено, что Е- уровни могут содержать скачки по перечислимости, более того, существует множество А такое, что К (А) Е Е~х — А"1.

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

Определения и обозначения. Все рассматриваемые множества и функции заданы на множестве натуральных чисел и = {0,1,2,.}. Мы используем малые латинские буквы /, д, к для обозначения всюду определенных функций; малые греческие буквы (р^ф^О используются для обозначения частичных функций. Для частичной функции </? и аргумента х пишем ip{x) 4-5 ссли функция ip определена на аргументе ж; в противном случае пишем ip(x) t- Через dorn ip> и ran (р обозначены соответственно область определения и область значений функции (р. Для множества А его характеристическая функция обозначается ха> мы часто отождествляем А с его характеристической функцией, записывая се как А(х). Ограничение функции / на аргументы у < х записывается / \ х\ запись A f х означает Ха I х. Если Р - предикат на множестве натуральных чисел, то запись цхР{х) означает наименьшее число х такое, что Р(х).

Тьюринговый функционал с геделевским номером z записывается как Ф~. Через use(X; z,x) обозначается itse-функция функционала Ф~(Х;а;). Вместо Ф,(0) пишем ipz\ обозначим Wz — dorn ip>z - в.п. множество с геделевским номером

Для множества А обозначим через А его дополнение; запись А — В означает А П В. Мощность множества А обозначается как |Л| или card А\ наибольший элемент конечного множества А обозначается через max А; полагаем тах0 = 0. Обозначим через А ф В сочленение множеств А и В, а именно, множество {2х : х £ Ä\ U {2х + 1 : х Е В}. Образ пары (х, у) относительно стандартной функции пары х2 + 2ху + у'2 + Зж + у) обозначается как {х,у)\ запись (х\,х2,хз) означает {{х\, х^), Жз); аналогично определяется (рс\, Х2, ■ ■ ■, хп). Определим проекции щ, тг\ относительно функции пары, полагая тго((х,у)) = х и 7Гх((х,у)) = у. Для множества А обозначаем А^ — {(y,z) : (y,z) 6 А}.

Список литературы диссертационного исследования кандидат физико-математических наук Файзрахманов, Марат Хайдарович, 2011 год

1. Арсланов М. М. О структуре степеней ниже 0'. // Известия вузов. Математика. 1988. - № 7. - С. 27-34.

2. Арсланов М. М., Калимуллин И. Ш., Купер С. Б. Свойства разложимости тотальных степеней по перечислимости. // Алгебра и Логика. 2003. - Т. 42. - № 1. - С. 3-25.

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

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

5. Ершов Ю. Л. Об одчюй иерархии множеств, II // Алгебра и Логика.- 1968. Т. 7. - т. - С. 15-48.7| Ершов Ю. Л. Об одной иерархии мнооюеетв, III // Алгебра и Логика.- 1970. Т. 9. - №1. - С. 34-52.

6. Ершов Ю. Л. Теория нумераций. М.: Наука. - 1977. - 416 с.

7. Калимуллин И. Ш. Структурные свойства верхней полурешетки степеней по перечислимости // Диссертация на соискание ученой степени к.ф.-м.и. Казанский государственный университет. Казань.- 2001.

8. Медведев Ю. Т. Степени трудности массовых проблем. // ДАН СССР 1955. - Т. 104. - С. 501-504.

9. Мучник А. А. Неразрешимость проблемы сводимости теории алгоритмов И ДАН СССР 1956. - Т. 108. - С. 194-197.

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

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

12. Ямалеев М. М. Структурные свойства тьюринговых степеней множеств из иерархии Ершова, // Диссертация на соискание ученой степени к.ф.-м.н. Казанский государственный университет. Казань.- 2009.

13. Arslanov M.M., Cooper S., Li A. There is no low maximal d. c. e. degree- Corrigendum. // Mathematical Logic Quarterly 2004. - V. 50. - № 6.- P. 628-636.

14. Bickford M., Mills F. Lowness properties of r.e. sets // Manuscript, UW Madison. 1982.

15. Carstcns H. G. A\-mengen. // Arch.Math.Log.Grundlagenforsch. 1976.- V. 18. P. 55-65.

16. Cholak P., Groszek M., Slaman T. An almost deep degree. // J. Symbolic Logic. 2001. -V. 66. - № 2. - P. 881-901.20j Cooper S. B. Degrees of Unsolvability. // Ph.D. Thesis, Leicester University, Leicester, England. 1971.

17. Cooper S. B. Partial degrees and the density problem. Part, 2: The enumeration degrees of the sets are dense. // J. Symbolic Logic.- 1984. V. 49. - P. 503-513.

18. Cooper S. B., Enumeration reductibility, nondetcrministic computations and relative compitability of partial functions. // Lecture Notes in Mathematics. 1990. - V. 1432. - P.57-110.

19. Cooper S. B., Harrington L.,x Lachlan A. H., Lempp S., Soare R. I. The d.r.e. degrees are not dense. // Ann. Pure Appl. Logic 1991. - V. 55.- P. 125-151.

20. Diamondstone D. Promptness does not imply superlow cuppable. // J. Symbolic Logic. 2009. - V. 74. - № 4. - P. 1264-1272.

21. Downey R. D.r.e. degrees and the nondiamond theorem. // Bull. London Math. Soc. 1989. - V . 21. - P. 43-50.

22. Downey R. Lattice nonembeddings and initial segments of the recursively enumerable degrees. // Ann. Pure Appl. Logic. 1990. - V. 49. - № 2.- P. 97-119.

23. Downey R., Jockusch C., Stob M. Array nonrecursive sets and multiple permitting arguments. // Lecture Notes in Math. -1990. V. 1432.- P. 141-173.

24. Downey R., Jockusch C., Stob M. Array nonrecursive degrees and genericity. // London Math. Soe. Lecture Note Ser. 1996. - V. 224.- P. 93-104.

25. Downey R., Greenberg N., Weber R. Totally u-computable emimerable degrees and bounding critical triples // J. Math. Logic 2007. - V. 7.- № 2. P. 145-171.

26. Epstein E. L. Minimal degrees of unsolvability and the full approximation construction // Memoirs of the American Mathematical Society. 1974.- № 162. American Mathematical Society, Providence, RI.

27. Friedberg R. M. Two recursively enumerable sets of incomparable degrees of unsolvability. // Proc.Natl. Acad. Sci. USA 1957. - V. 43. - P. 236238.

28. Friedberg R. M., Rogers H. Reducibilty and completeness for sets of integers // Z. Math. Logic and Grundl. Math. 1959. - V.2. - № 2.- P. 117-125.

29. Greenberg N., Nies A. Benign cost functions and lowness properties, j/ To appear.

30. Jockusch C. G., Soare R. I. U°rcla sses and degrees of theories, j j Trans. Amer. Math. Soc. 1972. - V. 173. - P. 33-56.

31. Kalimullin I. Sh. Some Notes on Degree Spectra of the Structures. // Lecture Notes in Computer Science. 2007. - V. 4497. -P. 389-398.

32. Kalimullin I. Sh. Splitting properties of n-c.e. enumeration degrees. // J. Symbolic Logic. 2002. - V. 67. - № 2. - P. 537-546.

33. Lachlan A. H. Lower bounds for pairs of recursively enumerable degrees. // Proc. London Math. Soc. 1966. - V. 16. - P. 537-569.i

34. Miller D. P. High recursively enumerable degrees and the anticupping property. // Lecture Notes in Math. 1981. - V .859. -P. 230—245.

35. Nies A. Reals which compute little // Lecture Notes in Logic. 2002.- V. 27. -P. 261-275.

36. Nies A. Computability and Randomness. New York.: Oxford University Press. - 2009. - 442 p.

37. Robinson R W. Jump restricted interpolation in the recursively enumerable degrees. // Annals of Math. 1971. - V. 93. - P. 586-596.

38. Sacks G. E. A minimal degree less than 0'. // Bull. Amer. Math. Soc.- 1961 V. 67. - P. 416-419.43j Sacks G. E. On the degrees less than 0' // Ann. of Math. 1963. - V. 2.- № 77. P. 211-231.

39. Sacks G. E. The recursively enumerable degrees are dense, j j Ann. of Math. 1964. - V. 80. - № 2. - P. 300-312.45| Schacffer B. Dynamic notions of genericity and array noncomput ability, j j' Ann. Pure Appl. Logic. 1998. - V. 95. - P. 37-69.

40. Soare R. Automorphisms of the lattice of recursively enumerable sets Part II: Low sets. // Annals of of Math. Logic. 1982. - V. 22 - P. 69-107.

41. Walk S. Towards a definition of the array computable degrees, j j PhD thesis, University of Notre Dame. 1999.

42. Wcinstein B. On embeddings of the 1-3-1 lattice into the recursively enumerable degrees, j/ PhD thesis, University of California, Berkeley. 1988.

43. Welch L. A herarchy of families of recursively enumerable degrees and a theorem of founding minimal pairs. // Ph.D. Diss. University of Illions. Urbana. 1980.

44. Yates C. E. M. On the degrees of index sets 11 j j Trans. Amer. Math. Soc. 1969. - V. 135. - P. 249-266.