Структурные свойства верхних полурешеток степеней по перечислимости тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение

1 Элементарные теории полурешеток гг-в.п. степеней по перечислимости

1.1 Свойства е-идеальных множеств.

1.2 Формулировка структурных теорем для полурешеток 7г-в.п. степеней по перечислимости и сравнительный анализ их элементарных теорий.

1.3 Доказательство структурных теорем.

2 Относительные дополнения в верхней полурешетке Д^-е-степеней по перечислимости.

2.1 Существование неполной П^-е-степени, не имеющей относительного Д^-дополнения вниз

2.2 Относительные дополнения вниз для низких е-степеней.

2.3 Проблема существования дополнений для Д"-е-степеней.

Одной из важных задач в теории алгоритмов является изучение алгебраических структур, связанных с понятием вычислимо перечислимого множества. Во-первых это связано с тем, что формальное описание вычислимых функций невозможно без рассмотрения частично-вычислимых функций и их областей определения (последние и есть вычислимо перечислимые множества). Во-вторых, многие известные неразрешимые проблемы математики (такие как, например, проблема равенства слов в ассоциативном исчислении, проблема разрешимости исчисления предикатов, 10-я проблема Гильберта и т.д.), формализованные в арифметике, сводятся к проблеме вычислимости того или иного вычислимо перечислимого множества.

Однако, класс вычислимо перечислимых множеств не может, конечно, охватить весь класс множеств натуральных чисел и, следовательно, весь класс неразрешимых проблем. Поэтому зачастую приходится исследовать возможность эффективного перечисления множества А, которое может не быть вычислимо перечислимым, по заданному перечислению другого множества В. Если это так, то мы говорим, что множество А сводится по перечислимости (е-сводится) к множеству В. Формальное определение этого интуитивно заданного понятия, принадлежащее Роджерсу и Фридбергу [19], будет приведено в пункте 2. Оно будет полностью соответствовать его интуитивному пониманию (см. [33] § 9.7).

В данной работе мы исследуем структуру степеней, называемых степенями по перечислимости или е-степенями, образованную сводимостью по перечислимости, т.е. структуру классов множеств, эквивалентных в том смысле, что их "сложности перечисления" одинаковы. Как и почти любая алгоритмически заданная степенная структура на множестве натуральных чисел, класс степеней по перечислимости является верхней полурешеткой, относительно частичного порядка, индуцированного сводимостью.

Исследования в этой области были начаты Медведевым в 1950-х годах и продолжены в работах Гаттериджа, Розинаса и других. В частности, было показано, что не существует минимальных е-степеней (см. [20]); доказано существование квазиминимальных е-степеней (см. [30]); установлено, что тотальные е-степени порождают относительно операции взятия наибольшей нижней грани все е-степени (см. [34]).

В последние два десятилетия с развитием приоритетных методов особое внимание стало уделяться изучению структуры е-степеней Е° -множеств — аналогу структуры тьюринговых степеней ниже 0' в структуре всех тью-ринговых степеней.

Купером была установлена плотность -е-степеней (см. [9]). В работах (см. [8] и [10]) опровергается плотность верхней полурешетки всех е-степеней. Купер [9] также определил оператор скачка в е-степенях, обобщающий понятие скачка в тьюринговых степенях. Мак-Эвоем [29] (см. также [36]) была введена иерархия, согласованная с оператором скачка, которая подобно арифметической иерархии для тьюринговой сводимости, классифицирует сложность множеств относительно сводимости по перечислимости.

