Вычислимые модели эренфойхтовых теорий

Диссертация посвящена исследованию некоторых вопросов теории конструктивных (вычислимых) моделей. Её основные результаты относятся к конструктивным моделям эренфойхтовых теорий, хотя некоторые рассматриваемые проблемы имеют более обгций характер. Теория конструктивных моделей возникла в 50-ых годах XX века в работах А. И. Мальцева, М. Рабина и других выдающихся математиков, с тех пор активно развивается. Объём литературы, посвященный этой тематике, очень велик. В качестве наиболее важных и современных источников можно указать [7], [2] и [11]. Эренфойхтовы теории являются классическим объектом не только для теории конструктивных моделей, но и, собственно, для теории моделей, где до сих пор остаются открытыми некоторые важнейшие проблемы, связанные с этим классом теорий. Из литературы по теории моделей стоит назвать [4], [27] и [14], по теории вычислимости — [26] и [28].

Основные результаты, касающиеся конструктивных моделей малых теорий, можно найти в [7], [11]. Главные современные открытые вопросыв [8].

Напомним, что полная теория Т называется малой, если множество.

Б (Т) её типов (под типом подразумевается максимальное совместное с теорией множество формул) счётно. Если обозначить через ш (Т) число попарно неизоморфных счётных моделей счётной полной теории Т, то Т называется эренфойхтовой, если 3 ^ ^(Т) < и>. Если со (Т) = 1, теория называется счётно-категоричной. Невозможность случая ш (Т) = 2 является классическим результатом Воота [32]. Ещё одним подклассом класса малых теорий являются категоричные теории, т. е. теории, любые 2 модели мощности которых изоморфны. В этом случае ш{Т) = ш.

Модель называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел и, а операции и предикаты — равномерно вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами — обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка. ^ Говорим, что произвольная модель консгпрукти-визируема, если она изоморфна некоторой вычислимой модели.

Главнейшими вопросами теории конструктивных моделей являются: проблема существования вычислимой модели, количество конструктиви-зируемых моделей данной теории, какие модели являются конструкти-визируемыми. Вопросы эти не праздны. К примеру, для классов эрен-фойхтовых и ¿-¿-¡—категоричный теорий на сегодняшний день нет удовле.

Эти два подхода (вычислимость и конструктивность) можно охарактеризовать как западный и советский соответственно. творительного ответа ни на один из них. Особенно сложно дело обстоит с эренфойхтовыми теориями.

