Содержание к диссертации
Введение
1 Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем . 12
1.1 Бескванторная интерпретируемость в мономорфных системах. 12
1.2 Конечноморфность систем с конечным множеством теорий бесконечных подсистем 21
1.3 Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем 28
2 Строение шкалы интерпретируемости для систем, бескван-торно выражающихся через заданный линейный порядок 59
3 Строение сильно субминимальных систем. 70
3.1 Определение субранга и субстепени 70
3.2 Строение сильно субминимальных систем 79
Выводы
Заключение
- Конечноморфность систем с конечным множеством теорий бесконечных подсистем
- Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем
- Определение субранга и субстепени
- Строение сильно субминимальных систем
Введение к работе
Исследование структурных свойств алгебраических объектов является клас сической задачей, решавшейся на протяжении всего развития современной математики. Но, как правило, полное решение проблемы структурной классификации находилось лишь для узких классов алгебраических систем: конечно порождённых абелевых групп, векторных пространств, алгебраически замкнутых полей и т.д. Для постановки общей проблемы классификации в 70-80 годах XX века С. Шелахом [12] была разработана теория стабильности, в которой условие классифицируемости для аксиоматизируемых классов систем было точно сформулировано и обосновано [1], [20].
Но, тем не менее, в рамках теории стабильности такой естественный и важный объект как бесконечный линейный порядок оказывается нестабильным, то есть не поддающимся структурной классификации. В связи с эти были предложены и другие подходы к построению структурной теории для нестабильных теорий - в частности теория О-минимальных структур [2], Т -стабильность [18] и . -стабильность [19], обобщающие классическое понятие стабильности.
В классической теории стабильности для классификации алгебраических систем используется понятие системы инвариантов - некоторого дерева, листья которого помечены кардиналами. Существование такой системы инвариантов для теории автоматически влечёт немаксимальность функции спектра для достаточно больших мощностей [13], поэтому теория линейного порядка, имеющая максимальный спектр, не может быть классифицирована при помощи такой системы инвариантов. С другой стороны, теория О-минимальных структур возникла из идеи, что в качестве инварианта для классификации алгебраических систем можно взять сам порядковый тип некоторого линейного порядка, то есть линейный порядок изначально брался в качестве базового простейшего объекта [9].
Кроме того, простейшие в смысле классического понятия стабильности объекты - сильно минимальные алгебраические системы - оказываются устроенными весьма не просто. Некоторое время стояла гипотеза Зильбе-ра [14] утверждающая, что сильно минимальные алгебраические системы либо интерпретирут бесконечное поле, либо локально модулярны. Однако Хрущовский [7] опроверг эту гипотезу, построив не локально модулярную сильно минимальную алгебраическую систему, в которой не может интерпретироваться никакая бесконечная группа.
Данная работа посвящена построению теории, подобной теории ш - стабильности [8], в которой понятие элементарного типа кортежа замещается на понятие элементарной теории подсистемы. Практически вся теория моделей построена на базовом понятии элементарного типа кортежа - множества формул, характеризующих элементы этого кортежа относительно всех других элементов системы. Понятие типа кортежа по существу описывает отношение между элементарным объектом (кортежом), элементы которого не имеют структуры, и всеми остальными элементами структуры. С другой стороны, если мы попытаемся ввести тип принципиально другого объекта -подсистемы в некоторой исходной системе, то этот объект уже может иметь сложную внутреннюю структуру, и в качестве элементарной характеристики такого объекта можно рассмотреть элементарную теорию этой подсистемы. Заметим, что в отличие от классического понятия типа кортежа в системе, элементарная теория подсистемы описывает не отношение этой подсистемы с другими частями исходной системы, а локально-глобальные характеристики элементов этой подсистемы (локально - потому что только для элементов данной подсистемы, а глобальные - потому что предложения описывают строение всей подсистемы глобально, в целом).
В классической теории моделей очень много результатов получено при том или ином ограничении на множества типов. В качестве первого, самого сильного, ограничения можно рассмотреть ограничение до конечности множества типов в системе. Хорошим классическим примером, когда ограничение количества типов до конечного даёт сильное структурное свойство, можно привести известную теорему Рылль-Нардзевского [11], характеризую -категоричне теории в терминах конечности множеств элементарных п-типов кортежей в теории. Таким образом постановка вопроса о свойствах алгебрических систем с конечным множеством теорий бесконечных подсистем оправдана аналогией с классическим результатом. В первой главе диссертации этот вопрос полностью решается полным описанием таких систем в случае конечной предикатной сигнатуры.
Замещение понятия элементарного типа кортежа на элементарный тип подсистемы позволяет придать стандартным понятиям ранга и степени принципиально иную семантику, по ставнению с рангами в теории стабильности. По аналогии с рангом Морли, в диссертации вводятся понятия субранга и субстепени предложения в некоторой системе, которые характеризуют структурную сложность множества теорий подсистем. Фактически, ранг и степень системы, которые определяются как ранг и степень тождественно истинного предложения, определяют сложность булевой алгебры формульных классов подсистем в исходной системе. Ограничивая ранг и степень, мы ограничиваем сложность этой булевой алгебры, то есть мы задаём класс систем ограниченной сложности (в данном смысле), для ко торого появляются реальные возможности строить структурную теорию. Основной результат данной диссертации, изложенный в третьей главе, состоит в полном описании структуры систем субранга 1 и субстепени 1 (сильно субминимальных алгебраических систем). Для бесконечных систем конечной предикатной сигнатуры это наименьшие возможные значения субранга и субстепени, то есть сильно субминимальные системы являются простейшими в вышеуказанном смысле системами в классе всех бесконечных систем конечной предикатной сигнатуры. Показано, что подобные системы тесно связаны с мономорфными и конечноморфными системами, изучавшимися в 60-х годах XX века. В частности, ключевыми для доказательства основных результатов диссертации оказались несколько теорем, доказанных С. Frasnay [4], [5], [6], и R. Fraisse [3].
Помимо описания структурной теории некоторого класса при помощи системы инвариантов, есть и другой подход - описывать элементы класса в терминах биинтерпретируемости с некоторым явно заданным классом систем. Борис Зильбер [15] сформулировал программу, основная идея которой заключается как раз в таком описании элементарных классов. Во второй главе диссертации даётся описание шкалы интерпретируемости для систем, бескванторно выражающихся через заданный линейный порядок. Фактически доказывается, что любая система конечной предикатной сигнатуры, бескванторно инстрпретирующаяся в некотором бесконечном линейном порядке, взаимно интерпретируется формулами первого порядка с одним из явно заданых предикатов (среди которых 5 дискретных и две бесконечные серии). В свете программы классификации Зильбера, этот результат имеет самостоятельную ценность.
Таким образом, если сравнить предложенную в данной работе методо логию классификации алгебраических систем по сложности с классической теорией стабильности, то можно сделать вывод, что две вышеуказанные проблемы - классифицируемость бесконечных линейных порядков и структурная простота простейших в данном смысле объектов - решаются положительно. Бесконечный линейный порядок типа и является сильно субминимальным (то есть простейшим в данном смысле), более того, все сильно субминимальные системы исчерпываются системами, интерпретирующимися бескванторными формулами через некоторый счётный линейный порядок очень простого вида либо через равенство. Кроме того, в отличие от общепринятого определения О-минимальных стуктур, линейный порядок изначально не фигурирует в определении сложности системы, но возникает естественным образом как простейшая структура. Стоит отметить, что Е.А. Палютин характеризовал понятия О-минимальной и слабо О-минимальной теории в терминах st-определимости [21], которая, в свою очередь, определяется через . -стабильность, так что понятие О-минимальной теории может быть определено и без явного введения линейного порядка. Также можно отметить, что хотя не все сильно субминимальные системы сами являются О-минимальными, все они интерпретируются в О-минимальных структурах (соответствующих линейных порядках).
В первой главе диссертации изучается строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем. Эта глава состоит из трёх параграфов.
В параграфе 1.1 сформулированы основные определения, использующиеся в диссертации, а также ряд лемм, характеризующих интерпретируемость строго n-местных предикатов бескванторными формулами в классе мономорфных систем через вложимость их групп автоморфизмов конеч ных подсистем.
Лемма 3. Пусть даны два строго т-местных предиката Р и Q, выражающихся через некоторый линейный порядок бескванторными формулами. Тогда предикат Р выражается через Q бескванторной формулой тогда и только тогда, когда AutQ(m) Autp(m).
Основной леммой, широко использующейся в дальнейшем, является следующий критерий частичного изоморфизма:
Лемма 4. Пусть некоторый строго т-местный предикат Р, определённый на мноэюестве А, выражается через некоторый линейный порядок бескванторной формулой. Тогда любое частичное взаимно-однозначное отображение ф : {ai,... ап} — {Ь\,..., &„} является частичным изоморфизмом относительно Р тогда и только тогда, когда соответствующая характеристическая биекция является автоморфизмом из группы Autp(n) автоморфизмов подсистем мощности п.
Кроме того, в этом параграфе приводятся некоторые определения из книги [3] (в частности определения индикативных групп - ключевого понятия для развития всей последующей теории) и лемма, обосновывающая взаимно-однозначную связь n-арных расширений групп в терминологии Фраиссе и групп автоморфизмов конечных подсистем в мономорфных системах.
В параграфе 1.2 вначале определяется функция Рго/Ие%(к), а также вводится понятие га-морфной системы, обобщающее понятие мономорфной системы. Следующее утверждение является основным результатом данного раздела:
Теорема 1. Пусть 21 - счётная алгебраическая система конечной предикатной сигнатуры с конечным числом п элементарных типов бесконечных подсистем. Тогда 21 - не более чем п-морфная алгебраическая система.
Следствие 2. Если 21 - бесконечная алгебрическая система конечной предикатной сигнатуры, то Profile%.(u)) Profile%(n) для всех п и.
В силу того, что М. Pouzet [10] доказана монотонность функции Profile для всех п w, то можно утверждать, что функция Рго/г1е ц(к) монотонно неубывает на отрезке к ш.
В параграфе 1.3 изучается строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем. Вначале рассматриваются диаграммы, описывающих стратегию построения непродолжаемого частичного изоморфизма между двумя линейно упорядоченными системами в игре Эренфойхта [17]. При помощи этих диаграмм доказывается следующая теорема, описывающая алгебраические системы конечной предикатной сигнатуры в терминах бескванторной интерпретируемости в явно заданном классе систем:
Теорема 2. Пусть 21 - некоторая бесконечная алгебраическая система конечной предикатной сигнатуры. Тогда следующие условия эквивалентны:
1. множество элементарных типов бесконечных подсистем в системе 21 конечно.
2. выполнено одно из следующих трёх условий:
(a) система 21 несчётна и все предикаты из сигнатуры (21) выражаются через конечное число констант С и равенство бескванторными формулами.
(b) система 21 счётна, и существует такой линейный порядок типа ш + т либо т + ш + ш, где т - некоторое натуральное число, на множестве А и такое конечное множество констант С, образующих начальный интервал в порядке , что все предикаты сигнатуры (21) выражаются через этот порядок и константы С бескванторными формулами.
(c) система 21 счётна и существует такой линейный порядок типа ш - п, где п - некоторое натуральное число, и такое конечное множество констант С, образующих начальный интервал в порядке на множестве А, что все предикаты сигнатуры (21) выражаются через предикат Г \С3 (то есть трансляцию, ограниченную на множество А \ С), и константы С бескванторными формулами.
Глава 2 посвящена изучению шкалы интерпретируемости для систем, бескванторно выражающихся через заданный линейный порядок.
Теорема 3. Пусть (А, ) - бесконечный линейный порядок. Тогда любая система, интерпретирующаяся бескванторными формулами через этот порядок, взаимно интерпретируется формулами первого порядка с некоторым индикативным предикатом из множества: { ,T3,Js,D4,=}U{I™q\p,q 0}U{Jl\r 0} среди корорых 5 дискретных классов и две бесконечные серии.
Доказательству этой теоремы предшествует ряд лемм о взаимной ин терпретируемости индикативных предикатов из одной серии но разной арности формулами с кванторами.
Глава 3 посвящена изучению строения сильно субминимальных систем. В параграфе 3.1 вводятся понятия субранга и субстепени предложения в алгебраической системе. Субранг - это функция, для каждой алгебраической системы определённая на множестве предложений сигнатуры системы и принимающих ординальные значения, а также значения -1 и оо. Субстепень - это функция, определяющаяся через субранг, и принимающая натуральные значения. Доказывается ряд свойств субранга и субстепени, а также доказывается предложение, утверждающее что определение субстепени корректно.
В параграфе 3.2 доказывается теорема, характеризующая бесконечные сильно субминимальные системы конечной предикатной сигнатуры через конечность множества элементарных типов бесконечных подсистем и мо-номорфность:
Теорема 4. Пусть 21 - бесконечная алгебраическая система конечной предикатной сигнатуры Е. Тогда следующие условия эквивалентны:
1. 21 - сильно субминимальна
2. множество элементарных типов бесконечных подсистем в системе 21 конечно и 21 - мономорфна.
Доказательству этой теоремы предшествует ряд технических лемм, описывающих множества решений для ряда формул с индикативными предикатами. Основное назначение этих лемм - показать, что если система 21 сильно субминимальна, то в ней найдётся предложение, выделяющее в точности дискретно упорядоченные подсистемы с наименьшим и наибольшим элементами, которые (см. [16]) попарно элементарно эквивалентны в сигнатуре . Это требуется для доказательства из 1 в 2. Для доказательства утверждения в обратную сторону, требуется теорема о строении систем с конечным множеством элементарных типов бесконечных подсистем.
Поскольку ранее в диссертации дается описание строения бесконечных алгебраических систем конечной предикатной сигнатуры с конечным множеством теорий бесконечных подсистем, то фактически эта теорема даёт описание всех бесконечных сильно субминимальных систем конечной предикатной сигнатуры.
Конечноморфность систем с конечным множеством теорий бесконечных подсистем
Исследование структурных свойств алгебраических объектов является клас сической задачей, решавшейся на протяжении всего развития современной математики. Но, как правило, полное решение проблемы структурной классификации находилось лишь для узких классов алгебраических систем: конечно порождённых абелевых групп, векторных пространств, алгебраически замкнутых полей и т.д. Для постановки общей проблемы классификации в 70-80 годах XX века С. Шелахом [12] была разработана теория стабильности, в которой условие классифицируемости для аксиоматизируемых классов систем было точно сформулировано и обосновано [1], [20].
Но, тем не менее, в рамках теории стабильности такой естественный и важный объект как бесконечный линейный порядок оказывается нестабильным, то есть не поддающимся структурной классификации. В связи с эти были предложены и другие подходы к построению структурной теории для нестабильных теорий - в частности теория О-минимальных структур [2], Т -стабильность [18] и . -стабильность [19], обобщающие классическое понятие стабильности.
В классической теории стабильности для классификации алгебраических систем используется понятие системы инвариантов - некоторого дерева, листья которого помечены кардиналами. Существование такой системы инвариантов для теории автоматически влечёт немаксимальность функции спектра для достаточно больших мощностей [13], поэтому теория линейного порядка, имеющая максимальный спектр, не может быть классифицирована при помощи такой системы инвариантов. С другой стороны, теория О-минимальных структур возникла из идеи, что в качестве инварианта для классификации алгебраических систем можно взять сам порядковый тип некоторого линейного порядка, то есть линейный порядок изначально брался в качестве базового простейшего объекта [9].
Кроме того, простейшие в смысле классического понятия стабильности объекты - сильно минимальные алгебраические системы - оказываются устроенными весьма не просто. Некоторое время стояла гипотеза Зильбе-ра [14] утверждающая, что сильно минимальные алгебраические системы либо интерпретирут бесконечное поле, либо локально модулярны. Однако Хрущовский [7] опроверг эту гипотезу, построив не локально модулярную сильно минимальную алгебраическую систему, в которой не может интерпретироваться никакая бесконечная группа.
Данная работа посвящена построению теории, подобной теории ш - стабильности [8], в которой понятие элементарного типа кортежа замещается на понятие элементарной теории подсистемы. Практически вся теория моделей построена на базовом понятии элементарного типа кортежа - множества формул, характеризующих элементы этого кортежа относительно всех других элементов системы. Понятие типа кортежа по существу описывает отношение между элементарным объектом (кортежом), элементы которого не имеют структуры, и всеми остальными элементами структуры. С другой стороны, если мы попытаемся ввести тип принципиально другого объекта -подсистемы в некоторой исходной системе, то этот объект уже может иметь сложную внутреннюю структуру, и в качестве элементарной характеристики такого объекта можно рассмотреть элементарную теорию этой подсистемы. Заметим, что в отличие от классического понятия типа кортежа в системе, элементарная теория подсистемы описывает не отношение этой подсистемы с другими частями исходной системы, а локально-глобальные характеристики элементов этой подсистемы (локально - потому что только для элементов данной подсистемы, а глобальные - потому что предложения описывают строение всей подсистемы глобально, в целом).
В классической теории моделей очень много результатов получено при том или ином ограничении на множества типов. В качестве первого, самого сильного, ограничения можно рассмотреть ограничение до конечности множества типов в системе. Хорошим классическим примером, когда ограничение количества типов до конечного даёт сильное структурное свойство, можно привести известную теорему Рылль-Нардзевского [11], характеризую -категоричне теории в терминах конечности множеств элементарных п-типов кортежей в теории. Таким образом постановка вопроса о свойствах алгебрических систем с конечным множеством теорий бесконечных подсистем оправдана аналогией с классическим результатом. В первой главе диссертации этот вопрос полностью решается полным описанием таких систем в случае конечной предикатной сигнатуры.
Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем
Основным инструментом при доказательстве следующей теоремы является критерий Тайманова-Фраиссе элементарной эквивалентности двух алгебраических систем (см. например [17], гл. 5, 24), при помощи которого, образно выражаясь, подсчитывается количество элементарных типов бесконечных подсистем в исходной системе. Для применения этого критерия будем использовать диаграммы, которые представляют собой схематические доказательства неэквивалентности систем, предикаты которых выражаются через некоторый линейный порядок на носителе. Доказательства элементарной неэквивалентности везде далее проводятся от противного: будет выбираться такое число N, и строиться такой частичный изоморфизм / с \domf\ N между системами по правилам критерия Тайманова-Фраиссе (или, что то же самое, игры Эренфойхта), что на некоторый \domf\ + 1-ый элемент одной из систем этот изоморфизм не продолжается. Построение такого изоморфизма и будет изображаться на диаграмме. Поскольку в дальнейшем мы будем рассматривать только не плотные линейные порядки, то на диаграммах носители систем будут изображаться при помощи точек, изображающих отдельные элементы носителя, и горизонтальных стрелок типа —,—у, і—у. Если между двумя отмечеными элементами нет многоточия или других элементов, то эти элементы считаются соседними в исходном линейном порядке (то есть между ними нет никаких других элементов). Количество элементов в некоторой группе обозначается числом над или под фигурной скобкой, охватывающей данную группу элементов (не путать с нумерацией элементов описывающей порядок построения изоморфизма!). Соответствие элементов обозначается криволинейными стрелками, соединяющими элементы двух систем. Если конкретные соответствия между двумя группами элементов, выделенных в рамки, несущественны и могут быть произвольными, то рамки, ограничивающие эти элементы соединяются стрелками типа Ф-. Если некоторая стрелка (возможно типа -ФФ-) не указывает на конкретный элемент, то это означает, что для доказательства несущественно, какому элементу сопоставляется данный элемент (или группа элементов). Порядок построения частичного изоморфизма обозначается номерами рядом с отмечеными элементами, а именно, нумеруются произвольно выбираемые элементы в игре Эренфойхта, которые также выделяются тем, что стрелки ведут от них к элементам, которые выбираются в игре Эренфойхта так, чтобы получившееся отображение было частичным изоморфизмом (последние не нумеруются). Построение изоморфизмов таково, что образы произвольно выбираемых элементов в большинстве случаев находятся однозначно из тех соображений, что при любом другом соответствии элементов на следующем же шаге построения возможно выбрать такой элемент, на который строимый изоморфизм не может быть продолжен. В более сложных случаях будут приводиться рассмотрения нескольких вариантов продолжения изоморфизма. Символ у либо Л указывает на тот элемент в системе, на который строящийся изоморфизм невозможно продолжить.
Похожим образом можно ввести диаграммы схематически изображающие биекции конечных линейно упорядоченных множеств. По сути определение такое же, но упрощённое. Все множества конечны, поэтому множества представляются точками (стрелок нет), и поскольку неважен порядок построения, то элементы не нумеруются и соединяются не стрелками, а просто линиями. При помощи таких диаграмм можно наглядно проиллюстрировать, как устроены индикативные группы.
Удобство описания частичных изоморфизмов диаграммами заключается в том, что по виду диаграммы сразу можно определить, какой характеристической биекции отвечает данное частичное отображение и возможно ли продолжение данного отображения до частичного изоморфизма на определённом количестве элементов. Определение. Пусть задан некоторый Р - некоторый п-местный предикат на множестве А и конечное число констант С С А. Тогда для каждого отображения / : {1,... ,п} — С U { } определим мнооюество индексов I = {г/(г) = } = {гі,... , г } и k-местный предикат Р на В = А\С следующим образом. Для произвольного кортежа а = (оі,..., а&) N В \= Pf(a) & A h Р(П, Если некоторый предикат Р определён на множестве В С А, то мы считаем его автоматически определённым на А как множество кортежей. Таким образом, если Р определён на множестве В С -А, то А (= P(ai,... ,a„) тогда и только тогда, когда все щ Є В и В \= Р(а\,... ,ап). Если Е -некоторое множество предикатов, определённых на В, то это соглашение распространяется и на него: все предикаты из Е мы считаем автоматически распространёнными на А.
Лемма 9. Пусть на множестве А задано мнооюество констант С С. А и некоторый предикат Р. Тогда если все предикаты Р для произвольных отображений / : {1,... ,п} — С U { } на множестве В = А\С бес-кванторно выражаются через мнооюество предикатов Е, то предикат Р выражается через Е U С на всём множестве А.
Определение субранга и субстепени
Рассмотрим подсистему Ф С 21с носителем В А\С. Расширим исходную сигнатуру всеми предикатами, которые получаются из исходных предикатов подстановками вместо некоторых переменных констант из С: Е ±=? {Р \Р Є Е, /- произвольное}. Тогда, если мы докажем интерпретируемость бескванторыми формулами предикатов сигнатуры Е через соответствующие линейные порядки на множестве В, то в силу леммы 9 мы получим то, что требуется. Таким образом можно считать, что С = 0, то есть констант нет.
Вначале рассмотрим простейший случай, когда все предикаты исходной сигнатуры Е вражаются через равенство бескванторными формулами. Если при этом система 21 несчётна, то выполнено условие 2а, а если система 21 счётна, то искомый порядок можно построить произвольным образом, например по типу ш, значит выполняется условие 2Ь. Таким образом, далее будем считать, что некоторый предикат из Е не выражается через равенство.
Предположим, что некоторый из предикатов Е не выражается никакой бескванторной формулой через трансляцию Г . Покажем, что в этом случае для любых двух подсистем Ші, Шг Q 21?если их носители упорядоченны порядком по типу ш + т и ш+п соответственно (га п), то эти подсистемы не элементарно эквивалентны. Пусть предикат Р не выражается через трансляцию никакой бескванторной формулой. Тогда через него некоторой бескванторной формулой выражается строго г-местный предикат Р (где г не превосходит арности Р ), который также не выражается через трансляцию. Это следует из того, что любой r-арный предикат Q выражается бескванторной формулой через конечное множество строго /г-местных предикатов (к г), каждый из которых, в свою очередь, выражается через исходный предикат некоторой бескванторной формулой:
Для доказательства того, что две подсистемы Bi, Я$2 Q 53, упорядоченные порядком по типам ш + т и и + п соответственно (т п), не элементарно эквивалентны достаточно показать, что элементарно не эквивалентны системы (B\,P) и (В2,Р).
Далее будем отождествлять предикат Р и соответствующую ему группу автоморфизмов. По теореме 4.6 из главы 11 в [3] и лемме 5, в группе Р существует максимальная индикативная подгруппа 1(Р) Р и существует такое натуральное число к, что Autp(k) = 1(Р)к, и для всех к к имеет место Autp(k ) = I(P)k = Autj (k ). Также для всех достаточно больших г (точнее г 4) и для всех к г, &-арные расширенные группы для некоторой r-арной индикативной группы из серии «S тоже лежат в той же серии (и с теми же параметрами, если серия зависит от параметров) -4.4 в главе 11 в [3]. Таким образом мы нашли все возможные группы автоморфизмов достаточно больших множеств для предиката Р, и поскольку далее используется только группа автоморфизмов для достаточно больших конечных подсистем (для определённости пусть эти подсистемы имеют мощность s), можно считать, что Autp(s) - индикативная группа, причём поскольку Р не выражается бескванторной формулой через трансляцию, то Autp(s) { , DS,SS}.
Доказательство элементарной неэквивалентности систем Ші, 82, проводится построением соответствующего непродолжаемого частичного изо-иорфизма при помощи диаграмм, описанных выше, леммы 4, характеризующей конечные частичные изоморфизмы в терминах групп автоморфизмов, и перебора конечного числа вариантов, определяющихся тем, в какую серию индикативных групп попадает Autp(s).
В этом случае по лемме 4 любой достаточно большой частичный изоморфизм должен сохранять порядок элементов. Строим частичный изоморфизм на max{n + 2, s} элементах, промежуточная диаграмма (за п + 2 шага построения) такова:
Если s п + 2, то построеный частичный изоморфизм на n + 1 элементах нельзя продолжить на п + 2 элемент так, чтобы полученное отображение было бы изоморфизмом относительно Р, поскольку по крайней мере два элемента меняются местами. Если же s п + 2, то на n + 2-ом шаге построения в качестве произвольно выбираемого элемента берём п + 2-ой элемент изображённый на диаграмме, и как бы мы ни продолжали построеный изоморфизм на оставшиеся s — (п + 2) элементов, полученное отображение также не может быть изоморфизмом относительно Р, поскольку всё равно по крайней мере два элемента меняются местами. Autp(s) = Js. В этом случае по лемме 4 любой достаточно большой частичный изоморфизм это либо отображение сохраняющее порядок, либо меняющее порядок на противоположный (в этом случае для лю бых двух элементов из области определения, их образы переставля ются местами в исходном порядке).
Строение сильно субминимальных систем
Множество /(01,02) содержит найменший элемент 6Q И наибольший элемент со. Покажем, что в этом случае множество /(ai,a2) упорядочение по типу ш + и . Определим индуктивно следующие две последовательности элементов из /(01,02): последовательность {b{\i 0}: 60 -уже определён, а 6г+і- это последователь элемента bi, и последовательность {с{\г 0}: сг_і - это предшественник элемента сг-, а первый элемент CQ уже определён. Заметим, что для всех і элементы 6г- и сг- лежит в отрезке /(01,02), так как иначе либо 6,- = ог, следовательно множество /(01,02) конечно, либо Ci = ai и множество /(01,02) конечно. Рассмотрим соответствующие бесконечные множества С+ {6гг 0} и С_ {с,-г 0}. Очевидно, что множества С+ и С_ упорядочены по типам и и и соответственно. Заметим также, что С+ Г) С_ = 0, поскольку иначе если для некоторых СІ и bj выполнено Ci = bj, то CQ = bj+i и тогда множество /(oi, 02) конечно. Остаётся показать, что /(01,02) = С+ U С_. Предположим противное, и существует элемент do Є I(ai,a,2) \ (С+ U С_). Рассмотрим две индуктивно определяемые последовательности элементов из J(ai,a2): do уже определён а d{+\ - это последователь элемента d{ и d{„\ - это предшественник элемента di. Заметим, что на каждом шаге построения последовательностей С+ d-i dj С-, так как иначе если, например, d{ Є С_, то в силу единственности последователей и предшественников в линейном порядке, do Є С-. Значит если рассмотреть D {di\i Є Z}, то это бесконечное множество и оно упорядоченно по типу ш + и, что противоречит условиям.
Пронумеруем элементы множества V по возрастанию: V = {a,i\i V}, ai a2 ... a\y\. Рассмотрим три возможных варианта устройства порядка на множестве А.
Случай 1. В множестве А нет подмножеств, упорядоченных по типу ш . Поскольку множество А бесконечное, то в А есть подмножества упорядоченные по типу ш. Тогда для любого 1 г \V\ множество 7(а,_1,аг) упорядоченно либо по типу ш, либо по типу конечного линейно упорядоченного множества. Покажем, что при 1 г \V\ множество 7(аг-_і,аг-) может быть упорядоченно только по типу UJ. Предположим противное, то есть для некоторого 1 і \V\ отрезок 7(a,-_i,o,-) конечен. Но тогда элемент аг- имеет предшественника. Поскольку щ Є V, то тогда аг- не имеет последователя, но тогда можно построить последовательность элементов by, j и, если в качестве bj+i брать произвольный элемент аг- bj+i bj. Множество {bj\j ш} будет упорядоченно по типу о; , что противоречит предположению. В итоге получаем, что исходное множество А упорядоченно по типу и п + т, где т может быть равным нулю, а п 1.
Случай 2. В множестве А нет подмножеств, упорядоченных по типу ш. Тогда для любого 1 і V отрезок і"(аі,аг+і) упорядочен либо по типу со либо по типу конечного линейно упорядоченного множества. Покажем, что при 1 і \V\ множество 1(щу аг+і) может быть упорядоченно только по типу со . Предположим противное, то есть для некоторого 1 г \V\ отрезок /(аг-,аг+і) конечен. Но тогда элемент аг- имеет последователя. Поскольку аг- Є V, то тогда щ не имеет предшественника, но тогда можно построить последовательность элементов bj, j со, если в качестве 6 +1 брать произвольный элемент bj 6J+i аг-. Множество \bj\j со} будет упорядочено по типу со, что противоречит предположению. В итоге получаем, что исходное множество А упорядочено по типу т + ш п, где т может быть равным нулю, а п 1.
Случай 3. Остаётся рассмотреть случай когда в А есть подмножества упорядоченные по типу и и подмножества упорядоченные по типу со . По условию в множестве А нет подмножеств упорядоченных по типу со + со. Это означает, что любое подмножество упорядоченное по типу со находится слева от любого подмножества, упорядоченного по типу со .
Концентрирующей парой назовём пару элементов из V, если эта пара имеет один из следующих видов: или это пара (а,, аг+і), в случае когда множество /(а,-, аг+і) упорядочено по типу а;-1-а; либо по типу конечного (возможно пустого) линейно упорядоченого множества, или это пара (аг-,аг), в случае когда у элемента аг- нет ни последователя, ни предшественника.
Установим следующие факты Если для некоторых элементов аг-,а+і Є V отрезок 1{а а{+\) упорядочен по типу со + со или по типу конечного линейно упорядоченого множества (возможно пустого), то отрезок 7(а,-_і,а,-) упорядочен по типу ш, а отрезок 7(а,-+і,а,-+2) - по типу ш . Для начала отметим, что элемент щ имеет последователя, а элемент а,-+і - предшественника. Поскольку и щ и аг+і лежат в множестве V, то тогда у аг- нет предшественника, а у аг+і - последователя, что возможно лишь в том случае, когда отрезок 7(а,-_і, щ) упорядочен по типу а;, а отрезок 7(а +х, а ) -по типу а; , что и тербовалось показать. Также заметим, что если некоторый элемент аг- Є V не имеет ни предшественника ни последователя, то отрезок i"(aj_i,aj) упорядочен по типу w, а отрезок 7(aj,aj+i) - по типу ш . Таким образом мы показали, что если (щ,а - концентрирующая пара (здесь j — і 1), то отрезок J(a,-_i, а,-) упорядочен по типу и), а отрезок I(a,j,aj+i) - упорядочен по типу ш .
Если для некоторых элементов 2j, aj_i Є V отрезок 7(aj_i, л ) упорядочен по типу ш, и пары (аг-,аг), (аг-,а,+і) не концентрирующие, то отрезок 7(аг-,а,+і) упорядочен по типу и). Для этого заметим, что элемент аг- не имеет предшественника. Тогда поскольку щ лежит в множестве V, то у аг- есть последователь, что возможно лишь в том случае, когда отрезок /(ах-_1,о,-) упорядочен либо по типу и либо по типу ш +ш . Но поскольку пара (аг-,аг+і) не концентрирующая, то возможен лишь первый случай.
