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

1 Предварительные сведения

2 Свойство униформизации в наследственно конечных надстройках

3 Е-допустимые семейства в HYP-надстройках

§3.1 Е-регулярные семейства.

§3.2 Фундаментальные множества

§3.3 Фундаментальные семейства в линейных порядках.

§3.4 Д*-множества в HYP-надстройках

4 Е-определимость специальных допустимых множеств

§4.1 О парах рекурсивно насыщенных систем.

§4.2 Е-определимость классов моделей с-простых теорий.

§4.3 Е-определимость специальных допустимых множеств.

Теория допустимых множеств, возникшая в середине 60-х годов прошлого века и получившая наиболее полное описание в классической монографии Дж. Барвайса "Admissible sets and structures" [22], изучает вопросы, находящиеся на стыке различных направлений математической логики: теории моделей, теории вычислимости и теории множеств. Развитие этой теории началось с обобщения теории вычислимости, при котором классическая теория вычислимости на натуральных числах становилась частным случаем теории вычислимости на ординалах. В работах С. Крипке и Р. Платека было введено понятие допустимого ординала и предложен подход, при котором вопросы, связанные с вычислимыми свойствами некоторых объектов (множеств натуральных чисел, ординалов), превращаются в вопросы определимости этих свойств в некоторой конструктивной части теоретико-множественного универсума при помощи специальных Е-формул. Развитие теории вычислимости на допустимых ординалах отражено в книге Дж. Сакса [31]. Одним из наиболее сложных вопросов этой теории является, в частности, исследование тьюринговой сводимости на ординалах.

Важным шагом в дальнейшем развитии стали работы Дж. Барвайса, в которых было введено понятие допустимого множества с праэлементами. Допустимые множества — это модели теории KPU (аббревиатура происходит от имен создателей этой теории - Крипке и Платека, - а также от первой буквы слова "urelements" - "праэлементы"), носителями которых служат транзитивные подмножества теоретико-множественного универсума с праэлементами — объектами, не наделенными структурой множества. То, что в качестве множества праэлементов может выступать носитель некоторой абстрактной структуры, оказывается очень важным для развития теории обобщенной вычислимости. Подход к пониманию вычислимости над абстрактной структурой как Е-определимости в допустимых множествах над этой структурой, в последнее время активно развивается. Классической монографией, в которой принят за основу такой подход, является монография Ю.Л. Ершова "Определимость и вычислимость" [4].

Как и в случае теории вычислимости на натуральных числах, имеется довольно много различных способов формализации обобщенной вычислимости для произвольной структуры Ш. Можно указать, например, монографию Я. Московакиса "Elementary induction on abstract structures" [29], где за основу принято понятие индуктивной определимости в 9Я, а также работу Р. Монтегю " Recursion theory as a branch of model theory" [28], использующую в качестве базисного понятие определимости в некотором многосортном языке, расширяющем язык структуры Ш1. С.С. Гончаровым, Ю.Л. Ершовым и Д.И. Свириденко был предложен подход, при котором вычислимость в структуре ШТ понимается как S-определимость в наследственно конечной списочной надстройке над моделью Ш (см. [2]). Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная омскими учеными И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым [1], использующая понятие некоторого абстрактного вычислительного устройства (BSS-машины), заданного на наследственно конечной списочной надстройке над структурой ЯЯ. Наконец, Ю.Л. Ершовым был предложен общий подход к пониманию обобщенной вычислимости на структуре ®t как Е-определимости в допустимых множествах над Ш (именно этот подход используется в работах А.С. Морозова, В.А. Руднева [15, 16], А.Н. Хисамиева, В.Г. Пузаренко [14], А.В. Роминой и др.). Следует отметить, что, как и в случае классической теории вычислимости, с точки зрения конечного результата (например, описания всех вычислимых отношений на структуре Ш) все вышеназванные подходы оказываются эквивалентными (см., например, работу [23]).

