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

• Попков, Роман Андреевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Попков, Роман Андреевич

Оглавление

Введение

1. Распределение счётных моделей теорий с континуальным числом типов

1.1. Примеры

1.2. Предпорядки Рудин — Кейслера

1.3. Предмодельные множества

1.4. Распределения счётных моделей теории по <ш<-последовательностям

1.5. Три класса счётных моделей

1.6. Операторы, действующие на классе алгебраических систем

1.7. Распределения простых и предельных моделей для конечных и счётных предпорядков Рудин — Кейслера

1.8. Взаимосвязь классов Р, Ь и NPL в теориях с континуальным числом типов. Распределения троек стз(Х') в классе %

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

2. Теории одноместных предикатов

2.1. Чистые теории независимых одноместных предикатов

2.2. Теории независимых одноместных предикатов с подстановкой ограниченного порядка

3. Теория группы целых чисел 65 Заключение

Введение диссертации (часть автореферата) на тему «Классификация счётных моделей полных теорий с континуальным числом типов»

Введение

Актуальность и степень разработанности темы исследования. Теория моделей как раздел математики сформировалась на стыке математической логики и алгебры в 50-х годах XX века. Предметом её изучения являются теории и алгебраические системы (структуры) и взаимосвязь между ними. Фундаментальный результат, теорема компактности для логики первого порядка, был получен А. И. Мальцевым в 1930-е годы, переоткрыт А. Тарским в 1950-е годы, и использовался А. И. Мальцевым для доказательства локальных теорем теории групп. Созданный им метод позволил дать общее решение ряда проблем, ранее решавшихся с частных позиций. А. Тарскому и Ю. Л. Ершову принадлежит целый ряд результатов относительно разрешимости и неразрешимости формальных теорий в логике первого порядка. Ю. Л. Ершову принадлежит решение классической проблемы о разрешимости элементарной теории поля р-адических чисел. Одним из вопросов теории моделей является классификация структур с точностью до элементарной эквивалентности. В. Шмелёвой получена такая классификация абелевых групп, А. Тарским — булевых алгебр, Ю. Л. Ершовым, И. Аксом и С. Коченом — ген-зелевых полей. Другой из задач теории моделей является классификация теорий но свойствам структур и наоборот. Такая классификация возможна по количеству типов в теориях (то есть множествам формул, описывающих взаимосвязь между элементами), по типу комбинаторных объектов, которые можно определить на структурах (например, бесконечные упорядочения, бесконечные деревья) и т.д. Исследования в данном направлении начались с работ Р. Воота [41], М. Морли [33] и Ч. Рыль-Нардзевского [36]. Р. Воотом было доказано, что любой неглавный тип опускается в некоторой модели. Ч. Рыль-Нардзевский показал, что полная теория является счётно категоричной тогда и только тогда, когда число п-типов (то есть, типов от п свободных переменных) конечно для любого п ^ 1. Это говорит о том, что каждая счётно категоричная теория определяется такой характеристикой, как функция Рыль-Нардзевского, ставящей каждому

натуральному п число тг-типов. Одним из результатов исследований М. Морли является доказательство гипотезы Лося о несчётной категоричности полных теорий [32]. Е. А. Палютиным получено описание категоричных универсалов, категоричных квазимногообразий, функций спектров хорновых теорий и квазимногообразий, установлен ряд результатов, относящихся к теории групп и теории модулей, основана и развита коммутативная теория моделей. При описании полных теорий возможны неизоморфные реализации этих теорий различными структурами, причём число этих реализаций может зависеть от мощности рассматриваемых структур. Следовательно, возникает так называемая спектральная функция /, ставящая в соответствие некоторой полной теории и фиксированной мощности Л мощность 1(Т, А) множества попарно неизоморфных моделей теории Т в мощности Л. Одной из основных задач теории моделей является проблема описания всех возможных спектральных функций как для некоторого класса всех теорий, так и для различных естественных его подклассов. Спектральная проблема решена для несчётных мощностей в классе всех теорий. Основные достижения по данному вопросу связаны с работами С. Шелаха [37], а окончательное решение проблемы представлено в работе Б. Харта, Э. Хрушовского и М. Ласковского [22]. В счётном случае ситуация оказалась сложнее. До сих пор не решена проблем Воота, существуют ли теории с несчётным, но не максимальных числом счётных моделей (предпринимались попытки построения примеров, опровергающих данную гипотезу [27]). Число счётных моделей активно исследовалось для различных теорий [17], [24], [26], [28], [32], [34], [35], [40] (список далеко не полный). Ряд исследований был направлен на обнаружение свойств, связанных со счётными моделями [8], [10], [16], [25], [29], [39], и счётных моделей с желаемыми теоретико-модельными и вычислимыми свойствами [4], [11], [31], [42]. Таким образом, классификация теорий и моделей является актуальной задачей. Подход к классификации счётных моделей, использующий связи между счётными моделями и между типами, предложен в работах [8], [10], [11], [13]. В статье [8] определяются гиперграфы простых моделей над реализациями типов малых теорий. На основе графовых структур моделей малых теорий устанавливаются иерархии множеств в этих гииерграфах, раскрывающие структурные связи в счётных моделях малых теорий. Обосновывается ключевая роль теоретико-графовых конструкций в построении эренфойхтовых теорий. На основе гиперграфовых конструкции классификация элементарных полных теорий с конечными предпорядками Рудин — Кейслера обобщается на класс всех малых теорий.

В статье [10] приводится синтаксическая характеризация класса элементарных полных теорий с конечным числом счетных моделей, которая является аналогом теоремы Рыль-Нардзевского о счётно категоричных теориях и основана на классификации теорий по квазииорядкам Рудин - Кейслера и функциям распределения числа предельных над типами моделей. Устанавливаются основные свойства указанных характеристик. Вводится понятие упорядоченной раскраски, исследуется роль таких раскрасок в построении теорий с конечным (> 1) числом счетных моделей, а также приводится пример а>-стабильной теории с упорядоченной раскраской, индуцирующей континуум предельных над данным типом попарно неизоморфных моделей. В статье [11] устанавливается реализуемость всех возможных параметров, приведённых в характеризационной теореме предыдущей статьи. Кроме того, в теореме 5.1 описываются квазииорядки Рудин - Кейслера в произвольных малых теориях. Целью работы [13] является обобщение классификации элементарных полных теорий с конечным числом счетных моделей относительно двух основных характеристик (предпорядков Рудин - Кейслера и функций распределения числа предельных моделей) на произвольный случай с конечным пред-порядком Рудин - Кейслера. Устанавливается, что те же самые характеристики играют ключевую роль в рассматриваемом случае, и доказывается совместность любых конечных предпорядков Рудина - Кейслера с произвольными функциями распределения /, удовлетворяющими условию rang/ С из U {а;,2ш}. В работах [2], [3] исследуются предельные модели теорий абелевых групп и унаров соответственно.

Цели и задачи. Целями данной работы являются:

1. Перенести способы классификации счётных моделей малых теорий на теории с континуальным числом типов.

2. Исследовать взаимосвязь различных счётных моделей некоторых естественных теорий.

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

1. Сформулировано условие, при котором последовательность Рудин - Кейслера для типов образует счётную модель (теорема 1.4.1).

2. Введено обобщение спектральной функции - тройка распределения числа счётных моделей сш3(Т), и охарактеризован класс теорий без простых и предельных моделей (теорема 1.5.2).

3. Введены специальные операторы на классе алгебраических систем, позволяющие

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

4. Описаны распределения простых и предельных моделей для не более чем счётных предпорядков Рудин - Кейслера (теорема 1.7.7). Показано, что любое конечное предупорядоченное множество можно реализовать в виде Ш<(Т) для теории из класса немалых теорий с простой моделью над 0 (теорема 1.7.12).

5. Описана взаимосвязь между различными классами счётных моделей (теоремы 1.8.1, 1.8.2, 1.8.4).

6. Введены операторы порождения предпорядков Рудин - Кейслера, позволяющие получить некоторые реализации иредмодельных множеств (теоремы 1.9.1, 1.9.2).

7. Исследована взаимосвязь между различными счётными моделями и найдены тройки распределения для теорий одноместных предикатов (глава 2) и теории группы целых чисел (глава 3).

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

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

Апробация работы. Результаты диссертация были представлены на международных конференциях "Мальцевские чтения" (Новосибирск, 2011, 2012, 2014, 2015), международных школах-конференциях "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлагол, 2011, 2013), международной конференции "Алгебра и математическая логика: теория и приложения" (Казань, 2014), на международной научной студенческой конференции "Студенты и научно-технические прогресс" (Новосибирск, 2012), всероссийской школе-семинаре "Синтаксис и семантика логических систем" (Улан-Удэ, 2012), Научной сессии НГТУ (Новосибирск, 2015), семинарах "Теория

моделей" Института математики им. С. JT. Соболева СО РАН.

Публикации. Результаты автора по теме диссертации опубликованы в работах [4355], при этом работы [43-45] опубликованы опубликованы в изданиях, которые входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание учёных степеней доктора и кандидата наук. Работа [46] опубликована в журнале, индексируемом в наукометрических системах (SCOPUS и т.д.). Работы [43, 46, 49, 52] написаны в неразрывном сотрудничестве с С. В. Судоплатовым.

Структура и объём диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы. Все утверждения занумерованы тройками индексов, из которых первый является номером главы, второй - номером раздела внутри главы, третий - номером утверждения в данном разделе. Объём диссертации - 78 страниц.

Благодарности. Автор от всей души благодарит своего научного руководителя Сергея Владимировича Судоплатова за постановку задачи и всестороннюю помощь при работе над диссертацией. Автор признателен участникам семинара "Теория моделей" ИМ СО РАН за множество ценных замечаний и предложений, способствовавших улучшению работы. Коллективу кафедры алгебры и математической логики НГТУ автор благодарен за неизменно доброжелательную атмосферу и поддержку.

Содержание работы. Обозначим через Тс класс всех счётных полных теорий Т, не являющихся малыми, т. е. таких, что множество S(T) типов теории Т континуально. Всюду в работе, если не оговорено противное, будем предполагать, что все рассматриваемые теории принадлежат классу % и называть такие теории немалыми или теориями с континуальным числом типов.

В теориях из класса %, вообще говоря, нет соответствия между типами и простыми над кортежами моделями, имеющегося для малых теорий (некоторых моделей для данной теории из класса Тс, простых над реализациями типов, может не существовать). Кроме того, континуально число попарно неизоморфных счётных моделей каждой такой теории. Однако, как будет показано в работе, в рассматриваемой ситуации структурная взаимосвязь типов позволяет распределять счётные модели теории подобно тому, как это происходит для малых теорий [8,12] и для произвольных счётных теорий одноместных предикатов (глава 2).

В начале главы 1, в разделе 1.1, приводится несколько примеров немалых теорий. Взаимосвязь между типами прослеживается с помощью предпорядка Рудин - Кейсле-Ра как показано в разделе 1.2. Известно, что если теория является малой, то эта взаимосвязь автоматически переносится на модели, простые над рассматриваемыми типами. В случае же малых теорий таких простых моделей может просто не существовать. Для такой ситуации возможно обобщение предпорядка Рудин - Кейслера, основанное на включении для конечных диаграмм ЕВ(*Ш). Сформулированы некоторые свойства, связанные с предпорядками Рудин - Кейслера в классе немалых теорий. В разделе 1.3 показано, что основные свойства данных предпорядков содержатся в понятии предмодельного множества. В разделе 1.4 сформулировано условие, при котором последовательность Рудин - Кейслера для типов образует счётную модель:

ТЕОРЕМА 1.4.1. Для любой ^-однородной модели ШТ счётной теории Т и <ш<-последовагпслъности q типов теории Т, реализующихся в модели Ш, следующие условия эквивалентны:

(1) некоторое (счётное) подмножество множества и(Ш,ц) является носителем элементарной подмодели модели Ш;

(2) q — элементарно подмодельная <ц^-последовательность.

Далее, в раздел 1.5, определяется три класса моделей: Р, Ь, NPL — простых над конечными множествами Р, предельных Ь и остальных счётных моделей NPL соответственно. Вводится некоторое обобщение спектральной функции 1(Т,ш): тройка распределения сш3(Т) = (Р(Т), Ь(Т), КРЬ(Т)) числа счётных моделей теории Т. Показано некоторые связи для моделей, принадлежащих данным классам. Известно [12], что для любой малой теории Т без конечных моделей верно равенство КРЬ(Т) = 0. Для теорий из класса Тс верен следующий критерий:

ТЕОРЕМА 1.5.2 Счётная модель Ш теории Т 6 Тс проста над некоторым конечным множеством или предельна тогда и только тогда, когда любой кортеж а Е М расширяется до кортежа Ъ £ М такого, что любая совместная формула <р(х, Ъ) является г-формулой.

Данная теорема позволяет охарактеризовать класс пр1-нулевых теорий, то есть теорий без остальных моделей.

Примеры, приведённые в разделе 1.1, показывают реализуемость в классе % троек (0,0,2Ш) и (2Ш,2Ш,0). Некоторым слиянием теорий Ттр и Т8аир реализуется тройка

(2Ш, 2W, 2Ш). Е. А. Палютин заметил, что теория Tersiup реализует тройку (1,0,2Ш). Эту же тройку реализует теория Tsjer. Дизъюнктным объединением малой теории с единственным неглавным типом и теории и теории Tsjpe реализуется тройка (ш, 1,2^). Дизъюнктным объединением малой теории с конечным (> 1) числом неглавных типов и теории Ts;pe реализуется тройка (ш, ш, 2W). Дизъюнктным объединением малой теории со счётным числом неглавных типов и теории Tsipe реализуется тройка (и, 2Ш,2Ш). Возникает вопрос, существуют ли тройки, которые не реализуются ни для какой теории. Не него отвечает

ПРЕДЛОЖЕНИЕ 1.5.4. Не существует теории Т е Тс, для которой cm3(Т) принимает какое-либо из следующих значений:

1) (Аь2"\Аз), где Al5 А3 <2";

2) (2W, А2, А3); где А2, А3 < 2Ш.

