Содержание к диссертации
Введение
1. Распределение счётных моделей теорий с континуальным числом типов 12
1.1. Примеры 12
1.2. Предпорядки Рудин — Кейслера 15
1.3. Предмодельные множества 22
1.4. Распределения счётных моделей теории по кк последовательностям 24
1.5. Три класса счётных моделей 27
1.6. Операторы, действующие на классе алгебраических систем 31
1.7. Распределения простых и предельных моделей для конечных и счётных предпорядков Рудин — Кейслера 36
1.8. Взаимосвязь классов Р, L и NPL в теориях с континуальным числом типов. Распределения троек ст3(Т) в классе Тс 45
1.9. Операторы порождения предпорядков Рудин - Кейслера 48
2. Теории одноместных предикатов 54
2.1. Чистые теории независимых одноместных предикатов 54
2.2. Теории независимых одноместных предикатов с подстановкой ограниченного порядка 61
3. Теория группы целых чисел 65
Заключение 72
- Предпорядки Рудин — Кейслера
- Три класса счётных моделей
- Взаимосвязь классов Р, L и NPL в теориях с континуальным числом типов. Распределения троек ст3(Т) в классе Тс
- Теории независимых одноместных предикатов с подстановкой ограниченного порядка
Введение к работе
Актуальность и степень разработанности темы исследования. Теория моделей как раздел математики сформировалась на стыке математической логики и алгебры в 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/ С wU {
Цели и задачи. Целями данной работы являются:
-
Перенести способы классификации счётных моделей малых теорий на теории с континуальным числом типов.
-
Исследовать взаимосвязь счётных моделей естественных теорий.
Основные результаты диссертации.
-
Сформулировано условие, при котором последовательность Рудин - Кей-слера для типов образует счётную модель (теорема 1.4.1, опубликована в [46]).
-
Введено обобщение спектральной функции - тройка распределения числа счётных моделей стз(Т), и охарактеризован класс теорий без простых и предельных моделей (теорема 1.5.2, опубликована в [46]).
-
Введены специальные операторы на классе алгебраических систем, позволяющие получить структуры и теории с нужными свойствами варьированием входящих параметров (раздел 1.6, опубликован в [46]).
-
Описаны распределения простых и предельных моделей для не более чем счётных предпорядков Рудин - Кейслера (теорема 1.7.7, опубликована в [46]). Показано, что любое конечное предупорядоченное множество можно реализовать в виде RK(T) для теории из класса немалых теорий с простой моделью над 0 (теорема 1.7.12, опубликована [46]).
-
Описана взаимосвязь между различными классами счётных моделей (теоремы 1.8.1, 1.8.2, 1.8.4, опубликованы в [46]).
-
Введены операторы порождения предпорядков Рудин - Кейслера, позволяющие получить некоторые реализации предмодельных множеств (теоремы 1.9.1, 1.9.2, опубликованы в [43]).
-
Исследована взаимосвязь между различными счётными моделями и найдены тройки распределения для теорий одноместных предикатов (глава 2, опубликована в [48]) и теории группы целых чисел (глава 3, опубликована в [44, 45]).
Научная новизна и значимость работы. Работа имеет теоретический характер. Все основные результаты являются новыми и могут использоваться
при дальнейших исследованиях в теории моделей. Также результаты могут быть включены в материал спецкурсов для студентов и аспирантов, специализирующихся в области теории моделей.
Методы исследования. В работе используются методы теории моделей: как классические, включая теорему компактности, так и специальные, основанные на теории генерических конструкций, как семантических, так и синтаксических, а также авторские методы, базирующиеся на введенных операторах, действующих на классах алгебраических систем.
Апробация работы. Результаты диссертация были представлены на международных конференциях "Мальцевские чтения" (Новосибирск, 2011, 2012, 2014, 2015), международных школах-конференциях "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлагол, 2011, 2013, 2015), международной конференции "Алгебра и математическая логика: теория и приложения" (Казань, 2014), на международной научной студенческой конференции "Студенты и научно-технические прогресс" (Новосибирск, 2012), всероссийской школе-семинаре "Синтаксис и семантика логических систем" (Улан-Удэ, 2012), Научной сессии НГТУ (Новосибирск, 2015), семинарах "Теория моделей" Института математики им. С. Л. Соболева СО РАН.
Публикации. Результаты автора по теме диссертации опубликованы в работах [43-55], при этом работы [43-45] опубликованы опубликованы в изданиях, которые входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание учёных степеней доктора и кандидата наук. Работа [46] опубликована в журнале, индексируемом в наукометрических системах (SCOPUS и т.д.). Работы [43, 46, 49, 52] написаны в неразрывном сотрудничестве с С. В. Судоплатовым.
Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы. Все утверждения занумерованы трой-
Предпорядки Рудин — Кейслера
Актуальность и степень разработанности темы исследования. Теория моделей как раздел математики сформировалась на стыке математической логики и алгебры в 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/ CuU {ш,2ш}. В работах [2], [3] исследуются предельные модели теорий абелевых групп и унаров соответственно.
Три класса счётных моделей
Обозначим через RK(T) множество Р типов изоморфизма моделей Шр, р Є S(T), с отношением подчинения, индуцированным отношением подчинения RK между моделями DTP: RK(T) = (Р; RK)- Будем говорить, что типы изоморфизма Мі,М2 Є Р взаимоподчиняемы (Mi RK М2), если взаимоподчиняемы их представители.
Рассмотрим также отношение RK, определённое на множестве S(T) полных типов теории Т. Обозначим систему (S(T); RK) через RKT(T).
Ниже будут исследоваться взаимосвязь и свойства предупорядоченных множеств RK(T) и RKT(T), а также взаимосвязь произвольных счётных моделей теории с континуальным числом типов.
Поскольку у теорий, имеющих континуум типов, может не быть простых моделей над кортежами, в общем случае и предельных моделей может не существовать. Тем не менее, взаимосвязь счётных моделей можно прослеживать с помощью следующего обобщения предпорядка Рудин — Кейслера на типах изоморфизма счётных моделей, который также будем обозначать через RK- ЭТО обобщение расширяет предпорядок RK для типов изоморфизма простых моделей над кортежами и основано на отношении включения для конечных диаграмм FD(DT).
Пусть Mi и Мг — типы изоморфизма моделей DTi и 9 (теории Т) соответственно. Будем говорить что тип изоморфизма Mi подчиняется типу изоморфизма М2 и писать Mi RK Мь если FD(0ti) С FD(9Jt2).
Поскольку отношение RK не зависит от представителей 9Jti и Я7І2 типов изоморфизма Mi и Мг, для представителей 9Jti и 9 также будем писать 9Jti RK 9.
Обозначим через СМ(Т) множество СМ типов изоморфизма счётных моделей теории Т, снабжённое отношением предпорядка подчинения RK на этом множестве: CM(T) = (CM; RK).
Очевидно, что RK(T) С СМ(Т). Поскольку при наличии неглавных типов счётной теории найдётся модель этой теории, не представимая в RK(T) равенство RK(T) = СМ(Т) равносильно о;-категоричности теории Т.
В соответствии с определением простая модель над типом и предельная модель над тем же типом, будучи неизоморфными, взаимно подчиняются друг другу. Тем самым подчиняются друг другу и любые две предельные модели над одним и тем же типом.
Указанное обобщённое отношение подчинение позволяет классифицировать счётные модели произвольной теории одноместных предикатов (глава 2).
Как уже отмечалось, ряд примеров показывает, что, в отличие от малых теорий, для теорий с континуальным числом типов отношение подчинения может не задавать наименьшего элемента (являющегося типом изоморфизма простой модели). Кроме того, согласно следующему примеру, в иерархии типов изоморфизма счётных моделей типы изоморфизма простых над кортежами моделей могут довольно свободно перемежаться с остальными типами изоморфизма счётных моделей.
ПРИМЕР 1.2.4. Рассмотрим дизъюнктное объединение счётных одноместных предикатов До и Ді, составляющее носитель строящейся системы. Определим раскраску Col: До — ш U {оо} с бесконечным числом элементов каждого цвета. На множестве R\ зададим структуру независимых одноместных предикатов Рд., к Є ш. Полную теорию полученной системы обозначим через Т0.
Зафиксируем плотное (в естественной топологии) множество X = {qm т Є ш} 1-типов, содержащих формулу R\{y). Используя двухместные предикаты Qm, т Є ш, типроо(ж), изолируемый множеством формул {До(ж) Л-іСо1га(ж) п Є w}, и окрестности п RQ(X) Л Д —ІСО\І(Х) типа Роо(х), получаем в обогащенной сигнатуре, что все типы из г=0 множества X аппроксимируются так, что реализуемость типа Роо( ) в модели ШТ обогащенной теории влечёт реализуемость в ШТ типа qm(y) посредством главной формулы Qm(a,y), где = Роо(а) и Qm(d,y) Ь qm(y), та Є ш, а реализуемость в модели каких-либо типов из X не влечёт реализуемость в этой модели типа Роо(х). Тем самым простой модели над типом роо подчиняется простая модель над множеством А, где А состоит из реализаций типов, принадлежащих X (по одной реализации каждого типа).
В свою очередь, модель ЯТРоо подчиняется счётной модели (не являющейся простой ни над каким кортежем), которая помимо реализации типа Роо (а также реализаций типов из X) содержит счётное множество реализаций 1-типов, совместных с R\(x) и не входящих в X.
Пример 1.2.4 показывает, что отсутствие простой модели в теории может сочетаться с наличием простой модели над некоторым кортежем. Вместе с тем, как устанавливает следующее предложение, при наличии ni-формулы никакая простая над кортежем модель не может подчиняться всем счётным моделям теории.
ПРЕДЛОЖЕНИЕ 1.2.5. Для любой ni-формулы fix) и любого неглавного типа р(у) Є S(T) найдётся неглавный тип q{x) Є S(T), содержащий формулу fix) и не подчиняющий типр(у).
ДОКАЗАТЕЛЬСТВО. На основании теоремы об опускании типов найдётся счётная модель ШТ теории Т, опускающая тип р(у). Вместе с тем из совместности формулы fix) вытекает существование кортежа а, для которого Ш \= tp(a). Тип q{x) tp(a) содержит формулу f{x) и по определению не может подчинять тип piy).
Из того, что каждая совместная конъюнкция ni-формулы fix) с некоторой формулой фіх) снова является пі-формулой, число типов qix) Є SiT), содержащих формулу fix) и не подчиняющих тип piy), бесконечно. Более того, в ряде примеров, подобных приведённым выше, это число не может быть счётным, так как в противном случае можно построить счётное обогащение Т" теории Т новыми предикатами Qnix, у), п Є ш, обеспечивающее изолированность каждого типа г (ж) Є SiT ), совместного с fix), его ограничением на сигнатуру теории Т, а также подчинение типар(у) каждому типу qix). Поскольку при этом fix) остаётся пі-формулой, получаем противоречие по предложению 1.2.5.
Отметим, что если тип ріу) не подчиняется типу qix), то введением новых неза висимых предикатов Pk(x), к Є ш, превращающих некоторую окрестность типа q(x) в пі-формулу, а сам тип q(x) — в 2Ш пополнений, получается теория, для которой тип р(х) не подчиняется континууму типов. Точно так же, аналогично примеру 1 если тип р(у) подчиняется типу q(x), то в соответствующем обогащении тип р(у) подчиняется континууму пополнений типа q(x).
Заметим, что система RKT(T) может иметь минимальный кк-класс, не являющийся наименьшим. Действительно, обогащением теории Tiup двухместными предикатами, можно получить плотное множество S 1-типов, каждый из которых взаимореализуется с остальными, и при этом сохраняется отсутствие простой модели (достигается это обогащение введением счётного множества двухместных предикатов, каждый из которых отвечает за взаимореализуемость двух 1-типов из выбранного плотного множества, и эта взаимореализуемость получается посредством аппроксимаций для окрестностей выбранных типов). Множество S, а также типы, взаимно подчинённые с типами из S, и образует минимальный кк_класс. Подобными обогащениями можно получить счётное число минимальных классов.
Наряду с примером 1.2.4 и предложением 1.2.5, в примере 1.2.1 продемонстрирован механизм подчинения некоторого неглавного типа всем неглавным типам теории, имеющей континуальное число типов и не имеющей пі-формул.
Принимая во внимание представленные особенности, в следующем параграфе предлагается список некоторых основных свойств систем RKT(T) для теорий Т из класса Тс (для счётных систем RKT(T) основные свойства (счётная мощность, направленность вверх, счётность классов кк-эквивалентности, наличие наименьшего RK-класса) представлены в работе [38]).
Взаимосвязь классов Р, L и NPL в теориях с континуальным числом типов. Распределения троек ст3(Т) в классе Тс
Обратно, пусть выполняется одно из трёх условий. Тогда существует биекция : S ,(Ti)\Yi н S,;J(T2)\12 (Yi,Y"2 множества главных типов в 5 ( ),5 ( соответственно), то есть для любого типа р Є S (Ti)\Yi, f(p) = g((p)), p Є Sl(Ti). Поставим в соответствие каждой модели ЯЯ(/) модель ЯЛ(д). Пусть Х\,Х2 Є Хтг и им соответствуют модели ЯЯ(/і) и ШТ(/2). Тогда Х\ ж2 означает, что fi(p) /г(р) для всех р Є Sl(Ti). Пусть ip : XTl н Хт2, р(х\) соответствует модель Ш(д\), /?(ж2) — модель DT( jr2)- Тогда для любых типов (р) Є Sl(T2) ді((р)) 72((р)) что равносильно тому, что р(хі) ір(х2), то есть сохраняется отношение подчинения. Следовательно CM(Ti) СМ(Т2). П
Напомним [9], что дизъюнктным объединением \_\ Шп попарно непересекающихся систем 9Лга попарно непересекающихся предикатных сигнатур Т.п называется система сигнатуры [J Ип U Рп \п Є ш с носителем J Мп, Рп = Мп и интерпретациями пре-дикатных символов из Еп, совпадающими с их интерпретациями в системах ШСп. Дизъюнктным объединением теорий Тп попарно непересекающихся предикатных сигнатур Ега называется теория
Для счётных теорий одноместных предикатов возможны следующие значения троек распределения: - малая теория, сигнатура которой состоит только из одноместных предикатов. Достаточно рассматривать только 1-типы, так как нет связей между элементами. Возможные тройки распределения для То получены в работе [1]. Пусть Т\- теория одноместных предикатов с континуумом типов. Если у Т\ есть не простая и не предельная модель, то все её модели являются не простыми и не предельными, так как все модели представимы в виде дизъюнктного объединения. Таким образом, получаем тройку спіз(Ті) = (0,0,2Ш). Если Т\ имеет хотя бы одну простую модель ШТ0 (примером такой теории является Tscjup), то она имеет континуум простых моделей DTj, і Є 2Ш, так как можно добавлять реализации счётного числа неглавных типов из континуума типов, которые не были реализованы в ШТо- Тогда теория Т счётного дизъюнктного объединения \_\ 9 имеет и континуум предельных моделей. Если допустить, что у Т есть не простые и не предельные модели, приходим к противоречию с существованием простой модели. Теория То U Т\ имеет 2Ш простых и 2Ш предельных моделей, так как все модели теорий То и Т\ являются простыми или предельными. Если 9 0 = То проста над множеством А, Ш\ \= Ті проста над В, то Ш \= Т0 U Ті проста над A U В. Если хотя бы одна из моделей ШТ0 9 1 является предельной, то ШТ = WIQ U ШТі также предельна. Таким образом, получаем все возможные тройки распределений для теорий одноместных предикатов.
Рассмотрим теории одноместных предикатов, обогащенные подстановкой F ограниченного порядка L, действующий на несущем множестве счётной модели данной теории. Множества формул, изолирующие 1-типы, состоят из формул вида Зхір(х,у), где Множества формул, изолирующих гг-типы, состоят из формул вида Зуір(хі, у) тр(хг, Xj). Будем называть типы р{х) и q{x) связанными подстановкой F, если существует такое число га, что множество p(x)Uq(y) U {Fm(x) = у} совместно. Реализация некоторого типа влечёт реализацию связанного с ним.
Имеем конечное число неглавных типов рі,рг, ,Рт сигнатуры Е. Если главные типы связываются только с неглавными, то связь главного типа Colj с неглавным типом Pi описывается формулами F{x) у, СоІДж), Рі(у), где / — формула, позволяющая отличить неглавный тип рі от остальных неглавных типов. В этом случае элементы у, являвшиеся элементами неглавных типов, после обогащения сигнатуры подстановкой становятся элементами главного типа. Также, в силу теоремы компактности, образуются неглавные типы gj, реализации которых связаны только с реализациями неглавных ТИПОВ Pi.
Таким образом, при обогащении сигнатуры Е подстановкой ограниченного порядка возможно увеличение числа неглавных типов с конечного числа до счётного.
Если имеется счётное число неглавных типов сигнатуры Е, то элемент неглавного типа может стать элементом главного типа только в том случае, если существует конечная формула ф, отделяющая любой неглавный тип от остальных неглавных типов. Если такой формулы нет, то все реализации неглавных типов сигнатуры Е становятся реализациями неглавных типов обогащенной сигнатуры.
В случае континуума типов невозможно одной конечной формулой отделить любой неглавный тип от остальных неглавных типов, следовательно, неглавных типов при обогащении сигнатуры Е так же останется континуум.
Таким образом, при обогащении сигнатуры Е подстановкой ограниченного порядка сохраняется ( -категоричность и малость теории Т. При обогащении теорий с конечным числом неглавных 1-типов число несвязанных неглавных типов может меняться в пределах (ш + 1)\{0}. Пусть Т\ и Т2 — счётные теории одноместных предикатов, тогда соотношение СМ (Ті) СМ(Т2) равносильно одному из следующих трёх условий: 1) Ті иТ2 имеют одинаковое, не более чем счётное, максимальное число попарно несвя
Теории независимых одноместных предикатов с подстановкой ограниченного порядка
Отметим, что в качестве элемента а можно взять 1. Так как в различных моделях Qo- элемент 1 имеет разные типы, то будем элемент 1, относящийся к Qo-, обозначать через 1Q(7. Также заметим, что поскольку все модели Qa являются минимальными [18], то за счёт данных моделей невозможно построение элементарной цепи, объединение которой является предельной моделью. Напомним [15], что 21 называется сервантной подгруппой 25, если для любого а Є А, любого п Є Z, из разрешимости уравнения пх = а в группе 25 следует его разрешимость в 21.
В группе 21 для всякого подмножества В существует минимальная сервантная подгруппа, содержащая В, именно пересечение (В) всех сервантных подгрупп группы 21, содержащих В. {В) состоит из всех элементов группы 21, зависящих от В [15]. Сер-вантную подгруппу (В) , порождённую множеством В, будем называть сервантной оболочкой множества В.
Каждый 1-тип закодируем последовательностью (5І)ІЄШ, где 8І Є ш U {оо}: 8І Є ш означает, что тип описывает делимость на р и неделимость на р , = оо означает, что тип описывает бесконечную делимость на pi, где pi — г-тое простое число. Для любой конечной подпоследовательности (#г)о г га, где 8І Є ш последовательности (8і)іЄш найдётся тип, соответствующий данной подпоследовательности, то есть тип, описывающий делимость на р/, 5І Є ш. Следовательно, по теореме компактности, есть и тип, соответствующий последовательности ( І)ІЄШ) в которой, возможно, некоторые 8і равны оо.
Будем говорить, что тип qi, закодированный последовательностью {8})ІЄШ. является делителем типа 2, закодированного последовательностью (8 )ІЄШ, если 8] 8] для всех і Є ш.
Далее, если это необходимо, будем отождествлять тип qj с кодирующей его последовательность {8І)ІЄШ и писать qj = ( )ІЄш. Будем говорить, что уравнение Yl cjQj = Qj шение в целых числах, если имеет решение в целых числах уравнение 2 cjaj = ai же, как для уравнений над Z: уравнение имеет решение тогда и только тогда, когда НОД{ді,... , qn}\ q. Если 8\ = оо для какого-либо і Є ш, то рассмотрим уравнение Yl cjQj = Qi гДе слагаемое q # заменено на слагаемое c{q\ такое что qi = (510,..., 5\,...), где 8\ Є ш. В последовательности таких уравнений, где в каясдом (т + 1)-ом 8\ больше соответствующего элемента в m-том уравнении, критерий разрешимости уравнения такой же, как для уравнений над Z. Если каждое такое уравнение имеет решение, то имеет решение исходное уравнение. 1) Рассмотрим два типа q\ = (5Q, ..., 8},...), 8} Є ш при г = 2п+1, 8} = оо при г = 2п, п Є ш, и q[ = (8Q, ..., 8 ,...), 8 І Є ш при і = 2п, 8 = оо при і = 2п + 1, п Є ш. Типы q1 и q[ независимы. Добавим к ним все типы из pspan{q\, q[} и получим множество Si; Пусть множ;ество Sj построено и типов, входящих в S равен q = ( )ІЄш. Рассмотрим множество S типов Tj таких, что Tj S и у них 8І = оо для тех г, при которых 81 и 8І Є ш для тех г, при которых 8І = оо. Добавим к Sj один из этих типов, получим множество SJ+i.
Множество S получаем на счётном шаге. С помощью линейных комбинаций и корней породим по индукции реализациями данных типов подгруппу 91, взяв по одной реализации каждого типа: не имеет решений (достаточно рассматривать такие уравнения в силу элиминации кванторов для теорий абелевых групп, о чём говорит теорема Шмелёвой 2). Если а\ \= qi,... , ап \= q, а \= q, то модель У1 не является простой над кортежем (а\,... , ап), так как для а \= q нельзя с помощью главной формулы р(х, а\,... , ап) записать обо всех делимостях элемента а (то есть тип tp(a/ai... ап) является неизолированным). Предельная модель строится из простых, но ни одной простой в данном случае нет, то есть У1 не является и предельной. Последовательностей (5i)i \ таких, что {г 5і Є ш}\ = ш и {г #j = oo} = ш, и соответствующих независимым типам, имеется континуум. Так как из континуального множества типов, счётное множество S можно выбрать континуумом способов, то существует континуум не простых не предельных моделей.
Таким образом, теорема 3.0.6 говорит о том, где не стоит искать не простые и не предельные модели, а теорема 3.0.7 показывает, как построить континуум данных моделей на основе типов, далёких от типов, реализующихся в моделях Qa. Однако интересным является вопрос, можно ли предъявить модели, не являющиеся не простыми и не предельными, в явном виде. Одной из таких моделей является фМр. В статье [18] показано, что данная структура является минимальной моделью рассматриваемой теории, следовательно, не является предельной. Произвольный элемент а Є R/ является реализацией типа q, "говорящего" о неделимости на pj, то есть 8j = 0, а остальные 8І равны оо. Но тогда q не делится на НОД типов, реализующихся в конечном числе прямых слагаемых R,-, / ф j, следовательно, согласно доказательству теоремы 3.0.7, модель фМр не является простой. Данная модель позволяет получить и континуум не простых добавить можно любой из континуума независимых типов, то получаем континуум не простых не предельных моделей.
Если счетная модель Ш теории бесконечной абелевой группы А с конечными инвариантами Шмелевой содержит элементарную подмодель М. , которая является простой над некоторым конечным множеством, то Ш либо проста над некоторым конечным множеством, либо предельна.