В подходе, при котором вычислимость на абстрактной структуре трактуется как Е-определимость в допустимых множествах над этой структурой, основное внимание уделяется изучению свойств вычислимости в специальных допустимых множествах. Под таковыми понимаются допустимые множества двух следующих типов: наследственно конечные надстройки над моделями, то есть допустимые множества вида HF(fJR) (где 971 — некоторая модель), которые в дальнейшем называтются HF-надстройками, и допустимые множества вида НУР{Ш) (где Ш — некоторая модель конечной сигнатуры), которые, по аналогии, будем называть в дальнейшем HYP-надстройками. Особенностью таких допустимых множеств является некоторая их "минимальность" относительно теоретико-множественного включения: для произвольной модели Ш (конечной сигнатуры) наследственно конечная надстройка HF(ffl) является наименьшим допустимым множеством, содержащим носитель М модели 971 как подмножество (М С HF(ffi)) (в англоязычной терминологии "a least admissible over 97Г'), в то время как надстройка вида HYP(Wl) является наименьшим допустимым множеством, содержащим носитель модели 971 как элемент (М G HYP(9R)) (в англоязычной терминологии "a least admissible above 971"). В силу такой "минимальности" , Е-определимость в допустимых множествах HF(ffl.) и НУР(Ш) лучше всего соответствует различным аспектам понятия обобщенной вычислимости в модели 971.

Вопросы определимости в таких " близких" к модели 971 допустимых множествах напрямую связаны с вопросами определимости в самой модели 971. Отсюда, однако, следует, что для сохранения классических свойств вычислимости на "сложность" модели 971 требуется наложить некоторые ограничения. Один из самых ярких примеров несоответствия между классической и обобщенной теорией вычислимости — результат В.А. Руднева [15], дающий пример модели 971, для которой в наследственно конечной надстройке HF(971) не существует универсальной вычислимой Е-функции. Отличительной особенностью построенной модели является то, что ее теория не является модельно полной. Поэтому естественным представляется рассмотрение моделей, теории которых обладают некоторым набором "регулярных" свойств, обеспечивающих необходимую согласованность обобщенной вычислимости в данной модели с классической теорией вычислимости.

Согласно [4], теория Т некоторой (конечной) сигнатуры а называется регулярной, если она модельно полна и разрешима. Моделями регулярных теорий являются, например, любой плотный линейный порядок L, а также поля R, С, Qp вещественных, комплексных и р-адических чисел, для которых (особенно для поля R) формализация понятия вычислимости представляет наибольший интерес. Так, например, М.В. Коровиной в работе [7] было доказано, что в наследственно конечной списочной надстройке над полем R существует универсальная вычислимая функция. Однако трудно считать теорию поля Ж простой, так как она имеет много неконструктиви-зируемых счетных моделей. Согласно [4], теория Т называется с-простой, если она регулярна, счетно категорична и имеет разрешимое множество полных формул. Примерами с-простых теорий могут служить теория чистого равенства, а также теория плотного линейного порядка. Модели с-простых теорий представляют большой интерес при изучении свойств вычислимости над несчетными моделями (см. [3]).

Настоящая работа посвящена изучению свойств вычислимости в специальных допустимых множествах, а именно в HF-надстройках и HYP-надстройках над моделями регулярных и с-простых теорий. Основными результатами работы являются следующие.

1. Получен критерий наличия свойства униформизации в наследственно конечных надстройках над моделями регулярных теорий. Как следствие, установлено наличие свойства униформизации и существование универсальной функции в наследственно конечных надстройках над полями вещественных и р-адических чисел.

2. Получено описание Е*-множеств праэлементов в HYP-надстройках над рекурсивно насыщенными моделями. Как следствие, получено описание £*-множеств для плотных линейных порядков.

3. Получен критерий рекурсивной насыщенности для пар моделей.

4. Получены критерии спектральной Е-определимости над классами моделей теорий плотного линейного порядка и чистого равенства.

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

1. И.В. Ашаев, В.Я. Беляев, А.Г. Мясников, Подходы к теории обобщенной вычислимости, Алгебра и логика, 32, N 4 (1993), 349 - 386.

2. С.С. Гончаров, Д.И. Свириденко, Е-программирование, в сб." Логико-математические проблемы МОЗ", (Вычислительные системы, 107), Новосибирск, Ин-т матем. СО АН СССР , 1985, 3 29.

3. Ю.Л. Ершов, Определимость в наследственно конечных надстройках, Доклады РАН, 340, N 1 (1995), 12 14.

4. Ю.Л. Ершов, Определимость и вычислимость, Новосибирск, Научная книга, 1996.

5. Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, М., Наука, 1980.

6. Ю.Л. Ершов, Е-допустимые множества, в сб." Логические вопросы теории типов данных", (Вычислительные системы, 114), Новосибирск, Инт матем. СО АН СССР, 1986, 35 39.

7. М.В. Коровина, О.В. Кудинов, Новый подход к вычислимости веще-ственнозначных функций, в сб."Структурные алгоритмические свойства вычислимости", (Вычислительные системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 3 23.

8. Х.Дж. Кейслер, Основы теория моделей, Справочная книга по математической логике, часть 1, 55 108, М., Наука, 1982.

9. Х.Дж. Кейслер, Ч. Ч. Чен, Теория моделей, М., Мир, 1977.

10. А. Макинтайр, Модельная полнота, Справочная книга по математической логике, часть 1, 141 182, М., Наука, 1982.

11. М. Маккаи, Допустимые множества и бесконечная логика, Справочная книга по математической логике, часть 1, 235 288, М., Наука, 1982.

12. М.Г. Перетятькин, Конечно аксиоматизируемые теории, Новосибирск, Научная книга, 1997.

13. В. Г. Пузаренко, О вычислимости над моделями разрешимых теорий, Алгебра и логика, 39, N 2 (2000), 170 197.

14. В.А. Руднев, Об универсальной рекурсивной функции на допустимых множествах, Алгебра и логика, 25, N 4 (1986), 425 435.

15. В.А. Руднев, О существовании неотделимой пары в рекурсивной теории допустимых множеств, Алгебра и логика, 27, N 1 (1987), 48 56.

16. В.Ю. Сазонов, Д.И. Свириденко, Денотационная семантика языка £-выражений, в сб."Логические вопросы теории типов данных", (Вычислительные системы, 114), Новосибирск, Ин-т матем. СО АН СССР, 1986, 16 34.

17. Дж.Е. Сакс, Теория насыщенных моделей, М., Мир, 1976.

18. Р.И. Соар, Вычислимо перечислимые множества и степени, Казань, 2000.

19. A. Adamson, Admissible sets and the saturation of structures, Ann.Math.Logic, 14, N 2 (1978), 111 157.

20. A. Adamson, Saturated structures, unions of chains and preservation theorems, Ann.Math.Logic, 19, N 1 (1980), 67 96.

21. J. Barwise, Admissible sets and structures, Berlin, 1975.

22. C.E. Gordon, Comparisons between some generalisations of recursion theory, Compositio Math., 22, N 3 (1970), 333 346.

23. E. Herrmann, On Lindebaum functions of tto-categorical theories of finite similarity type, Bull.Acad.Polon.Sci.Ser.Sci.Math.Astronom.Phis, 24, N 1 (1976), 17- 21.

24. H.A. Kierstead, J.B. Remmel, Indiscernibles and decidable models, J. Sim-bolic Logic, 48, N 1 (1983), 21 32.

25. H.A. Kierstead, J.B. Remmel, Degrees of indiscernibles in decidable models, TAMS, 289, N 1 (1985), 41 57.

26. A. Macintyre, On definable subsets of p-adic fields, J. Symbolic Logic, 41, N 3 (1976), 605 610.

27. R. Montague, Recursion theory as a branch of model theory, Proceedings of the Third International Congress for Logic, Methodology and Philosophy of Science, Amsterdam, 1967.

28. Y.N. Moschovakis, Elementary induction on abstract structures, North-Holland, 1974.

29. J.P. Ressayre, Models with compactness properties relative to an admissible language, Ann.Math.Logic, 11, N 1 (1977), 31 56.

30. G.E. Sacks, Higher recursion theory, Berlin, 1990.

31. J.H. Schmerl, A decidable categorical theory with a non-recursive Ryll-Nardzewski function, Fund.Math, 48, N 2 (1978), 121 125.

32. L. van den Dries, Algebraic theories with definable Skolem functions, J. Symbolic Logic, 49, N 4 (1984), 625 630.Работы автора по теме диссертации

33. А.И. Стукачев, Теорема об униформизации в HF(R), Материалы XXXIV международной научной студенческой конференции "Студент и научно-технический прогресс": Математика, НГУ, 1996, 83.

34. A.I. Stukachev, Uniformization property in heredidary finite superstructures, Siberian Advances in Mathematics, 7, N 1 (1997), 123 132.

35. А.И. Стукачев, Теорема об униформизации в наследственно конечных надстройках, в сб. "Обобщенная определимость и вычислимость", (Вычислительные системы, 161), Новосибирск, Ин-т Математики СО РАН, 1998, 3 14.

36. А.И. Стукачев, £-допустимые семейства в структурах вида HYP(9Jt), в сб. "Algebra and Model Theory 3", Новосибирск, изд. НГТУ, 2001, 126 -130.

37. А.И. Стукачев, Е-допустимые семейства над линейными порядками, Алгебра и логика, 41, N 2 (2002), 228 252.

38. А.И. Стукачев, Об определимости в допустимых множествах вида HF(SDt), в сб. трудов 33-й региональной молодежной конференции "Фундаментальные проблемы теоретической и прикладной математики", Екатеринбург, 2002, стр. 47 50.

39. А.И. Стукачев, О некоторых свойствах вычислимости над моделями, препринт N 18 , Новосибирск, НГУ, 2002.