В книге [9] описаны возможные способы построения теорий с заданными свойствами. Одним из таких способов является применение операторов. В разделе 1.6 приводится описание следующих операторов: континуального разбиения с-Partition, выделения счётного подмножества cj-AIIoc (запрета движения вниз banDown), запрета движения вверх banllp, построения предельных моделей typeLim над типом, построения предельных моделей seqLim над <rk-последовательностью.

В разделе 1.7 описываются распределения простых и предельных моделей для конечных и счётных предпорядков Рудин - Кейслера.

ТЕОРЕМА 1.7.7. Для любого конечного предупорядоченного множества (X; <) и любой функции /: -» и> U {ц;,2ш}7 удовлетворяющей условию f(x) > 0 при \х\ > 1 (где х^у^х<уиу< х), существует теория Т Е % (не имеющая простой модели) и изоморфизм g: (X; <) ^ RK(Т) такие, что IL(g(5)) = f(x) для любого х 6

Согласно теореме 1.7.7, для класса Тс положительные значения Р(Т) могут определяться простыми моделями, не являющимися простыми над 0. Модификацией приведённого доказательства можно реализовать произвольное конечное предупорядочен-ное множество (X; <} с наименьшим элементом в виде RK(T) для теории Т ЕТС, имеющей простую модель над 0

