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

• Автор: Гаврюшкин, Александр Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 77 с.

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

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

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

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

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

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

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

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

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

2.2.4. ТЛ(91) — требуемая теория

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 модели мощности которых изоморфны. В этом случае ш(Т) = ш.
Модель называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел ш, а операции и предикаты — равномерно вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами — обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка. ^ Говорим, что произвольная модель конструкти-визируема, если она изоморфна некоторой вычислимой модели.
Главнейшими вопросами теории конструктивных моделей являются: проблема существования вычислимой модели, количество конструктиви-зируемых моделей данной теории, какие модели являются конструкти-визируемыми. Вопросы эти не праздны. К примеру, для классов эрен-фойхтовых и ^^категоричный теорий на сегодняшний день нет удовлеТЭти два подхода (вычислимость и конструктивность) можно охарактеризовать как западный и советский соответственно.

параметром эренфойхтовости, а функцию / — вторым параметром эренфойхтовости.
Определение 70. Теория Т называется эренфойхтовой теорией с параметрами эренфойхтовости (Х,ф), если существует изоморфизм д? : X —> КК(Т), и для всех х £ X/ ~ выполнено 1Ь[чр{х)) = ф(х).
Определение 71. Пусть Т — эренфойхтова теория с параметрами эренфойхтовости (Х,ф).
Спектром разрешимых моделей эренфойхтовой теории ЯОМ{Т) назовём пару {У,д), где У = {ж 6 X | элементу х соответствует3) разрешимая модель теории Т}; 5/ = 5д,4) (д(х) = тп <4- над моделями, соответствующими3^ элементам из х, имеется в точности тп разрешимых предельных неизоморфных моделей теории Т).
Спектром вычислимых моделей эренфойхтовой теории БСМ(Т) назовём пару (У, д), где У = {х £ X [ элементу х соответствует3) конструк-тивизируемая модель теории Т}; 6/ = 6д, (д(зТ) — тп О над моделями, соответствующими3) элементам из х, имеется в точности тп конструкти-визируемых предельных неизоморфных моделей теории Т).
Вопрос 72. Описать множества ЗОМ{Т) и БСМ(Т) для произвольной эренфойхтовой теории Т.
Как уже отмечалось во Введении, вопрос этот отнюдь не прост.
В работе Судоплатова [30] для произвольных параметров эренфойхтовости (X, /) построена эренфойхтова теория Т с параметрами эрен3)В смысле изоморфизма <р из определения 70.
4) Через 6 обозначается область определения.