Множество формул назовём разрешимым, если существует алгоритм, проверяющий принадлежность произвольной формулы данному множеству. Модель 21 разрешима, если найдётся алгоритм, отвечающий на вопрос 21 |= (р (а0,., ап) равномерно по <£>, ао,. ¦ ¦, ап.2^ Для ши и>х-категоричных теорий имеется замечательный результат Харрингтона [12] и Хисамиева [15] об эквивалентности разрешимости теории разрешимости всех её моделей. Последнее же, в свою очередь, равносильно существованию разрешимой модели этой теории. В то время, как для эренфойхтовых теорий сначала Лахлан и Морли [21] построили пример разрешимой теории с шестью моделями, среди которых имеются неразрешимые, а затем Перетятькин [23] обнаружил серию примеров разрешимых эренфойхтовых теорий, имеющих любое число моделей, среди которых лишь простая разрешима. Во всех упомянутых примерах неразрешимые модели получаются за счёт наличия неразрешимых типов. В той же статье Морли [21] имеется естественный в этом свете вопрос, который открыт до сих пор, давно стал фольклором и хорошо известен под названием.

Проблема Морли. Пусть Т — эренфойхтова теория, и все типы, совместные с Т, разрешимы. Любая ли счётная модель теории Т разрешима?

Стоит отметить, что если с эренфойхтовой теорией совместны только.

Конструктивизируемость модели эквивалентна существованию такого алгоритма лишь для бескванторных формул у. разрешимые типы, то имеется по крайней мере 3 разрешимые модели: простая (модель, элементарно вкладывающаяся в любую другую модель теории), насыщенная (модель, в которую все остальные модели теории элементарно вкладываются) и слабо насыщенная (модель, реализующая все типы теории), но не насыщенная.3−1 Поэтому, в случае отрицательного ответа на проблему Морли, контр-пример должен иметь, по меньшей мере, 4 модели.

На пути решения этой проблемы возникали различные её аналоги. Например, можно переходить к более высоким уровням алгоритмической сложности. Скажем, что отношение является гиперарифметическим (арифметическим), если оно получено из вычислимого отношения взятием (конечного числа раз) проекций и дополнений. Множество имеет гиперарифметическую (арифметическую) сложность, если проблема принадлежности произвольного элемента этому множеству эквивалентна выполнимости гиперарифметического (арифметического) отношения.

Если в формулировке проблемы Морли все вхождения подслова «разрешим» заменить на «арифметичн», то получится открытый вопрос, впервые предложенный Гончаровым и Милларом: любая ли модель эрен-фойхтовой теории с арифметическими типами будет арифметической?

Как показал Миллар [1], этот вопрос имеет положительный ответ, если дополнительно потребовать, чтобы любое обогащение теории конечным числом констант оставалось эренфойхтовой теорией. Однако требование это является существенным. См., например, Вудроу [33]: существу.

3> Здесь и далее предполагается, что все рассматриваемые объекты, в частности, модели (не более, чем) счётные. ет эренфойхтова теория с четырьмя моделями, константное расширение которой имеет и моделейПеретятькин [24]: существует эренфойхтова теория с тремя моделями, любое константное расширение которой имеет ш моделей.

Для гиперарифметической эренфойхтовой теории можно показать (см., например, [7]), что все модели будут иметь гиперарифметическую сложность.

Неожиданностью было появление результата Хусаинова, Ниса и Шора [16] о существовании теории с тремя счётными моделями, среди которых лишь насыщенная конструктивизируема. Это вместе с результатом второй главы диссертации: существует эренфойхтова теория, обладающая неконструктивизируемой моделью, такая, что и простая, и насыщенная модели конструктивизируемы — наталкивает на размышления об отрицательном решении проблемы Морли.

Изучая связь между алгоритмической сложностью малой теории с алгоритмическими сложностями её моделей, Гончаров и Хусаинов в [9] и [10] построили примеры ши о^-категоричных теорий сколь угодно большой арифметической сложности, и при этом имеющих конструкти-визируемые модели. В первой главе диссертации имеются аналогичные примеры эреифойхтовых теорий. Этот же вопрос в случае гиперарифметической сложности остаётся открытым для всех трёх классов теорий.

Упомянутые выше три типа изоморфизма моделей: простая, насыщенная и слабо насыщенная — являются классическими. На самом деле, говорить о типе изоморфизма слабо насыщенной модели уже не совсем корректно, поскольку у теории может существовать несколько неизоморфных слабо насыщенных моделей. Наличие примеров эренфойхто-вых теорий, имеющих любое количество моделей с одной стороны, и изученность лишь трёх из них — с другой, является существенным камнем преткновения для исследований по данной тематике. Сравнительно недавно, в [29], Судоплатовым была получена синтаксическая характе-ризация класса эренфойхтовых теорий. Было доказано, что в качестве параметров, задающих любую эренфойхтову теорию можно взять конечный предпорядок (с некоторыми естественными дополнительными условиями) и отображение, действующее из этого предпорядка в множество натуральных чисел (тоже с несущественными свойствами). (Назовём эти параметры параметрами эренфойхтовости.) В этой связи, вопрос о расположении разрешимых, конструктивизируемых и др. моделей друг относительно друга стал гораздо осмысленнее. Кроме того, в работе [30] Судоплатовым построены примеры теорий, обладающих произвольными наперёд заданными параметрами эренфойхтовости (более подробно результаты, связанные с этой проблематикой изложены в готовящейся к изданию книге [31]). Это обнажило весь класс вопросов, связанных со спектром вычислимых моделей теории, т. е. с взаимным расположением конструктивизируемых моделей. К сожалению, конструкция примеров из [30] чрезвычайно сложна, и попытки сразу доказывать теоремы кон-структивизируемости наталкиваются на серьёзные трудности. Но всё же некоторые частные случаи уже сейчас поддаются анализу. В третьей главе диссертации изучаются некоторые вопросы теории конструктивных моделей для эренфойхтовых теорий, имеющих первым параметром эренфойхтовости — конечный линейный порядок. В частности, из результао тов диссертации следует существование эренфойхтовой теории, имеющей сколь угодно большое число моделей, при этом конструктивизируемыми являются только модели, очень близкие, в некотором теоретикомодель-ном смысле, к насыщенной модели. Общий же вопрос характеризации спектра вычислимых моделей в случае эренфойхтовой теории остаётся открытым, равно как и в случае а>1-категоричной теории. Кроме того, в случае эренфойхтовой теории, к нему добавляется также открытый вопрос характеризации спектра разрешимых моделей.

1. Ash, С., Millar, Т., Persistently Finite, Persistently Arithmetic Theories, Proc. Am. Math. Soc., 89, 3, 487−492, 1983.

2. Ash, C., Knight, J., Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.

3. Baldwin, J., Lachlan, A., On strongly minimal sets, The Journal of Symbolic Logic, 36, 79−96, 1971.

4. Чэн, Ч. Ч., Кейслер, Г. Дж., Теория моделей, Мир, Москва, 1973.

5. Гончаров, С. С., Конструктивные модели а^-категоричных теорий, Математические заметки, 23, 885−889, 1978.

6. Гончаров, С. С., Сильная конструктивизируемость однородных моделей, Алгебра и логика, 17, 4, 363−388, 1978.

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

8. Goncharov, S., Khoussainov, В., Open Problems in the Theory of Constructive Algebraic Systems, CDMTCS Research Report Series, CDMTCS-124, 2000.

9. Гончаров, С. С., Хусаинов, Б. М., О сложности теорий вычислимых Ni-категоричных моделей, Вестник НГУ. Серия: математика, механика, информатика, 1, 2, 63−76, 2001.

10. Гончаров, С. С., Хусаинов, Б. М., Сложность теорий вычислимых категоричных моделей, Алгебра и логика, 43, 6, 650−665, 2004.

11. Handbook of Recursive Mathematics, Elsevier, 1998.

12. Harrington, L., Recursively Presented Prime Models, Journal of Symbolic Logic, 39, 305−309, 1974.

13. Hart, В., Hrushovski, E., Laskowski, M., The Uncountable Spectra of Countable Theories, Ann. Math. (2), 152, 1, 207−257, 2000.

14. Hodges, W., A Shorter Model Theory, Cambridge University Press, 1997.

15. Хисамиев, H. Г., О сильно конструктивных моделях разрешимой теории, Изв. АН Каз ССР. Сер. 1. Физика и математика, 3, 83−84, 1974.

16. Khoussainov, В., Nies, A., Shore, R., Computable Models of Theories with Few Models, Notre Dame Journal of Formal Logic, 38, 2, 165−178, 1997.

17. Knight, J., Nonarithmetical No-categorical Theories with Recursive Models, The Journal of Symbolic Logic, 59, 1, 106−112, 1994.

18. Кудайбергенов, К. Ж., О конструктивных моделях неразрешимых теорий, Сибирский математический журнал, 21, 155−158, 1980.

19. Lerman, М., Schmerl, J., Theories with Recursive Models, The Journal of Symbolic Logic, 44, 1, 59−76, 1979.

20. Marker, D., Non-E"-axiomatizable Almost Strongly Minimal Theories, The Journal of Symbolic Logic, 54, 3, 921−927, 1989.

21. Morley, M., Decidable Models, Israel Journal of Mathematics, 25, 233 240, 1976.

22. Nies, A., A New Spectrum of Recursive Models, Notre Dame Journal of Formal Logic, 40, 3, 307−314, 1999.

23. Перетятькин, M. Г., О полных теориях с конечным числом счётных моделей, Алгебра и логика, 12, 5, 550−576, 1973.

24. Перетятькин, М. Г., О теориях с тремя счётными моделями, Алгебра и логика, 19, 2, 224−235, 1980.

25. Reed, R., A Decidable Ehrenfeucht Theory with Exactly Two Hyperarithmetic Models, Ann. Pure Appl. Logic, 53, 2, 135−168, 1991.

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

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

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

29. Судоплатов, С. В., Полные теории с конечным числом счётных моделей I, Алгебра и логика, 43, 1, 110−124, 2004.

30. Судоплатов, С. В., Полные теории с конечным числом счётных моделей И, Алгебра и логика, 45, 3, 314−353, 2006.

31. Судоплатов, С. В., Проблема Лахлана, готовится к изданию, доступна в сети Интернет: http://www.math.nsc.ru/~sudoplatov/lachlan03092008.pdf.

32. Vaught, R., Denumerable Models of Complete Theories, Infinistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warshaw, 303−321, 1959.

33. Woodrow, R., Theories with a Finite Number of Coutable Models, The Journal of Symbolic Logic, 43, 3, 442−455, 1978. Работы автора по теме диссертации.

34. Gavryushkin, A., On Complexity of Ehrenfeucht Theories with Computable Model, Logical Approaches to Computational Barriers (Second Conference on Computability in Europe), Report Series, Swansea University, 105−108, 2006.

35. Гаврюшкин, A. H., Сложность эренфойхтовых моделей, Алгебра и логика, 45, 5, 507−519, 2006.

36. Gavryushkin, A., Computable Models Spectra of Ehrenfeucht Theories, Logic Colloquium 2007, Book of Abstracts, Uniwersytet Wroclawski, 4647, 2007.

37. Гаврюшкин, A. H., Спектры вычислимых моделей эренфойхтовых теорий, Алгебра и логика, 46, 3, 275−289, 2007.

38. Gavryushkin, A., Computable Models Spectra of Ehrenfeucht Theories, Logic and Theory of Algorithms, Fourth Conference on Computability in Europe, CiE 2008 Local Proceedings, University of Athens, 50−51, 2008.

39. Гаврюшкин, A. H., О конструктивных моделях теорий с линейным порядком Рудина-Кейслера, Вестник НГУ. Серия: математика, механика, информатика, 9, 2, 30−37, 2009.