ТЕОРЕМА 1.7.12. Пусть (X, <) — не более чем счётное предупорядочениое множество, /: Y —У и U {о>, 2Ш} — функция, у которой Y — не более чем счётное множество <-последовательностей, т. е. последовательностей в X, образующих <-цепи, и

выполняются следующие условия:

а) f(y) > 1, если никакая коконечная подпоследовательность последовательности у не состоит из одинаковых элементов;

б) f{y) < fil/), если у' — подпоследовательность последовательности у;

в) f(y) — f{y')j есЛи У = (Уп)пач} и у' = (у'п)п<=ч> — последовательности, для которых найдутся такие числа k, m £ и, что уь+п = у'т+п> начиная с некоторого п.

Тогда существует теория Т € % и изоморфизм g: {X, <) —> RK(T) такой, что каждое значение f(y) равно числу предельных моделей над <rk-последовательностью {Яп)пеи>, соответствующей <-последовательности у = (уп)пеш? где д(уп) — тип изоморфизма модели ffîqn, п G со.

В разделе 1.8 описываются взаимосвязи между различными классами счётных моделей. Верны следующие теоремы:

ТЕОРЕМА 1.8.1. Пусть (Х,<) — не более чем счётное предупорядоченное множество, в котором X представлено в виде дизъюнктного объединения некоторых множеств Р и npl, /: f —> gj u {w, 2ш} — функция, у которой Y — не более чем счётное множество (Р, ^-последовательностей, т. е. последовательностей в Р, образующих <-цепи, и выполняются следующие условия:

а) f(y) > 1? если никакая коконечная подпоследовательность последовательности у не состоит из одинаковых элементов;

б) f{y) < f(y')> если у' — подпоследовательность последовательности у;

в) f(y) = f{y'); если у = (уп)пеш и У' = (у'п)пеи ~~ последовательности, для которых найдутся такие числа k,m Ей), что Ук+п — у'т+п> начиная с некоторого п.

Тогда существует теория Т и изоморфшзм g: (X, <) ^СМо^) на некоторую подсистему СМ0(Т) = (СМ0(Г);<КК) системы СШ{Т), гдеСМ0(Г) С P(T)UNPL(T), удовлетворяющий следующим условиям:

1) g(P) = Р(Т), д(NPL) = СМо(Т) П NPL(T);

2) каждое значение f(y) равно числу предельных моделей над <rk-последовательностью (qn)new, соответствующей <-последовательности у = (уп)пеш, где д(уп) — тип изоморфизма модели 9Л9п, п £ со.

