Оглавление
Введение 3
1. Сложность эренфойхтовых теорий с вычислимой моделью 10
1.1. Маркеронские расширения................................ 14
1.2. Основной результат..................................... 17
2. Спектры вычислимых моделей эренфойхтовых теорий 26
2.1. Некоторые конструкции...................................33
2.2. Основной результат......................................35
2.2.1. Некоторые пояснения..............................35
2.2.2. Определение модели 21............................37
2.2.3. Конструкции вычислимой модели....................38
2.2.4. ТЛ(91) — требуемая теория........................41
3. О конструктивных моделях теорий с линейным порядком Рудина-Кейслера 46
3.1. Используемые определения и результаты...................47
3.2. Общая проблематика......................................49
3.3. Теории с линейным порядком Рудина-Кейслера..............51
3.4. Конструктивные модели теорий с линейным порядком Рудина-Кейслера..............................................58
2
Введение
Диссертация посвящена исследованию некоторых вопросов теории конструктивных (вычислимых) моделей. Её основные результаты относятся к конструктивным моделям эренфойхтовых теорий, хотя некоторые рассматриваемые проблемы имеют более общий характер. Теория конструктивных моделей возникла в 50-ых годах XX века в работах А. И. Мальцева, М. Рабина и других выдающихся математиков, с тех пор активно развивается. Объём литературы, посвящённый этой тематике, очень велик. Б качестве наиболее важных и современных источников можно указать [7], (2) и [11). Эренфойхтовы теории являются классическим объектом не только для теории конструктивных моделей, но и, собственно, для теории моделей, где до сих пор остаются открытыми некоторые важнейшие проблемы, связанные с этим классом теорий. Из литературы но теории моделей стоит назвать [4|, [27] и [14|, по теории вычислимости — (2б| и [28|.
Основные результаты, касающиеся конструктивных моделей малых теорий, можно найти в [7], [11[. Главные современные открытые вопросы - в [8].
Напомним, что полная теория Т называется малой, если множество
3
5(Т) сё типов (под типом подразумевается максимальное совместное с теорией множество формул) счётно. Если обозначить через ш(Т) число попарно неизоморфных счётных моделей счётной полной теории Т, то Т называется эрспфойхтовой, если 3 < и(Т) < со. Если и>(Т) = 1, теория называется счётно-категоричной. Невозможность случая и>(Т) = 2 является классическим результатом Воота [32). Ещё одним подклассом класса малых теорий являются -категоричные теории, т. е. теории, любые 2 модели мощности которых изоморфны. В этом случае а>(Т) = со.
Модель называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел и/, а операции и предикаты — равномерно вычислимые функции на этом подмножестве. В свою очередь, иод вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами — обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка.^ Говорим, что произвольная модель конструкти-оизируема, если она изоморфна некоторой вычислимой модели.
Главнейшими вопросами теории конструктивных моделей являются: проблема существования вычислимой модели, количество конструктиви-зируемых моделей данной теории, какие модели являются конструкти-визируемыми. Вопросы эти нс праздны. К примеру, для классов эрен-фойхтовых и ^-категоричный теорий на сегодняшний день нет удовле-
1*Эти два подхода (вычислимость и конструктивность) можно охарактеризовать как западный и советский соответственно.
4
творительного ответа ни на один из них. Особенно сложно дело обстоит с эрепфойхховыми теориями.
Множество формул назовём разрешимым, если существует алгоритм, проверяющий принадлежность произвольной формулы данному множеству. Модель 21 разрешима, если найдётся алгоритм, отвечающий на вопрос 21 |= v>(a<h..., ап) равномерно по <р,а0,. • • ,а„.2^ Для и- и категоричных теорий имеется замечательный результат Харрингтона [12] и Хисамиева [15] об эквивалентности разрешимости теории разрешимости всех её моделей. Последнее же, в свою очередь, равносильно существованию разрешимой модели этой теории. В то время, как для эренфойхтовых теорий сначала Лахлан и Морли (21) построили пример разрешимой теории с шестью моделями, среди которых имеются неразрешимые, а затем Перетятькин [23] обнаружил серию примеров разрешимых эренфойхтовых теорий, имеющих любое число моделей, среди которых лишь простая разрешима. Во всех упомянутых примерах неразрешимые модели получаются за счёт наличия неразрешимых типов. В той же статье Морли [211 имеется естественный в этом свете вопрос, который открыт до сих пор, давно стал фольклором и хорошо известен под названием
Проблема Морли. Пусть Т — эренфойхтова теория, и асе типы, совместные с Т, разрешимы. Любая ли счётная модель теории Т разрешима?
Стоит отметить, что если с эренфойхтовой теорией совместны только
2*Конструктивизируемость модели эквивалентна существованию такого алгоритма лишь для бескванторных формул
разрешимые типы, то имеется по крайней мере 3 разрешимые модели: простая (модель, элементарно вкладывающаяся в любую другую модель теории), насыщенная (модель, в которую все остальные модели теории элементарно вкладываются) и слабо насыщенная (модель, реализующая все типы теории), но не насыщенная.3* Поэтому, в случае отрицательного ответа на проблему Морли, контр-пример должен иметь, по меньшей мере, 4 модели.
На пути решения этой проблемы возникали различные се аналоги. Например, можно переходить к более высоким уровням алгоритмической сложности. Скажем, что отношение является гиперарифметиче-ским (арифметическим), если оно получено из вычислимого отношения взятием (конечного числа раз) проекций и дополнений. Множество имеет гиперарифметическую (арифметическую) сложность, если проблема принадлежности произвольного элемента этому множеству эквивалентна выполнимости гипсрарифметического (арифметического) отношения.
Если в формулировке проблемы Морли все вхождения подслова «разрешим» заменить на «арифметичн», то получится открытый вопрос, впервые предложенный Гончаровым и Милларом: любая ли модель эрен-фойхтовой теории с арифметическими типами будет арифметической?
Как показал Миллар [1], этот вопрос имеет положительный ответ, если дополнительно потребовать, чтобы любое обогащение теории конечным числом констант оставалось эренфойхтовой теорией. Однако требование это является существенным. См., например, Вудроу [33]: сущсству-
3) Здесь и далее предполагается, что все рассматриваемые объекты, в частности, модели (не более, чем) счётные.
С
- Київ+380960830922