Содержание к диссертации
Введение
1 Обобщенная стабильность 10
1.1 Определения, обозначения 10
1.2 Стабильные теории 16
1.3 Р-стабильность 23
2 (РД)-стабильность 29
2.1 Определения 30
2.2 Характеризация (Р, 1)-стабильности 31
3 (Р,а)-стабильность 39
3.1 Признак не (Р,а) стабильности 39
3.2 (Р,а)-стабильность абелевых групп без кручения 42
Выводы
- Стабильные теории
- Р-стабильность
- Характеризация (Р, 1)-стабильности
- (Р,а)-стабильность абелевых групп без кручения
Введение к работе
Постановка задачи и актуальность темы диссертации.
Теория моделей как раздел математики находится на стыке математической логики и алгебры и сформировалась как самостоятельная область в 1950-х годах. Одним из объектов изучения этого раздела математики является классификация элементарных теорий. Одним из способов получения этой классификации является классификация по количеству типов в этих теориях (то есть совместных с теорией множеств формул со свободными переменными и с фиксированным множеством параметров, являющихся элементами модели данной теории). Исследования в этом направлении начались с работ Р. Вота [1], К. Рыль-Нардзевского [2] и М. Морли [3]. Р. Вот доказал, что любой неглавный тип можно опустить в некоторой модели. К. Рыль-Нардзевский доказал, что если число п-типов над пустым множеством конечно для любого п, то теория счетно категорична. М. Морли глубоко исследовал тотально трансцендентные теории, то есть теории, в которых имеется лишь счетное число типов над любым счетным множеством параметров. Как результат этих исследований М. Морли доказал гипотезу Лося о несчетной категоричности полных теорий. В дальнейшем понятие тотально трансцендентной теории было обобщено С.Шелахом до понятия стабильной теории [4] — теории в которой для некоторой бесконечной мощности ж мощность множества полных 1-типов над множеством параметров мощности ж не превосходит этой мощности ж. Одним из ключевых свойств стабильных теорий является свойство определимости типов, состоящее в том, что для любых моделей 9Я =^ 9Т и любой формулы ip с параметрами из 9Т существует формула ф с параметрами из 9Я, такая что
Далее эта область исследований, которую называют теорией стабильности, развивалось в нескольких направлениях. Одно из направлений — изучение подклассов стабильных теорий, обладающих теми или иными интересными свойствами. С точки зрения спектра стабильности (класса мощностей, в которых теория стабильна) среди стабильных теорий можно выделить подкласс суперстабильных теорий (теории, стабильные во всех мощностях, начиная с 2'т'), в котором являются под-
классом w-стабильные, часть из которых являются несчетно категоричными. Так же интересными подклассами стабильных теорий являются сильно минимальные [5] и однобазируемые теории [6], [7].
С другой стороны развиваются направления, целью которых является обобщить понятие стабильности, сохраняя при этом те или иные полезные свойства и методы исследования. В развитие методов, основанных на исследовании свойств отношения ответвляемости типов изучаются простые теории [8], розовые теории [9].
Теория стабильности бурно развивалась во второй половине 20 века и продолжает развиваться. Вопросам стабильности посвящены множество публикаций и монографий [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21] (список далеко не полный).
Стабильные теории не содержат формульно определимого порядка. Однако теории упорядоченных структур так же могут обладать хорошими свойствами. Развитию этой идеи посвящены исследования о-минимальных и слабо о-минимальных теорий [22], [23], [24], [25], [26], [27], [28], [29], [30].
Следует отдельно отметить исследования теорий пар моделей [31], [32], [33], [34] — теорий, в которых одноместный предикат выделяет подмодель. Основным вопросом здесь является, какие условия нужно наложить на предикат для того, чтобы хорошие свойства теории без предиката сохранялись и для теории пары моделей. Одним из результатов этих исследований является определимость типов над любыми Р-множествами для типов над Р-моделями которая была установлена Т.Нурмагамбетовым и Б.Пуаза [35].
Интересное обобщение понятия стабильности было предложено Му-стафиным [36], которое было в последствии уточнено до понятия Е*-стабильности Палютиным [37]. Палютин так же доказал для этого уточнения теорему об определимости типов, обобщающую как определимость типов для стабильных теорий, полученную Шелахом [38], так и результат Т.Нурмагамбетовым и Б.Пуаза для теории пар. Понятие ^-стабильности представляет собой новую шкалу стабильности, основным параметром которой является некоторое отображение типов полной теории в типы другой теории. Палютиным было так же показано, что классы о-минимальных, слабо "оминимальных, сильно минимальных и простых теорий являются стабильно определимыми [39], то есть могут быть определены как классы _Е*-стабильных теорий для подходящего отображения Е*.
В развитие этой теории автором диссертации изучаются несколько частных случаев ^-стабильности (обобщенной стабильности), их свойства и отношения.
Стабильные теории
В [37] приведен пример представления типов, демонстрирующий связь Е -стабильности с классической стабильностью. В этом параграфе мы рассмотрим этот и несколько других способов выразить классическую стабильность в терминах обобщенной стабильности. Для начала введем определение стабильной теории. Определение. Полная теория Т называется стабильной в мощности А если в любой модели 9Я теории Т для любого множества А С М, такого, что \А\ А множество полных 1 -типов теории Т с параметрами из А по мощности не превосходит А (5х(Тл) А, где ТА — теория языка LA , полученная объединением Т и полной диаграммы множества А). Т называется стабильной, если она стабильна в некоторой бесконечной мощности А. Предложение 1.2.1. Пусть Т — полная теория языка L, и С = {с} — одно-элементоное множество констант. Теория Т является Ее -стабильной тогда и только тогда, когда Т стабильна. Доказательство. Пусть Т стабильна в мощности А. То есть для любой 9Л и любого А С М \SX{TA)\ А. Пусть X — множество переменных мощности А и t(X) Є Sx(T). Поскольку t{X) совместно, то найдутся такие ЗЯ и А С М, что ЭЯ \= t(A). Заметим, что также будет выполнено Wl \= Ec(t)(A), что сразу следует из определения Ее Пусть t\ — произвольное пополнение Ec(t). Тогда найдется ровно один такой t-x є SX(TA) , что іг(с) — і( ), h — это в точности тип, полученный из типа ti(A) заменой каждого вхождения константы с в каждой формуле на переменную х (предполагаем, что х не имеет вхождений в формулы из t\). Тем самым построено биективное отображение из множества пополнений типа Ec{t) в множество типов SX(TA) - Следовательно мощность множества пополнений Ec{t) не превосходит А, то есть Т является Ее -стабильной в мощности А. Предположим, что Т не стабильна в мощности А. То есть, найдется модель РТ и множество А С М, что 13 (7 )1 А. Рассмотрим все предложения языка LA, истинные в DJI (полную диаграмму А). Рассмотрим множество переменных X мощности Айв каждой формуле заменим все вхождения констант из А на переменные из X соответственно.
Полученное множество переменных обозначим как t(X) Є Sx(T) Далее, используя такое же взаимно-однозначное соответствие между элементами SX{TA) и пополнениями Ec(t), получаем, что множество пополнений Ec(t) по мощности превосходит А. То есть Т является не Ее -стабильной. Как видно из предложения 1.2.1, классическая стабильность является частным случаем обобщенной стабильности. На самом деле классическая стабильность может быть определена через обобщенную стабильность несколькими эквивалентными способами. Лемма 1.2.1. Пусть Т — полная теория языка L . Для любого п Є и Т ?{ci,...,cn} стабильна тогда и только тогда, когда Т Е[С1у -стабильна. Доказательство. Покажем, что -Е{Сь...,с„} -стабильная теория {С1} -стабильна. По теореме 1.1.1 достаточно показать, что для любых X , t Є Sx{T), X, Y С Xm , если пара (X, Y) отделима в Е{СІу(і), то она отделима в t. Из той же теоремы сле дует, что если пара (X, Y) отделима в E{cu.„iCny(t) , то она отделима в t. Покажем, что если пара (X, Y) отделима в E{Cly{t), то она отделима в Е{С1 c„}(0- Пусть (х, х) отделяет X от Y в E[Cly. Заметим, что формула р(х, х) яв ляется формулой языка {С1}, а значит и формулой языка L[ciy. Кроме того типы Е{СЛ}(І) и Е{С1 с„}() являются замыканием типа t относительно выводимости. По этому формула р(х, х) отделяет X от Y в Е{С1 ,...,с„} Покажем, что Е[С1у -стабильная теория Я{С1,...,с„} -стабильна. Индукция по п: Пусть для всех п п, Т Е{С1 JJ- стабильна. По теореме 1.1.1 для любых X , t Є Sx(T), X, Y С Xm , если пара (X, Y) отделима в -Б{сі,..., }( ), то она отделима в t. Покажем, что если (X,Y) отделима в -E{ci,...,c„}(0 і то она отделима в t. Тогда по теореме 1.1.1 из этого будет следовать Е[Сг ,...)С„} -стабильность. Предположим противное. Пусть (X, Y) отделима в E{cli...iCn}(i) и неотделима в t. Тогда из сказанного выше следует, что (X,Y) неотделима в E{clt„_iCn_1y(t). Если t — некоторое пополнение типа {ф(уі,...,уп-1)\ф{с1,...,сп-і) Є E{cu...tCn_l}(t)}, где yi,...,yn_i не лежат в X , то (X, Y) неотделима в f (Если бы формула tp отделяла (X,Y) в t , то (Ф)] ." 1 отделала бы ее в -E{Cl,...,c„_i}() ) Пусть формула (v,x) отделяет (X,Y) в {С1,...,С„}() Тогда найдется некоторое пополнение t" типа E{ci,...,c„}( ), содержащее множество формул Мх,х)х Є X} U {- (х,х)х Є Y} . Возьмем в качестве t тип f = {ф{уи..., y„_i)№(ci,..., cn_0 Є і" Г i ( -i)} Ясно, что t — пополнение {ф(уі, , уп-і)\ф(сі, ) Cn-i) Є Е _Х(С)} . Име ем с одной стороны, что (X, Y) неотделима в t . С другой стороны формула Pi(v,x,y), такая что /?(v,x) = ( 1(v,x,c), отделяет (X,Y) в El{t ). В си лу -Б{С1} -стабильности теории Т, (X,Y) отделима в t . Противоречие. Значит предположение, что Т не Е{С1 cj -стабильна, неверно. Лемма 1.2.2. Пусть Т — полная теория языка L, и Т 7(....,} -стабильна. Тогда Т Ерк -стабильна. Доказательство Пусть /?(v,x) отделяет (X,Y) в Epk(t). Покажем, что (X,Y) отделима в -E?{ci,...,c„.fc}. По теореме 1.1.1 из этого будет следовать Ерк-стабильность теории Т. Пусть і! — такое пополнение Epk(t), которое содержит формулы { /?(х, х)х Є X} U {-1 (х, х)х Є Y}. Рассмотрим множество формул t", содержащие все формулы из t , с заменой каждого вхождения предиката -P(z) на формулу (z) = V"=i 7=1( = cj+k-(i-i))) Для всевозможных наборов переменных z длины /с. Покажем, что t" непротиворечиво.
Предположим противное. Пусть t" несовместно, тогда найдутся фі,...,фа Є t! и Xii iXs Є і") такие что х,- получена из Vi заменой Р на так, как указано выше, и доказуема секвенция но тогда доказуема секвенция Vz(P(z) (z)),Xl,...,Xsr- поскольку Vz(P(z) -»(z)) h (фі - ХІ) доказуема для каждого г Є {1,..., s} , то доказуема Поскольку константы ( не входят в формулы ч/ч,..., фя , то доказуема секвенция Заметим, что формула 3-nzP(z) эквивалентна формуле 3yVz(P(z) - \/Г=і(Л?=і( = %+fc.(i-i)))) Получаем, что 3 "zP(z) Є і и -,3 "zP(z) Є f. Противоречие с непротиворечивостью t . Значит t" непротиворечиво, то есть t" - тип. Ясно, что t" Э t, а значит i" D {ci,...,c„fc}(0 (поскольку {С1 c„.fc}(i) —наименьший тип языка L.fc , содержащий Формула Ф(у,х), полученная из y?(v,х) заменой Р на f, будет отделять (X, Y) в t" , а значит и в .E{Cl cn.k}(t). Действительно, поскольку t содержит фор мулы { /?(х,х)х Є X} U {-іу?(х,х)х Є Y} , то t" содержит формулы {Ф(х,х)х Є X} U {-.Ф(х,х)х Є Y} . Значит Т - Е к -стабильна. П Предложение 1.2.2. Пусть секвенция Г Ь (р языка, содержащего предикат Р(х), доказуема. Формула (х) не имеет свободных вхождений переменных, кроме входящих в х. Г и if получены из Г и р заменой всех вхождений предиката Р(у) на формулу (у), для всех кортежей у, для которых есть такое вхождение. Тогда доказуема секвенция V \- ip Доказательство. Заметим, что замена Р на сохраняет структуру секвенции. То есть секвенция вида Фі,..., Фп f- Ф переходит в секвенцию вида Ф[}..., Ф п \- Ф . Кроме того формулы (подформулы) вида (ФтФ), где т Є {V, Л, —} ,- Ф , ЗхФ , УхФ перейдут в формулы (подформулы) вида (Ф тФ ) , -іФ , ЭжФ , \/хФ соответственно. Кроме того, держатся в х, то множество свободных пременных каждой формулы (подформулы) Ф содержится в множестве свободных переменных соответствующей ей формулы (подформулы) Ф . Пусть D — доказательство секвенции Г Ь р в виде дерева. Построим дерево секвенций D заменой Р на f в каждой секвенции дерева D . В силу вышеперечис ленных свойств, каждый переход в D будет применением того же правила вывода, что и соответствующий переход в дереве D . Все начальные секвенции останутся ак сиомами, а заключительной секвенцией будет Г Ь ср.
Р-стабильность
В этом параграфе будут рассмотрены несколько представлений типов, полученных добавлением одноместного предикатного символа (которые заданы в параграфе 1). Предложение 1.3.1. Всякая (Р, 0) -стабильная теория (Р, 1) -стабильна. Всякая (Р, 1) -стабильная теория (Р, а) -стабильна. Всякая (Р, о) -стабильная теория (Р, е) -стабильна. Доказательство. Пусть Т —полная теория языка L , Е\ и Е —представления типов теории Т в языке L , t —некоторое множество формул языка L и E2(t) = Еі (і) U t . Покажем, что из Е\ -стабильности следует Е2 -стабильность. Действительно, пусть ip отделяет (X, Y) в -Єг(і) . Тогда она тем более отделяет Следующее предложение показывает, что понятие (Р, 0) -стабильной теории вырождено. Предложение 1.3.2. Пусть Т — полная теория языка L, имеющая бесконечную модель. Тогда Т не (Р, 0) -стабильна. Доказательство. Предположим Т (Р, 0) -стабильна. Заметим, что любая пара непересекающихся бесконечных множеств кортежей длины 1 отделима в E p \t) при помощи предиката Р. По теореме 1.1.1 для любого X, в любом типе из Sx(T) любая пара непересекающихся бесконечных множеств из X отделима. При этом для разных Y Q X пары (У, X\Y) отделяются разными формулами (в силу определения отделимости). Значит язык L должен содержать не меньше формул, чем имеется различных подмножеств в X , то есть 2 х . В силу произвольности X , в качестве .Х" можно взять \L\. Получаем 2 LI \L\ . Противоречие. Такой теории не существует. Следующий пример демонстрирует, что в отличие от (Р, 0) стабильности понятие (Р, 1) стабильности не является вырожденным, и из (Р, 1)-стабильности не следует (Р, 0) -стабильность. Пример 1.3.1. Возьмем в качестве языка L язык, не содержащий никаких символов. Пусть Т — теория языка L, имеющая бесконечную модель. Ясно, что Т — полная теория. Покажем, что Т (Р, 1) -стабильна. Пусть t — произвольный полный тип теории Т над бесконечным множеством переменных. Тогда в языке Lp тип Е р,1 {) может иметь следующие пополнения: итого счетное число пополнений. Т (Р, 1) -стабильна. Естественно, наиболее интересным является вопрос об отношении стабильности и Р -стабильности. Следующая теорема показывает, что из (Р, 1)-стабильности следует стабильность. Теорема 1.3.1. Пусть Т — полная теория языка L, Т (Р, 1) -стабильна.
Тогда Т стабильна. Доказательство. Для доказательства рассмотрим дополнительно два представления типов: То что эти отображения являются представлениями типов показывается в точности так же, как в предложении 1.1.1 Ясно, что из (Р, 1)-стабильности следует Е" -стабильность (это следует из доказательства предложения 1.3.1). Е "-стабильность эквивалентна стабильности. Это следует из того, что Е " отличается от ЕР заменой Р на "Р. Действительно, если t(X) — полный тип теории Т, X и Y — множества кортежей одинаковой длинны, состоящих из переменных из X, х — кортеж переменных из X, формулы Ф!(х,х0) и Ф2(х,х) отличаются заменой каждого вхождения предиката Р в Фі отделяет X от Y в Ep(t(X)) тогда и только тогда, когда Ф2 отделяет X от Y в E "(t(X)) и по теореме 1.1.1 Е " -стабильность эквивалентна стабильности. Покажем, что из Е" -стабильности следует Е " -стабильность. Пусть р отделяет (X,Y) в E "(t) и не отделяет (X,Y) в E"(t). Это фактически означает, что для некоторого z Є X из множества формул { (х,х)х є X} U { V(x,x)x Є Y} U t U {3\у Р(у)} выводится P(z). Заметим, что доказуема секвенция: 3!у Р(у) Ь ( y?(v,x) «-» (Зу( ,Р(у) Л i(v,x,y)))), где -ф получена из р заменой всех вхождений предиката Р(х) на формулу "(х = у) для всех переменных х для которых есть вхождение предиката Р(х). А значит доказуема секвенция: Из этого следует, что множество формул {V (x,x, z)x Є X} U {" (х,х0,2;)х Є Y} U t совместно. Таким образом, формула I/J(V,X0,Z) будет отделять (X,Y) в t, что противоречит і? "-стабильности. П Следующие примеры говорят о том, что обратное неверно. Пример 1.3.2. Рассмотрим модель 21, носителем которой является множество целых чисел (А = Ъ), язык L — {Q(x, у)} состоит из одного двухместного предиката, задающего на А отношение следования естественным образом (Q(x,y) = у = х + 1). Рассмотрим теорию Т = Th(A) этой модели. Она является стабильной, (Р, а) -стабильной, но не является (Р, 1) - стабильной. Ясно, что с Т совместно множество формул F(X) = {х\ ф х?\для любых х\,х і Є — бесконечное множество переменных. Действительно, любая конечная часть этого множества формул выполнима на модели 2t. Таким образом, теория Т имеет модель 9Я, в которой существует бесконечное число несвязанных друг с другом цепочек. Покажем, что Т не (Р, 1) -стабильна. Действительно, возьмем в качестве ти- па t рассмотренное выше множество формул F(X). Формула \/u(Q(v,u) —» Р(и)) отделяет любые два бесконечных подмножества множества переменных X . Покажем, что Т стабильна. Для произвольного множества переменных X и произвольного типа t{X), совместного с Т, возможны следующие пополнения типа E{cy(t) : а) с принадлежит какой-то из цепочек, содержащих элементы из X, б) с принадлежит другой цепочке. Во втором случае тип уже полный, поскольку тогда элемент с множеством X никак не связан. В первом случае, нужно еще указать, в какой именно цепочке лежит с, и номер элемента с в цепочке (по сравнению с элементами из X).
При указании номера, возможно счетное количество вариантов. Умножив его на количество цепочек, получим мощность множества пополнений, не превосходящую Покажем, что Т (Р, а) -стабильна. Заметим, что, исходя из определения представления типов Е(р а , предикат Р является алгебраически замкнутым, то есть либо содержит цепочку целиком, либо не содержит ни одного ее элемента. Если тип t содержит формулы, выражающие, что множество X лежит в бесконечном числе цепочек, то возможны только следующие пополнения типа S p- (i): а) -iP содержит п цепочек пбш б) - Р содержит бесконечное число цепочек. Если же тип t содержит формулы, выражающие, что множество X лежит в к цепочках, то кроме того возможны пополнения: в) Р содержат т цепочек тп Є ш , m к г) Р содержит бесконечное число цепочек. Легко заметить, что в любом случае число пополнений счетно. Следующий пример показывает, что из стабильности теории Т не следует ее (Р, а) -стабильность. Пример 1.3.3. Возьмем в качестве Т теорию эквивалентности (к) с бесконечным числом бесконечных классов эквивалентности. Эта теория является стабильной, поскольку при добавлении константы, возможны только следующие пополнения типа t(X): ста х для некоторого х Є X , Таким образом мощность множества пополнений равна \Х\ . С другой стороны Т не является (Р, а) -стабильной. Действительно, возьмем в качестве t(X) тип, содержащий формулы, выражающие, что все переменные из X попарно не эквивалентны. Это возможно, поскольку все классы эквивалентности бесконечны, а значит алгебраическое замыкание вырождено. Тогда формула Зу(Р(у) Л х та у) будет отделять любые два бесконечных подмножества X . Приведем еще один интересный пример — случайный граф (см. [38] Ex. 4.5, р.79). Случайный граф является примером простой теории [8], не являющейся стабильной. Пример 1.3.4. Пусть L = {Q(x,y)} , где Q — двухместный предикатный символ, Т — теория языка L со следующими аксиомами: Теория T является полной. Покажем, что Т не стабильна. Действительно, пусть 9Я = Т — монстр-модель, А и В — бесконечные множества, А С М и В С М, АГ\ В = 0 . По компактности из аксиом теории Т следует, что существует элемент d, такой, что 9JI \= Q(a,d) для всех элементов а множества А и 9Я = "Q(b,d) для Ъ Є В . Если t(X) — такой тип теории Т, что 9Я \= t(AUB), то формула Q(x, с) языка L{c} будет отделять Хі от Xi над типом t, для некоторых бесконечных подмножеств Х\ и Хч множества X . По теореме 1.1.1 Т не стабильна.
Характеризация (Р, 1)-стабильности
В этой главе наша цель — показать, что теория Т тогда и только тогда (Р, 1)-стабильна, когда ее молено проинтерпретировать в теории языка, состоящего из одноместных предикатов. Достаточность этого условия показывается в предложении 2.2.1 и лемме 2.2.1. Следующее предложение будет являться базисом для дальнейшего доказательства. Предложение 2.2.1. Если язык L состоит только из одноместных предикатов, то полная теория Т языка L (Р,1) -стабильна. Доказательство: Известно, что теория Ті (не обязательно полная) языка, состоящего только из одноместных предикатов, допускает элиминацию кванторов с точностью до формул без свободных переменных. Действительно, пусть Ф(х) — формула языка L и Ті — (возможно неполная) теория языка L. Применив индукцию по числу кванторов, можно считать, что Ф имеет вид где ipij — предложения, а Ф - — атомарные формулы либо их отрицания. Эквивалентными преобразованиями молено привести Ф к виду Ясно, что эта формула имеет желаемый вид, поскольку каждая из формул Ф - фактически зависит только от одной переменной. Тем самым индукционный шаг доказан. База индукции (для бескванторных формул) очевидна. Пусть Т - полная теория языка L, состоящего только из одноместных предикатов и Т не (Р, 1)-стабильна. По теореме 1.1.1 существуют полный тип t(X) и пара (X, Y) множеств кортежей переменных из X такие, что (X, Y) неотделима в t и отделима формулой у(х, х) языка Lp в типе Е{1). Заметим, что язык Lp состоит только из одноместных предикатов и теория Т является (неполной) теорией языка Lp, а значит к формуле р можно применить элиминацию кванторов. То есть Ь у?(х,х) - \J {фі Л Фг(х, х0)) для некоторых предложений фі и бескванторных формул Ф (х,х), г п. Так как совместность множества формул, содержащих дизъюнкцию равносильна совместности этого множества с од ним из членов этой дизъюнкции, то получаем, что совместно множество формул tU{P{x)\x eI}U {фіо Л Фіо(х,х)х Є X} U { фіо V "1ФІ0(Х, x)x Є Y} , для некоторо го г о . Так как фі0 не содержит свободных переменных, то получаем, что совместно множество формул Ю{Р(х)\х Є Х}и{ФІ0(х,х)х Є Х}и{"Фг0(х,х0)х Є Y} . Пусть Ф — формула языка L, полученная из Фіо заменой всех вхождений подформул вида Р(х) на формулу х = х. Так как формула Фг0 не содержит кванторов, совместно множество формул t U {Ф (х,х)х Є X} U { (x,x)x Є Y}.
Таким образом Ф отделяет пару (X, Y) в t. Противоречие. Предложение 2.2.2. Пусть Т и Т — полные теории языков L и L соответственно, и языки L и L не содержат общих символов. Пусть М — структура языка LU L , такая что выполнены условия (2) любая атомарная формула (х) языка L равносильна в М формуле у/(х) языка L . Тогда Т определимо интерпретируется в Т" . Доказательство: Пусть / — соответствие между атомарными формулами язы ка L и равносильными им формулами языка V . Продолжим / до отображения / всех формул из L в множество формул языка L естественным способом / ( Ф) = Ясно, что для любой формулы /?(х) из L выполнено М \= ip(a) - f (ip)(a) для любого а є М. Так как М \ L \= Т и М \ V \= Т", то из полноты ГиТ получаем Следующая лемма выражает свойство сохранения "сложности"теории при ее интерпретации в другой теории, то есть что интерпретируемая теория не может быть "сложнее"той, в которой она интерпретируется. Лемма 2.2.1. Если полная теория Т языка L определимо интерпретируется в теории Tj языка L\ и теория 7\ (Р, 1) -стабильна, то и теория Т (Р, 1) -стабильна. Доказательство: Нетрудно заметить, что переход к подобным теориям и определимым обогащениям сохраняет (Р, 1) -стабильность. Поэтому можно считать, что L С L\, Т С Т\. В доказательстве этой леммы, отображения Е р : Sx{T) — Sx(Lp) и Е р : Sx(Ti) — SX(L\P) будем обозначать одинаково. Заметим, что для полного типа t теории Г: выполнено Предположим, что Т не (Р, 1)-стабильна. Тогда существуют множество переменных X мощности Л, и тип t(X) теории Г, такой, что Ep(t) имеет не менее А+ пополнений. Выберем некоторое обогащение ti(X) типа t(X) до полного типа теории Ті. Покажем, что для каждого пополнения t+(X) типа E p l (t(X)) в языке Lp можно найти содержащее его пополнение tf(X) типа E F (ti(X)). Для этого достаточно показать, что множество формул t+UE iti) совместно. В силу определения это равносильно совместности множества формул t+(X) U t%(X) U {Р(х)\х Є X} . А поскольку {Р(х)\х Є X} С t+(X) , это равносильно совместности множества формул t+ U t\. Заменив множество переменных X на множество констант С, получим что нужно показать непротиворечивость теории b+(C) U h(C). Заметим, что t+(C) — теория языка Lp U С, t\(C) — теория языка L\ U С. При этом Lpf\L\ — L, t+(C) \ (LU С) = h(C) \ (LUC) = t(C) — полная теория. По теореме Робинсона о непротиворечивости t+(C) U t\(C) — совместная теория. Таким образом для каждого пополнения t+(X) типа Е(р,1Ці(Х)) в языке Lp можно найти содержащее его пополнение tf(X) типа Е 1)(ti(X)). Следовательно существует не менее А+ различных пополнений типа Ep(ti). Противоречие с (Р, 1)- стабильностью теории Ті. Перейдем к доказательству необходимости условия интерпретируемости в теории языка, состоящего только из одноместных предикатов для (Р, 1) -стабильности.
Для этого нам понадобится вспомогательное свойство, описанное в следующей теореме, которое, как будет показано далее, так же является характеризационным для (Р, 1) -стабильных теорий. Теорема 2.2.1. Пусть Т — стабильная теория языка L . tp(z,x) — формула языка L, 1(х) — к и для каждого п Є ш теории Т принадлежит предложение, означающее, что существует множество к -кортежей Ап мощности п, такое что для любой пары различных кортежей (а1, а2) из А„ выполнено 3z(z а1 Л z а2 Л " ( (г, а1) -» ip(z, а2))). Тогда теория Т не (Р, 1)-стабильна. Доказательство: Сначала покажем, что в монстр-модели ffi найдется неразличимое множество кортежей А, такое что для любых двух различных кортежей а1 и а2 из А найдется d не входящий в них, что ((p(d, а1) - (p(d,a2)). Достаточно показать, что А — упорядоченно-неразличимое множество, тогда в силу стабильности оно будет неразличимым множеством. Пусть Vi = {хгг Єш} — множество А;-кортежей, попарно не содержащие общих переменных. Покажем совместность множества формул R = TU{3z(z . x.4Az хг Л По условию TU{3z(z x Az х Л .х 1) - /з(2,хг 2)))х ,х 2 Є Vbii ф г2} совместно. Выберем в монстр модели множество В — {bss Є и }, реализующее эти формулы. Рассмотрим конечное множество формул -01 (у1,... , уп),..., (у1, ,УГт) из Fv(T). Вводя фиктивные переменные, будем считать п = ... = тт — г. По теореме Рамсея для любого г Є ш и любых формул фііу1,..., уг),..., фтІУ1, ) Уг)) где у1,... ,уг — А;-кортежи, попарно не содержащие общих переменных, существует бесконечное подмножество В С В , такое что для любых b 1,..., blr, Ы1,..., Ыг Є В , ъ\ ... гг , ji . .. jr , выполнено ф (Ьгі,..., Ьїг) - - Таким образом локальная совместность множества формул R показана. По теореме компактности найдется счетное множество А упорядоченно-неразличимых к -кортежей с условием {3z(z ф a1 /\z ф a2 A ((p(z, а1) - p(z, а2)))ах, а2 еА.а1 а2} . В силу стабильности, А — неразличимое множество. Возьмем некоторые различные кортежи Ь1, Ь2 є А. По построению множества А, существует такое d, не принадлежащее кортежам Ь1 и b2 , что ( (d,b1) -» ip(d, b2)). Без ограничения общности можно считать, что (p(d, b1) и V(rf, b2). Случай 1: d принадлежит одному і-із кортежей из А. Пусть deb3. Т.к. d ф Ь1 и d ф Ь2, то Ь3 ф Ь1 и Ь3 ф b2 . Рассмотрим формулу V(b3,x) = ip(d,x). Тогда выполнено (b b1) и " (b b2), противоречие с неразличимостью А. Этот случай невозможен.
(Р,а)-стабильность абелевых групп без кручения
В предыдущей главе было дано полное описание класса (Р, 1) -стабильных теорий, и этот класс оказался сравнительно узким, и поэтому он не представляет дальнейшего интереса для изучения. Из определения (Р, а) -стабильности можно предположить, что класс (Р, а) -стабильных теорий значительно шире. Но пока что мы приводили лишь единичные примеры (Р, а) -стабильных теорий, не являющихся (Р, 1) -стабильными. В этом параграфе мы покажем, что все полные теории абелевых групп без кручения являются (Р, а) -стабильными. И поскольку те из них, которые имеют бесконечные модели, не интерпретируются ни в какой теории языка, состоящего только из одноместных предикатов, тем самым мы получим сразу серию примеров (Р, а)-стабильных, но не (Р, 1)-стабильных теорий и наглядно продемонстрируем, что понятие (Р, а) -стабильности существенно отличается от уже рассмотренного понятия (Р, 1)-стабильности. В этом параграфе в качестве языка L будем рассматривать язык групп, содержащий один двухместный функциональный символ + , одноместный функциональный символ — и константу 0. Рассматривая абелевы группы (языка L), будем опускать скобки в записи термов, пользуясь ассоциативностью операции сложения. Термы вида t + ... + t будем п раз для простоты обозначать п t, где п — натуральное число, I — терм языка L . Термы вида (—) + ... + (—) будем обозначать — п t, где п — натуральное число, t — п раз терм языка L. Комбинируя эти два обозначения, будем использовать коэффициенты из множества целых чисел в записи термов. Заметим, что любую встречающуюся в параграфе формулу, использующую эти обозначения, можно записать обычным способом, только с использованием символов языка L. Эти обозначения используются только для упрощения изложения.
Пусть Н — абелева группа, Hi — подгруппа Н. Если а Є II, то множество Ні + а — {h + a\h Є Ні} будем, как и принято, называть классом смежности подгруппы Ні в группе Н. Мощность множества классов смежности Ні в Н называ- ется индексом Hi в Н и обозначается [Н: Hi]. Если индекс [Н: Hi] бесконечен, то пишем [Н: Hi] = оо . Если Н2 — подгруппа в Н, то индекс НіГ\Н2 в Ні также будем называть индексом Н2 в Ні и обозначать [#і: Н2]. Как и ранее, обогащение языка L одноместным предикатом Р будем обозначать Lp, обогащение множеством констант С — Lc Обогащение языка L предикатом Р и множеством констант С будем обозначать LQ . Нам пригодятся следующие леммы из [40] Лемма 3.2.1. Пусть Но,..., Нп — подгруппы некоторой абелевой группы А, а0,...,ап Є А, Н0 Доказательство. [40] Глава 7, 39 Лемма 2. Лемма 3.2.2. Пусть Ао,. ,Ап — конечные множества. Тогда ЛС \J АІ = J2 (- Доказательство. [40] Глава 7, 39 Лемма 3. Определение. Формула Ф языка L называется позитивно примитивной, если она имеет вид 3xi ... 3xnG , где Э — конъюнкция атомарных формул. Доказательство предложения 3.2.1 и леммы 3.2.3 повторяет доказательство предложения 4 и леммы 4 из [40] Глава 7, 39, соответственно. Формулировки этих утверждений отличаются наличием предиката, выделяющего подгруппу, при этом доказательства остаются корректными и приводятся здесь для удобства чтения и наглядности. Предложение 3.2.1. Пусть Ф(хі,... ,хп) — позитивно примитивная формула языка Lp и G — структура языка Lp, такая что G \ L является абелевой группой, а предикат Р выделяет подгруппу. Тогда (а) Ф(хі,... ,хп) определяет подгруппу в декартовой степени Gn группы G; (б) для любых щ,..., ап Є G и І 1 формула Ф(хі,..., a;j_i, сц,..., ап) либо не выполняется в G, либо определяет в G1"1 смежный класс по подгруппе, определяемой в G1"1 позитивно примитивной формулой Ф(жі,..., жг_і, 0,...,0). Доказательство. Следует из того, что G \= (0,..., 0) = 0 и для любого терма t[x\,..., хп) языка L и любых а\,..., ап, bi,..., bn Є G , и из того, что пересечение двух групп является группой. Лемма 3.2.3. Пусть G — структура языка LP, такая что G \ L является абелевой группой, а предикат Р выделяет подгруппу. Любая формула Ф(жі,..., хп) языка LP эквивалентна в Th(G) булевой комбинации Ф (хі,... ,хп) позитивно примитивных формул. Доказательство индукцией по числу кванторов. Достаточно рассмотреть случай Ф = Vz(0o V ... V Gm) , где &І , і т, — позитивно примитивные формулы или их отрицания. Так как дизъюникция отрицаний позитивно примитивных формул эквивалентна отрицанию одной позитивно примитивной формулы, то, добавив, если нужно, формулу Эх = х, можно считать, что Ф = Ух( "Ф0 V Фі V Фт), где ФІ, і = т, — позитивно примитивные формулы. Так как УэГФо эквивалентна отрицанию позитивно примитивной формулы, то можно считать, что т 0. Итак, достаточно рассмотреть случай, когда Ф есть Пусть ВІ , і m, — подгруппы G, определенные соответственно формулами Фі(0,..., 0, у), і m . В силу леммы 3.2.1 можно считать, что [BQ : Bi] m!, 0 і m.
Следовательно, для Ь0,..., 6п_х є G и а С {1,..., тп— 1} позитивно примитивная формула определяет в G либо пустое множество, либо множество, содержащее конечное число п(а) = [Во Г) П ВІ (- П ... П Вт)] классов смежности по подгруппе В0 П ... П Вт . Рассмотрим множество где через 7(Z) обозначается множество подмножеств множества Z . Для любого S С У({1,..., т}) определим формулу По лемме 3.2.2 получаем, что Ф(хо, . ,xn-i) эквивалентна в Th(G) формуле V Ф5(жо,... ,ж„_і). Заменяя в формуле V Ф5(жо,... ,х„_і) формулы За; Д Ф, на эквивалентные им позитивно примитивные формулы (заменим связанные пе ременные в Ф,- так, чтобы кванторы существования можно было вынести за знак конъюнкции), получим требуемую Ф . Предложение 3.2.2. Пусть G — структура языка L такая, что G \ L является абелевой группой без кручения, предикат Р выделяет алгебраически замкнутое подмножество, и алгебраически замкнутое множество констант С реализуется элементами из Р . Пусть Ф(хо,..., хп-\) — конъюнкция атомарных формул языка Lc , т. е. Ф имеет вид Л (52 ai,j xi = ai) г е ai,j целые коэффициенты, а, — константы из С, г т, j п . Тогда а) (перестановка строк) b будет решением в G формулы Ф(х) тогда и только тогда, когда b является решением в G формулы Фі(х), полученной из Ф перестановкой конъюнктивных членов; б) (сокращение строки на общий делитель) если d — наибольший общий делитель коэффициентов а о, - ,а П_1, то d делит а ; кроме того b будет решением в G формулы, Ф(х) тогда и только тогда, ко- гда Ъ является решением в G формулы Фг(х), полученной из Ф заменой і -го конъюнктивного члена на 2 a t Xj = а\, где оц = d a+j , j п, ( = d а { ; в) (сложение строк) b будет решением в G формулы Ф(х) тогда и только тогда, когда b является решением в G формулы Фз(х), полученной заменой i\ -го конъюнктивного члена гш ]Г) (diltj -f с cti2j) Xj = а + с аІ2, для і\, і% т, где с — целое число.