ТЕОРЕМА 1.8.2. В условиях теоремы 8 существует теория Т £ % и изоморфизм g: (X, <)=>СМ0(Т) на некоторую подсистему СМо(Т) = (СМо^); <rk) системы СМ(Т), где СМ0(т') с р(т) UNPL(t), удовлетворяющий следующим условиям:

1) д(Р) = СМо(Т) П Р(Г), д(ШЪ) = ОТЦТ);

2) каждое значение /(у) равно числу предельных моделей над <нк-последовательностью (<}п)пеи, соответствующей <-последовательности у — (уп)п€и>, где д(уп) ~ тип изоморфизма модели Шдп, п € из.

Суммирует предыдущие результаты

ТЕОРЕМА 1.8.4. В предположении континуум-гипотезы, для любой теории Т из класса % тройка ст3(Т) принимает одно из следующих значений:

1) (2Ш,2Ш, Л), где \е из и {ш,2ш};

2) (0,0,2");

3) (Ль Л2,2й), гдеХ^ > 1, \и Л2 6 ш и 2"}.

Все указанные значения имеют реализации в классе %.

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

ТЕОРЕМА 1.9.1. Для любого конечного предупорядоченного множества Хо = №;<о,/о) с раскраской /0: <о —> и обладающего свойством раскраски первого