Кроме того, исследовались вопросы, касающиеся наиболее важного класса -е-степеней — класса е-степеней А2-множеств (Д°-е-степеней). Например, Арсланов, Калимуллин и Сорби [6] доказали теорему о плотности Д^-е-степеней, дополняющую теорему Купера [9] о плотности Е° -е-степеней. Йи, Купер и Сорби (см. [12], [13] и [14]) исследовали вопросы о дополняемости и относительной дополняемости Е^-е-степеней. Они показали, что все нетривиальные Д2-е-степени (в отличие от всех Е'^ -е-степеней) обладают относительными дополнениями вниз и наверх в структуре Е^-е-степеней. Эти результаты естественным образом приводят к вопросу о существования дополнения в структуре Д°-е-степеней (или хотя бы в структуре Е°-е-степеней) для произвольной Д2-е-степени. Например, согласно результату Познера [32] ответ положителен для тьюринговых степеней.

В главе 2 исследуется именно этот вопрос и доказывается, что ответ на него отрицателен. Более того, существует неполная П°-е-степень, не имеющая даже относительного дополнения вниз в Д 2-е-степенях (что говорит о том, что результат Купера и Сорби [13] об относительном дополнении вниз для произвольной нетривиальной Д°-е-степени нельзя улучшить построением Д2-относительного дополнения вниз). Далее доказывается, что низкие е-степени все таки имеют относительное дополнение вниз в Д°-е-степенях, что приводит к проблеме существования дополнений хотя бы для низких е-степеней. Последняя теорема в главе 2 приводит к отрицательному ответу и на этот вопрос. А именно, установлено, что существует низкая П°-е-степень, не имеющая дополнений даже в Е° -е-степенях.

При изучении структуры Д^-е-степеней оказывается удобным использовать иерархию Ершова (см. [16]—[18]), являющуюся более тонкой, чем арифметическая иерархия или иерархия Мак-Эвоя, и позволяющая классифицировать все Д2-множества (см. [17]). (Для конечных уровней X"1 этой иерархии множества и степени из этого уровня называются также п-вычислимо перечислимыми или те-в.п.)

В частности, интересным является вопрос о наименьшем уровне в иерархии Ершова, в котором существует степень с тем или иным алгебраическим свойством. Так, например, Купером было замечено [10], что существует квазиминимальные £31 е-степени, тогда как Е^"1 -е-степени быть квазиминимальными не могут.

Аналогично, в главе 1 построением 3-в.п. е-степеней, являющихся вершинами четырехэлементной решетки "ромб", усиливается результат Ахмад [2] о вложимости ромба в Д2-е-степенях.

В этой же главе изучаются вопросы о разложимости ненулевых е-степеней. (Говорят, что е-степень а разложима, если а = Ь0 и Ьх, где Ь0 < а и Ьх < а). Исследования в этой области были начаты Ахмад [1], которая доказала существование ненулевой неразложимой -е-степени.

1. Ahmad S. Some results on the structure of the S2 enumeration degrees//Recursive Function Theory Newsletter. -1989. -V. 38.

2. Ahmad S. Embedding the diamond in the S2 enumeration degrees// J. Symbolic Logic. -1991. -Y. 50. -P. 195-212.

3. Арсланов M. M. Структурные свойства степеней ниже 0' //ДАН СССР. -1985. -V. 283, -№ 2. -С. 270-273.

4. Арсланов М. М. О верхней полурешетке степеней ниже 0' //Изв. вузов. Математика. -1988, -№ 7. -С. 27-33.

5. Arslanov М. М., Degree structures in local degree theory// Lecture Notes in Pure and Applied Mathematics. -1997. -V. 187. -P. 49-74.

6. Arslanov M. M., Kalimullin I. Sh., Sorbi A. Density results in the Д2 e-degrees//Preprint, Universita di Siena, Dipartamento di Matematica, Siena. -1999. -/No 364.

7. Арсланов M. M., Калимуллин И. Ш., Купер С. Б. Свойства разложения тотальных степеней по перечислимсти// работа представлена в журнал Алгебра и Логика. -2001.

8. Calhoun W. С., Slaman Т. A. The П2 е-degrees are not dense// J. Symbolic Logic. -1996. -V. 61. -P. 1364-1379.

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

10. Cooper S. В. Enumeration reducibility, nondeterministic computations and relative computability of partial functions// Lecture Notes in Mathematics. -1990. V. 1432. -P. 57-110.

11. Cooper S. В., Copestake C.S. Properly S2 enumeration degrees// Z. Math. Logik Grundlag. Math.// -1988. -V. 34. -P.491-522.

12. Cooper S. В., Sorbi A. Noncappable enumeration degrees below 0'e// J-Symbolic Logic. To appear.

13. Cooper S. В., Sorbi A. Capping in the enumeration degrees below 0'e.// To appear.

14. Cooper S. В., Sorbi A., Yi. X.Cuppping and noncupping in the enumeration degrees of £° sets// Ann. Pure Appl. Logic. -1996. -V. 82. -P. 317-3-42.

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

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

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

18. Ершов Ю. Л. Об одной иерархии множеств III// Алгебра и Логика. -1970. -№ 1. -С. 34-51.

19. Fridberg R. М., Rogers Н. Reducibilty and completeness for sets of integers// Z. Math. Logic and Grundl. Math. -1959. —V. 2, -No 2. -P. 117-125.

20. Gutteridge L. Some Results on Enumeration Reducibility//PhD thesis, Simon Fraser University. -1971.

21. C. G. Jockusch, Jr. Semirecursive sets and positive reducibility// Trans. Amer. Math. Soc. -1968. -V. 131. -P. 420-436.

22. Калимуллин И. Ш. Об элементарных теориях полурешеток п-р.п. степеней по перечислимости// Изв. вузов. Математика. -2001. 4. -С. 24-27.

23. Kalimullinl. Sh. Splitting properties of n-c.e. enumeration degrees// работа принята к печати в Journal of Symbolic Logic.

24. Калимуллин И. Ш. Относительные дополнения в степенях по перечислимости// Алгебра и Логика. -2000. -№ 5. -С. 547-566.

25. Калимуллин И. Ш. Об элементарных теориях п-р.п. степеней по перечислимости// тезисы международной конференции "Логика и приложения" (Новосибирск, май 2000 г.). 2000. -С. 81.

26. Kalimullin I. Sh. On the group generated by primitive recursive permutations// тезисы международной конференции "Computability and models" (Hiedelberg, January 2001). 2001. -P. 11.

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

28. Lachlan A. H. Bounding minimal pairs// J. Symbolic Logic. -1979. -V. 44. -P. 626-642.

29. McEvoy K. The structure of enumeration degrees// PhD thesis, School of Mathematics, University of Leeds. -1984.

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

31. Miller D. High recursively enumerable degrees and the anti-cupping property// Lecture Notes in Mathematics. -1981. -V. 859. -P. 230-245.

32. Posner D. The upper semilattice of degrees < 0' is complemented// J. Symbolic Logic. -1981. -V. 46. -P. 705-713.

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

34. Розинас М. Г. О полурешетке е-степеней// Рекурсивные функции, Ивановский гос. университет -1978. -С. 71-84

35. Soare R. I. Recursively enumerable sets and degrees, Heidelberg: SpringerVerlag, 1987. (см. русский перевод: Соар Р. И. Вычислимо перечислимые множества и степени -Казань: Казанское мат. общество, 2000. 576 с.)

36. Sorbi A. The enumeration degrees of sets// Lecture Notes in Pure and Applied Mathematics. -1997 -V. 187. -P. 303-330.

37. Yates С. E. M. A minimal pair of recursively enumerable degrees)/J. Symbolic Logic. -1966 -V. 31. -P. 159-168.