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

На правах рукописи

Гаврюшкин Александр Николаевич

ВЫЧИСЛИМЫЕ МОДЕЛИ ЭРЕНФ ОЙХТОВЫХ ТЕОРИЙ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

а-''

. г,

Новосибирск-2009

003471412

Работа выполнена в Новосибирском государственном университете

Научный руководитель: доктор физико-математических наук, профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

Официальные оппоненты: доктор физико-математических наук, доцент Судоплатов Сергей Владимирович

доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллинович

Ведущая организация: Казанский государственный университет

Зашита диссертации состоится 18 июня 2009 г. в 14 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им.С.Л.Соболева СО РАН по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан «15» мая 2009 г.

Учёный секретарь диссертационного совета

кандидат физико-математических наук/л£^ А.Н. Ряскин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Модель называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел о>, а операции и предикаты — равномерно вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми

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

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

Множество формул назовём разрешимым, если существует алгоритм, проверяющий принадлежность произвольной формулы данному множеству. Модель 21 разрешима, если найдётся алгоритм, отвечающий на вопрос 21 [= у(оо,..., а„) равномерно по <р, ао,..., апУ Для ш- и иг-категоричных теорий имеется замечательный результат Харрингтона [6] и Хи-самиева [7] об эквивалентности разрешимости теории разрешимости всех её моделей. Последнее же, в свою очередь, равносильно существованию разрешимой модели этой теории. В то время, как для эренфойхтовых теорий сначала Ла-хлан и Морли [8] построили пример разрешимой теории с шестью моделями, среди которых имеются неразрешимые, а затем Перетятькин [9] обнаружил серию примеров разрешимых эренфойхтовых теорий, имеющих любое число моделей,

^Эти два подхода (вычислимость и конструктивность) можно охарактеризовать как западный и советский соответственно.

2' Конструктивизируемость модели эквивалентна существованию такого алгоритма лишь для бескванторных формул <р.

среди которых лишь одна разрешима. Во всех упомянутых примерах неразрешимые модели получаются за счёт наличия неразрешимых типов. В той же статье Морли [8] имеется естественный в этом свете вопрос, который открыт до сих пор, давно стал фольклором и хорошо известен под названием

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

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

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

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

3> Здесь и далее предполагается, что все рассматриваемые объекты, в частности, модели (не более, чем) счётные.

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

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

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

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

вна самом деле, говорить о типе изоморфизма слабо насыщенной модели уже не совсем корректно, поскольку у теории может существовать несколько неизоморфных слабо насыщенных моделей.

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

Научная новизна. Все основные результаты диссертации являются новыми.

Основные результаты диссертации.

1. Построен пример эренфойхтовой теории, имеющей любые наперёд заданные число моделей и арифметиче-

скую сложность, при этом обладающей конструктиви-зируемой моделью.

2. Построен пример эренфойхтовой теории, имеющей некоструктивизируемую модель, с конструктивизируе-мыми простой и насыщенной моделями.

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

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

Апробация работы. По результатам диссертации были сделаны: пленарный доклад на конференции «Мальцев-ские чтения 2007» (Новосибирск, Россия), доклады на конференциях «Computability in Europe 2008» (Афины, Греция), «Logic Colloquium 2007» (Вроцлав, Польша), «Computability in Europe 2006» (Свонси, Великобритания), доклад на «Международной студенческой конференции 2006», отмеченный дипломом первой степени, «Asian Logic Conference 2005» (Новосибирск, Россия). Кроме того, результаты докладывались на совместных семинарах НГУ и ИМ СО РАН «Конструктивные модели», «Алгебра и логика», на совместном семинаре ИМ СО РАН (Россия) - The University of Notre Dame (США) «Constrictive models», а также на школе-семинаре ИМ СО РАН «Workshop Computable Models and Numberings».

Публикации. Основные результаты опубликованы в работах [15]—[20].

Структура и объём диссертации. Диссертация состоит из введения, трёх глав и списка литературы (39 наименований). Объём диссертации 77 стр.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

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

Теорема 1. Для всех натуральных чисел га > 3 « ш ^ 1 существует теория Эренфойхта Т, эквивалентная по Тьюрингу

0М

и имеющая с точностью до изоморфизма п счётных моделей, одна из которых конструктивизируема.

Как в формулировке этой теоремы, так и далее, множества формул отождествляются с множествами их гёде-левских номеров. Под «эквивалентностью по Тьюрингу» и «0('«)» понимается следующее:

Определение 1. Множества А С и> и В С и> эквивалентны по Тьюрингу, если алгоритм вычисления характеристической функции множества А сводим к алгоритму вычисления характеристической функции множества В, и обратно: алгоритм вычисления характеристической функции множества В сводим к алгоритму вычисления характеристической функции множества А.

Определение 2. Обозначим через 0(1) множество всех натуральных чисел п, таких, что алгоритм с номером п останавливается через конечное число шагов, если на вход было подано число га. Пусть 0<-т~1\ определено для т > 1, обозначим через 0(т) множество всех натуральных чисел п, таких, что алгоритм относительно оракула 0(т-1) с номером п останавливается через конечное число шагов, если на вход было подано число п.

Вторая глава имеет своей целью изучение вопроса: «Какие модели эренфойхтовой теории могут быть конструктиви-зируемы?» — в его классическом понимании, т.е. при ограничении тремя типами изоморфизма счётных моделей.

Определение 3. Модель 21 называется элементарной подмоделью модели 23 (обозначается 21 ^ 55), если для любой формулы (р и любых элементов оо,..., ап из модели 21 выполнено 211= ср(а0, ■.., ап) 93 |= <р(а0,..., ап).

Определение 4. Модель 21 теории Т называется простой, если для любой модели 23 \= Т существует <£ X 03, т. ч. 21 = <£.

Определение 5. Модель 21 теории Т называется насыщенной, если для любой модели 23 [= Т существует € Ь 23, т. ч. 21 = С.

В насыщенной модели реализуется любой тип, совместный с теорией. Но не любая модель, реализующая все типы является насыщенной.

Определение 6. Модель 21 теории Т называется слабо насыщенной, если в 21 реализуется любой тип, совместный с Т.

Основными результатами второй главы являются теоремы 2 и 3.

Теорема 2. Существует эренфойхтова теория Т, т. ч. единственная конструктивизируемая модель этой теории не является ни простой, ни насыщенной, ни слабо насыщенной.

Теорема 3. Существует эренфойхтова теория Т, т. ч. простая и насыщенная модели теории Т конструктиви-зируемы, и существует неконструктивизируемая модель теории Т.

Третья глава посвящена вопросу разрешимости и вычислимости моделей эренфойхтовой теории в терминах харак-теризационной теоремы Судоплатова. Обратимся сначала к работе [13], где и доказана упомянутая теорема, для введения необходимых определений.

Через Ш1р обозначим класс (изоморфных) простых над реализацией типа р моделей, т. е. Шр = {ЙЛй| существует модель 91 [= р(а), (9Яа, а) — простая модель теории Т/г((91, а))}, где Т^(21) = {<£ 1211= </?}.

Определение 7. Тип р не превосходит тип q по предпоряд-ку Рудина-Кейслера (р ^як ?), если Шя |= рУ

Р ~як <лк 9 & ? <як р)-6)

Обозначим через ЯК[Т) множество типов изоморфизма моделей Шр по всем р € 5(Т). Отношение г^дк естественным образом переносится на множество ЯК(Т), поэтому индуцированное отношение будем обозначать так же: & само множество ЯК(Т) считать предупорядоченным.

Определение 8. Тип р теории Т называется властным, если из того, что р реализуется в некоторой модели Ш теории Т следует, что в ЯЛ реализуются все типы из 5(Т).

Определение 9. Последовательность 9Я0 ^ ^ ... называется элементарной цепью над типом р, если ЯЯ„ = Шр для всех п бы,

Определение 10. Модель Ш называется предельной над типом р, если = и ШП) для некоторой элементарной над

типом р цепи (ШТ„)пеи„ но ЗЯ Щ Шр.

5)Равносильно Шр ~< Шч.

6'В случае, когда типы р п д находятся в некотором отношении по Д-К-порядку, говорят, что и модели Шр и находятся в этом же отношении.

Для М е ЯК(Т)/ обозначим через 1Ь{М) число попарно неизоморфных моделей, предельных над элементами из М.

Теорема 4. (СудоПЛАТОВ [13]). Следующие условия эквивалентны:

1. и}{Т) <ш;