(второго) рода, а также для любого счётно порождённого предупорядоченного множества СШ(Ло) первого (второго) рода существует счётная теория Т £ %, для которой некоторое ограничение системы Ш<Т(Т), обогащённое формулами, обеспечивающими подчинение типов и раскраску дуг, изоморфно системе о).

ТЕОРЕМА 1.9.2. Для любого счётного ограничения (Х\ <) предмодельного множества существует теория Т ЕТС, для которой некоторое счётное ограничение системы ИКТ(Т) изоморфно системе (Х\ <).

Глава 2 посвящена классификации полных теорий одноместных предикатов. В разделе 2.1 исследуются чистые теории одноместных предикатов. С помощью понятия плотного множества типов для теории 2]ир (где в определении плотного множества не упоминается предикат Ях) описывается (глава 2) предупорядоченное по отношению <ик множество М типов изоморфизма счётных моделей теории 7]ир. Каждая счётная модель задаётся счётным числом реализаций типов некоторого плотного множества. При этом модель ПЛ1 подчиняется модели 9Л2 тогда и только тогда, когда каждый 1-тип р, реализуемый в реализуется в Ш?2 и число реализаций каждого типа р в

ЯЯх не превосходит числа реализаций того же типа в ШТг- Поскольку плотность множества типов сохраняется при произвольном удалении или добавлении одного 1-типа, у множества М нет ни минимальных, ни максимальных элементов. Верна

ТЕОРЕМА 2.1.4. Пусть и Т^ — счётные теории одноместных предикатов, тогда соотношение СМ(71) ~ СМ(Т2) равносильно одному из следующих трёх условий:

1) Т\ и Тг имеют одинаковое, не более чем счётное, число неглавных 1-типов;

2) Т\ и Тг имеют континуальное число типов и простую модель;

3) Т\ и Тг имеют континуальное число типов и не имеют простой модели. С учётом троек распределения, полученных в работе [1], верна следующая ТЕОРЕМА 2.1.5. Для счётных теорий одноместных предикатов возможны следующие значения троек распределения:

1) (1,0,0) — для малой теории без неглавных 1-типов;

2) (а», 1,0) — для малой теории с одним неглавным 1 -типом;

3) 0) — для малой теории с конечным > 1 числом неглавных 1-типов;

4) (а;,2ш,0) — для малой теории со счетным числом неглавных 1-типов;

5) (2^,2^,0) или (0,0,2"') — для теории с континуальным числом типов.

В разделе 2.2 для теорий одноместных предикатов с подстановкой ограниченного порядка сформулирована теорема 2.2.1, аналогичная тереме 2.1.4.

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

ТЕОРЕМА 3.0.6. Если счётная модель Ш |= ТЬ ((X, +, 0)) содержит элементарную подмодель которая является простой над некоторым кортежем, то либо проста над некоторым кортежем, либо предельна.

Предыдущая теорема говорит о том, где не стоит искать не простые и не предельные модели. Теоремы 3.0.4, 3.0.6, 3.0.7 суммирует

СЛЕДСТВИЕ 3.0.8. ст3(ТЬ((2,+,0») = (2м, 2", 2м).

Заключение содержит список основных результатов, полученных в работе.

Глава 1.

Распределение счётных моделей теорий с континуальным числом типов

1.1. Примеры

Напомним некоторые основные примеры теорий с континуальным числом типов [6,7]:

1) теория ТЪ((М; +, •)) стандартной модели арифметики на натуральных числах (для любого подмножества А множества Р всех простых чисел совместно множество формул Ф(.т), описывающее делимость элемента на любое число из А и отсутствие делимости на любое число из Р\ А);

2) теория ТЬ((Ж;+, 0)) (имеется континуум 1-типов но той же причине, что и в предыдущем примере);

3) теория упорядоченных полей +, •, <)) (имеется 2Ш сечений для множества рациональных чисел);

