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

• Автор: Попков, Роман Андреевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Новосибирск
• Количество страниц: 79 с.

Оглавление
Введение

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

1.1. Примеры

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

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

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

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

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

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

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

1.8. Взаимосвязь классов Р, Ь и NPL в теориях с континуальным числом
типов. Распределения троек стз(Т) в классе 1~с
1.9. Операторы порождения предпорядков Рудин - Кейслера
2. Теории одноместных предикатов
2.1. Чистые теории независимых одноместных предикатов
2.2. Теории независимых одноместных предикатов с подстановкой ограниченного порядка
3. Теория группы целых чисел
Заключение

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

натуральному п число п-типов. Одним из результатов исследований М. Морли является доказательство гипотезы Лося о несчётной категоричности полных теории [32]. Б. А. Палютиным получено описание категоричных универсалов, категоричных квазимногообразии, функции спектров хорновых теорий и квазимногообразий, установлен ряд результатов, относящихся к теории групп и теории модулей, основана и развита коммутативная теория моделей. При описании полных теорий возможны нензоморф-ные реализации этих теорий различными структурами, причём число этих реализаций может зависеть от мощности рассматриваемых структур. Следовательно, возникает так называемая спектральная функция I, ставящая в соответствие некоторой полной теории и фиксированной мощности А мощность 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] определяются гиперграфы простых моделей над реализациями типов малых теорий. На основе графовых структур моделей малых теорий устанавливаются иерархии множеств в этих гиперграфах, раскрывающие структурные связи в счётных моделях малых теорий. Обосновывается ключевая роль теоретико-графовых конструкций в построении эренфойхтовых теорий. На основе гиперграфовых конструкций классификация элементарных полных теорий с конечными преднорядками Рудин — Кейслера обобщается на класс всех малых теорий.

лирует а, где а |= р(х). Построим дерево Д,-расширений над какой-либо реализацией о0 типа р. Рассмотрим последовательности г0,..., гп,... Є 2“, соответствующие маршрутам, задаваемым формулами fî,u(a1, а0) А ... Л Rln(an+,an) Л .... Всего имеется 2“ расширений. Как показано в [10], [11] для достижения конечного или счётного числа Л предельных моделей, задача сводится к построению некоторой системы тождеств.
Если X = п Є ш {0}, то используется следующая система тождеств:
1) п — 1 « тп, т. > п;
2) тт и т, т < п
3) ЩП2 ■ ■ .ns ~ ns, min{ni,n2,...,ns_i} > ns.
Если А = ш, используется система тождеств:
1) пп ps гг, п Є ш;
2) П]П2 ...nsæns, inm{nbn2,... ,ns_i} > ns;
3) ПП2 И Пі(щ + 1)(пг + 2) . . . (tl2 — 1 )п2, П < П2.
Оператор построения предельных моделей над <кк-последовательностью seqLim((gn)neu, Л, {Д|2>}гЄи,) получает на вход:
1) <ЛА--последователыюсть (qn)neu
2) Л Є ш + 1 — число предельных моделей над последовательностью (qn)n€u',
3) последовательность двухместных предикатных символов R^ і Є ш.
Рассмотрим типы qn и qn+1- Так как они принадлежат <дк-последовательности, то
существует формула tp(x, у) такая, что дп+1(у)и{<^(х, у)} совместно и qn+i(y)U{ip(x, у)} Ь qn(x). Пусть предикаты R, действуют так, что Rt(x,y) h р(х,у) и для любых а |= qn+i{y), Rt(x,a.) h qn(x). Будем далее рассматривать вместо предикатов Д, их номера г. Тогда над рассматриваемой <як-последовательностью (qn)neu существует шш последовательностей s = ii,..., г/с,..., соответствующих Rtl (o,j, ag) A ... A Rln{asn, a* ) A ..., где < 1= Яп(х), neoj.
По последовательности типов (д„)пєш строятся последовательности простых моделей fflqn над реализациями типов qn, где (тг-Ы)-ая модель является элементарным расширением гг-ной. Любая предельная модель является объединением счётной цени некоторой последовательности простых моделей над кортежами. Предикаты Дг, г Є и>, служат для связывания реализаций типов из (qn), что приводит к построению требуемого числа предельных моделей. Как показано в [8], задача построения расширения теории с условием существования заданного числа предельных моделей над (qn) сводится к факторизации