2. |5(Г)| = ш, \Ш{Т)\ < и, ЩМ) < ш для всех М € ЯК(Т)/ ~як.

Главными результатами третьей главы диссертации являются теоремы 5 и 6.

Определение 11. Модель 371 (= Т называется квазипростой, если она проста над реализацией некоторого типа теории Т.

Обозначим через Ьп линейный порядок, состоящий из п + 1 элемента: {а;0 < х\ < ... < хп}.

Теорема 5. Пусть Существует эрен-

фойхтова теория Тп, для которой 11К(Тп) = Ьп, при этом, модели, соответствующие элементам хо,х\,... порядка Ьп, разрешимы, модели, соответствующие элементам Хк+1,... ,хп не конструктивизируемы.

Теорема 6. Для любого 1 ^ п € ш существует эренфойх-това теория Тп, ПК(Тп) = Ьп, все квази-простые модели Т„ неконструктивизируемы, существует конструктивизи-руемая модель теории Тп.

В заключение, автор выражает огромную благодарность и сердечную признательность своему научному руководителю, Сергею Савостьяновичу Гончарову, за незабываемое приглашение в мир науки, в мир математики, определившее мои профессиональные интересы.

Список литературы

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

[2] Ash, С., Knight, J., Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.

[3] Handbook of Recursive Mathematics, Elsevier, 1998.

[4] Goncharov, S., Khoussainov,B., Open Problems in the Theory of Constructive Algebraic Systems, CDMTCS Research Report Series, CDMTCS-124, 2000.

[5] Vaught, R., Denumerable Models of Complete Theories, Infinistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warshaw, 303-321, 1959.

[6] Harrington, L., Recursively Presented Prime Models, Journal of Symbolic Logic, 39, 305-309, 1974.

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

[8] Morley, M., Decidable Models, Israel Journal of Mathematics, 25, 233-240, 1976.

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

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

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

[12] Khoussainov, В., Nies, A., Shore, R., Computable Models of Theories with Few Models, Notre Dame Journal of Formal Logic, 38, 165-178, 1997.

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

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

Работы автора по теме диссертации

[15] 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.

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

[17] Gavryushkin, A., Computable Models Spectra of Ehrenfeucht Theories, Logic Colloquium 2007, Book of Abstracts, Uniwersytet Wroclawski, 46-47, 2007.

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

[19] 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.

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

Гаврюшкин Александр Николаевич

ВЫЧИСЛИМЫЕ МОДЕЛИ ЭРЕНФОЙХТОВЫХ

ТЕОРИЙ

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Формат 60 х 84 1/16 Усл. печ. л. 1.0 Тираж 100 экз.

Подписано в печать 14.04.09 Печать офсетная Заказ № 205

Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул.Пирогова 2

Введение

1. Сложность эренфойхтовых теорий с вычислимой моделью

1.1. Маркеровские расширения.

1.2. Основной результат.

2. Спектры вычислимых моделей эренфойхтовых теорий

2.1. Некоторые конструкции.

2.2. Основной результат.

2.2.1. Некоторые пояснения.

2.2.2. Определение модели 21.

2.2.3. Конструкция вычислимой модели.

2.2.4. — требуемая теория.

3. О конструктивных моделях теорий с линейным порядком Рудина-Кейслера

3.1. Используемые определения и результаты.

3.2. Общая проблематика.

3.3. Теории с линейным порядком Рудина-Кейслера.

3.4. Конструктивные модели теорий с линейным порядком Рудина-Кейслера.

Диссертация посвящена исследованию некоторых вопросов теории конструктивных (вычислимых) моделей. Её основные результаты относятся к конструктивным моделям эренфойхтовых теорий, хотя некоторые рассматриваемые проблемы имеют более обгций характер. Теория конструктивных моделей возникла в 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, 233240, 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.