4) теория ТВ(}ир счётного множества последовательно делимых одноместных предикатов Б^Р, 5 € 2<ш, задаваемая следующими аксиомами:

ЗбФ)->£ъ(х), ее {0,1}; 12

5) теория Г;ир счётного множества независимых одноместных предикатов к € из, задаваемая всевозможными аксиомами

Зж (Рф) А ... А Р\т{х) А ^Рп(х) А ... А

{¿1,... , гт} П ... , = 0 (континуальное число 1-типов достигается за счёт совместности любого множества формул {Р^к\х) |&£о;},<5€2и;);

6) (Пример предложен Е. А. Палютиным) Теория Тегв;,ф счётного множества последовательно независимых одноместных предикатов к £ из, с отношением эквивалентности задаваемая следующими аксиомами:

а) существует бесконечно много Е-классов, и каждый Е-класс бесконечен;

б) для любого к 6 ш существует единственный Е'-класс, содержащий бесконечно много решений каждой формулы Р(5" (х) А ... А Р^ (х), ..., 5к £ {0,1}, и не пересекающийся с отношениями Р, , г > /с; имеется простая модель, и эта модель состоит лишь из этих ^-классов;

континуальное число 1-типов достигается в ¿'-классах, пересекающихся со всеми предикатами Р*., к £ ш;

7) теория Т^ счётного множества последовательно независимых отношений эквивалентности Еп \ п £ из, задаваемая следующими аксиомами:

а) I- Еп+1(х, у) Ео(х, у), п£ из-,

б) |= Ух, у(Е0(х, у) 3г(Ет(х, г) А Еп(г, у))), тфщ

в) каждый класс является бесконечным, а каждый Еп+\-класс является одноэлементным или бесконечным, п £ ш;

г) если .Е^-ц-класс X содержится в .Ео-классе У, то У состоит из бесконечного числа -Бп+1-классов, каждый из которых является одноэлементным или бесконечным, пбш;

д) если Хп+х — бесконечный -класс, содержащийся в Е'о-классе У, то У представляется в виде объединения бесконечных пересечений Х\ П ... П Хп П Хп+1 для ¿^-классов Хг, 1 < г < щ при этом для любых 8* е {0,1} бесконечны множества Х^.-.П^ПХ^П У,п£и;

е) для любого п £ из имеется ровно один £о-класс, содержащий бесконечные Е\-,..., Е^-классы и одноэлементные ^„-классы, п < т\ имеется простая модель, и эта модель состоит лишь из этих ¿о-классов;

континуальное число 2-типов достигается в .Е^-классах, содержащих бесконечные Еп+1-классы, п 6 и.

Системы (М; +, •) и ((Ц); +,-,<) являются простыми (поскольку носители этих систем совпадают с <1с1(0)), система (2/,+,0) является простой над любым своим ненулевым элементом (но не проста над 0).

Теория Т8(-ыр имеет простую модель, и эта модель опускает тип ргх(х), выводимый из множества формул, описывающих неограниченную делимость для формулы по-

средством ^-¿(х). Более того, теория Т^цр имеет простую модель над любым конечным множеством, и тем самым имеет континуум попарно неизоморфных моделей, каждая из которых проста над некоторым кортежем.

Теория Т;ир не имеет простой модели ни над каким конечным множеством, а теории ^егешр и Г8;ег, имея простые модели над пустым множеством, не обладают ни одной простой моделью над неглавными типами.

Список литературы диссертационного исследования кандидат наук Попков, Роман Андреевич, 2015 год

Библиография

[1] Байкалова К. А. О некоторых гиперграфах простых моделей и порождаемых ими предельных моделях // Algebra and Model Theory 7. Collection of papers, НГТУ, Новосибирск, 2009., С. 6-17.

[2] Байкалова К. А. Предельные модели теорий абелевых групп // Algebra and Model Theory 8. Collection of papers, НГТУ, Новосибирск, 2011., С. 9-12.

[3] Байкалова К. А. Предельные модели теорий унаров // Вестник Омского университета, 2014, № 2 (72), С. 10-14.

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

[5] Ершов Ю. Л., Палютин Е. А. Математическая логика. ФИЗМАТЛИТ, Москва, 2011.

[6] Кейслер Г., Чэн Ч. Ч. Теория моделей. Мир, Москва, 1977.

[7] Справочная книга по математической логике: Ч. 1. Теория моделей. / Под ред. Дж. Барвайса. Наука, Москва, 1982.

[8] Судоплатов С. В. Гиперграфы простых моделей и распределения счётных моделей малых теорий // Фундаментальная и прикладная математика, 2009, Т. 15, № 7., С. 179-203.

[9] Судоплатов С. В. Классификация счётных моделей полных теорий. Ч II. Изд-во НГТУ, Новосибирск, 2014.

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

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

[12] Судоплатов С. В. Проблема Лахлана. Изд-во НГТУ, Новосибирск, 2009.

[13] Судоплатов С. В. О числе счётных моделей полных теорий с конечными предпо-рядками Рудина - Кейслера // Сиб. матем. журн., 2007., Т. 48, № 2., С. 417-422.

[14] Судоплатов С. В., Овчинникова Е. В. Математическая логика и теория алгоритмов. Изд-во НГТУ, Новосибирск, 2010.

[15] Фукс Л. Бесконечные абелевы группы. Т. 1. Мир, Москва, 1974.

[16] Baizhanov В. S., Sudoplatov S. V., Verbovskiy V. V. Conditions for non-symmetric relations of semi-isolation // Siberian Electronic Mathematical Reports, vol. 9 (2012), pp. 161-184.

[17] Baldwin J. Т., Lachlan A. H. On strongly minimal sets //J. Symbolic Logic, vol. 36 (1971), pp. 79 96.

[18] Baldwin J. Т., Blass A. R., Glass A. M. W., Kueker D. W. A 'natural' theory without a prime model // Algebra Universalis, vol. 3 (1973), pp. 152-155.

[19] Baldwin J. Т., Plotkin J. M. A topology for the space of countable models of a first order theory // Zeitshrift Math. Logik. and Grundlagen der Math., vol. 20 (1974), pp. 173-178.

[20] Baldwin J. T. Fundamentals of stability theory (Perspectives in Mathematical logic), Springer-Verlag, Berlin, 1988.

[21] Casanovas E. The number of countable models. University of Barcelona, 2012, (Preprint).

[22] Hart В., Hrushovski E., Laskowski M. S. The uncountable spectra of countable theories 11 Ann. Math., vol. 152 (2000), pp. 207-257.

[23] Hodges W. Model theory (Encyclopedia of mathematics and its applications: v. 42). Cambridge University Press, 1993

[24] Hrushovski E. Finitely based theories //J. Symbolic Logic, vol. 54 (1989), pp. 221-225.

[25] Ikeda K. Pillay A., Tsuboi A. On theories having three countable models // Math. Logic Quarterly, vol. 44 (1998), pp. 161-166.

[26] Kim B. On the number of countable models of a countable supersimple theory // J. London Math. Soc., vol. 60 (1999), pp. 641-645.

[27] Knight R. W. The Vaught conjecture: A counterexample. Oxford University, Oxford, 2002, (Preprint).

[28] Lachlan A. H. On the number of countable models of a countable superstable theory //, Proc. Int. Cong. Logic, Methodology and Philosophy of Science, North-Holland, Amsterdam, 1973, pp. 45-56.

[29] Lempp S., Slaman T. The complexity of the index sets of H0-categorical theories and of Ehrenfeucht theories // Contemporary Mathematics. Vol. 425. Advances in logic, Amer. Math. Soc., Providence, 2007, pp. 43-47.

[30] Marker D. Model Theory: An Introduction (Graduate texts in mathematics; 217). Shpringer-Verlag, New-York, 2002.

[31] Millar T. Pure Recursive Model Theory // Handbook of Computability Theory, ed. E. R. Griffor, Elsevier Science B. V., 1999, pp. 507-532.

[32] Morley M. The number of countable models //J. Symbolic Logic, vol. 35 (1970), pp. 14-18.

[33] Morley M. D. Categoricity in power // Trans. Amer. Math. Soc., vol 114 (1965), pp. 514-538.

[34] Newelski L. Vaught's conjecture for some meager groups // Israel J. Math., vol. 112 (1999), pp. 271-300.

[35] Pillay A. Countable models of stable theories // Proc. Amer. Math. Soc., vol. 89 (1983), pp. 666-672.

[36] Ryll-Nardzewsky C. On the Categoricity in Power ^ // Bull. Acad. Pol. Sci. Ser. Math. Astr. Phys., vol. 7 (1959), pp. 545-548

[37] Shelah S. Classification Theory and the Number of Non-Isomorphic Models. North-Holland, Amsterdam, 1990.

[38] Sudoplatov, S. V. On Rudin-Keisler preorders in small theories / / Algebra and Model Theory 8. Collection of papers. NSTU, Novosibirsk, 2011, pp. 94-102.

[39] Tanovic P. Theories with constants and three countable models // Archive for Math. Logic, vol. 46 (2007), pp. 517-527.

[40] Vaught R. Denumerable models of complete theories // Infinistic Methods, Pergamon, London, 1961, pp. 303-321.

[41] Vaught R. L. Models of complete theories // Bull. Amer. Math. Soc., vol. 69 (1963), pp. 299-313.

[42] Woodrow R. E. Theories with a finite number of countable models //J. Symbolic Logic, vol. 43 (1978), pp. 442-455.

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

[43] Попков Р. А., Судоплатов С. В. Операторы порождения предпорядков Рудин -Кейелера в классе теорий с континуальным числом типов / / Известия Иркутского государственного университета. Серия: Математика, 2013, Т. 6, № 2, С. 48-56.

[44] Попков Р. А. О простых над конечными множествами и предельных моделях теории аддитивной группы целых чисел // Вестник Омского университета, 2014, № 2 (72), С. 34-36

[45] Попков Р. А. Распеделение счетных моделей теорий группы целых чисел // Сибирский математический журнал, 2015, Т. 56, № 1, С. 185-191.

[46] Попков Р. А., Судоплатов С. В. Distributions of countable models of complete theories with continuum many types // Siberian Electronic Mathematical Reports, 2015, Vol. 12., R 267-291., http://semr.math.nsc.ru/vl2/p267-291.pdf.

[47] Попков Р. А. Алгебры 1-типов теории целых чисел, индуцируемые групповой операцией // Вестник Карагандинского университета. Серия "Математика", 2013, Т. 69, № 1, С. 81-85.

[48] Попков Р. А. Классификация счётных моделей полных теорий одноместных предикатов с подстановкой ограниченного порядка // Algebra and Model Theory 8. Collection of papers, НГТУ, Новосибирск, 2011. С. 73-82.

[49] Попков Р. А., Судоплатов С. В. О распределениях счетных моделей теорий с континуальным числом типов // Синтаксис и семантика логических систем: Материалы 4-й Российской школы-семинара, ФГБОУ ВПО "Восточно-Сибирская государственная академия образования", Иркутск, 2012, С. 98-102.

[50] Попков Р. А. Счётные модели полных теорий одноместных предикатов с подстановкой ограниченного порядка // Международная конференция "Мальцевские чтения", посвященная 60-летию чл.-кор. С. С. Гончарова, 11-14 окт. 2011 г. Тезисы докладов, Новосибирск, 2011, С. 87.

[51] Попков Р. А. Конечные 1-предпорядки Рудин-Кейслера счётных полных теорий с континуальным числом типов // Материалы юбилейной 50-й международной

научной студенческой конференции "Студенты и научно-технической прогресс": Математика. Новосиб. гос. ун-т., Новосибирск, 2012, С. 19.

[52] Popkov R. A., Sudoplatov S. V. On realizations of Rudin-Keisler preorders for theories with continuum many types // Международная конференция "Мальцевские чтения", 12-16 ноября 2013 г. Тезисы докладов. Новосибирск, 2012, С. 146.

[53] Попков Р. А. О числе простых и предельных моделей теории аддитивной группы целых чисел // "Алгебра и математическая логика: теория и приложения": материалы конф., Казань, 2-6 июня 2014 г., С. 118-119.

[54] Попков Р. А. Распределение счетных моделей теорий одноместных предикатов // Новосибирск. Международная конференция "Мальцевские чтения", 10-13 ноября 2014 г. Тезисы докладов, Новосибирск, 2014, С. 132.

[55] Попков Р. А. О счётных моделях теорий абелевых групп с коненчными инвариантами Шмелёвой // Новосибирск. Международная конференция "Мальцевские чтения", 3-7 мая 2015 г. Тезисы докладов, Новосибирск, 2015, С. 195.