Примитивно связанные теории

Алгебра, и логика, 39, N 2 (2000), 145-169

УДК 510.67:512.57

П Р И М И Т И В Н О С В Я З Н Ы Е ТЕОРИИ*)

Е, А. П А Л Ю Т И Н Юрию Леонидовичу Ершову, многому меня

научившему,

в связи с его 60-летием

Введение

Цель настоящей работы — доказать теорему об элиминации кванто­ ров для так называемых примитивно связных теорий. Примерами таких теорий служат теории модулей. Данная теорема обобщает хорошо извест­ ную теорему Баура—Гараваглиа—Монка (см. [1]) об элиминации кванторов в теории моделей модулей. Отметим, что определение класса примитив­ но связных теорий не содержит, в отличие от модулей, каких-либо усло­ вий относительно вида аксиом, задающих эти теории. В [2, 3] приведена аналогичная теорема для так называемых коммутативных теорий. Класс примитивно связных теорий содержится в классе коммутативных теорий, но коммутативные теории, в отличие от примитивно связных, не допус­ кают полной элиминации кванторов до примитивных формул (необходи­ мо добавление произвольных 1-местных формул). Упомянем работу [4], в которой рассматриваются так называемые аддитивные теории. Как и примитивно связанные, они обобщают теории модулей и являются част­ ным случаем примитивно связных теорий. Отметим, что доказательство основной теоремы для аддитивных теорий значительно проще. *'Работа выполнена при финансовой поддержке Российского фонда фундаменталь­ ных исследований, проект N 99-01-00600.

©

Сибирский фонд алгебры и логики, 2000

146

Е. А. Палютин Пусть Т — полная теория первого порядка языка L. Никаких ограни­

чений на мощность языка L мы не предполагаем. Как обычно, фиксируем некоторую достаточно насыщенную модель Q теории Т с носителем С Все рассматриваемые элементы и множества берутся из С. Кортежи (п-ки) элементов (ai,...,a n ) и переменных (х\, ...,х п ) будут обозначаться соот­ ветственно а и х. Если s — кортеж элементов или переменных, то через /(s) обозначаем его длину. Вместо 6 1= Ф(а) будем использовать просто выражение Ф(а). Вместо а € Сп пишем а € С. Формулы вида Зз1...Эа: п (ФоЛ...ЛФ*.), где Ф,, г ^ fc, — атомарные формулы, называются позитивно ными; для краткости будем называть их

примитив­

примитивными.

Если а — кортеж элементов из 6, то через tp+(a) будем обозначать множество всех примитивных формул Ф(х), истинных в С на кортеже а. Эквивалентность а на некотором множестве X п-ок элементов из С, определенная в С с помощью некоторой примитивной формулы Ф(х 1 ,х 2 ), называется примитивной эквивалентностью. Область определения X та­ кой эквивалентности а задается в С примитивной формулой Ф(х, х) и обо­ значается через dom а. Обычно а отождествляют с Ф и используют выра­ жение Qf(xL,x2) вместо Ф(х*,х 2 ). Если Ф(х,у) — примитивная формула, а — кортеж элементов, 1(a) = = /(у), то через Ф(С,а) обозначается множество всех кортежей элемен­ тов из С, на которых в С выполняется формула Ф(х,а). Такие множе­ ства называются примитивными.

Говорят, что примитивное множество

X 0-определимо, если X = Ф(С) для некоторой примитивной формулы Ф(х). Если Ф(х,у) — примитивная формула, a, b — n-ки из С и /(a) = = /(b) == /(у), то множества Ф(С,а) и Ф(6,Ь) называются

примитивными

копиями. ОПРЕДЕЛЕНИЕ. Теория Т называется примитивно

нормальной,

если для любых примитивных копий X, У выполняется X = Y или X П ПУ = 0.

Примитивно связные теории

147

В случае модуля М над ассоциативным кольцом R примитивные ко­ пии являются классами смежности некоторой подгруппы, поэтому теории модулей примитивно нормальны. Примитивно нормальной будет также теория системы А, если теория ее декартовой степени Аш стабильна. Если Ф(х, у) — примитивная формула, то через хФ обозначается формула Зу(Ф(х 1 ,у) Л Ф(х 2 ,у)). Если теория Т примитивно нормальна, то формула (хФ)(х 1 ,х 2 ) определяет в С эквивалентность, областью опре­ деления которой является множество ЗуФ(С,у), а ее классами будут все непустые множества вида Ф(С, а), где а — набор элементов из С. Поэтому непустое примитивное множество X является классом некоторой прими­ тивной эквивалентности а — назовем ее носителем множества X. Непу­ стые примитивные множества Х1 Y тогда и только тогда будут прими­ тивными копиями, когда они имеют общий носитель а, который назовем свидетелем копий X , Y. Множество X называется А-примитивным,

если существует такое

семейство 5 примитивных множеств, что

X =

f){Y\Y€S}.

Эквивалентность а называется А-примитивной,

если существует та­

кое множество Е примитивных эквивалентностей, что

Ясно, что область определения doma Д-примитивной эквивалент­ ности а является 0-определимым Д-примитивным множеством и любое непустое Д-примитивное множество X будет классом некоторой Д-при­ митивной эквивалентности а, назовем ее носителем X . Пусть а — эквивалентность, X — некоторое множество. Будем гово­ рить, что X является а-замкнутым,

если аа С X при любом а 6 (X П

d o m a ) . Через а \ X обозначается ограничение (аПХ2)

эквивалентности

а на множество X. Через Х/а обозначаем множество {(а \ X)a | a 6 X}. Непустое множество X называется обобщенно примитивным множеством),

(о. п.

если существуют такое Д-примитивное множество X* и

148

Е. А. Палютин

такая примитивная эквивалентность а, что X* С dom а и X = Х*/а.

При

этом X* называется основой, а а — образующей эквивалентностью

мно­

жества -X". Носитель основы X* о. п. множества -X" назовем носителем

X.

Отождествляя одноэлементное множество {а} с элементом а, будем счи­ тать, что Д-примитивные множества являются обобщенно примитивными. Классы X и У одной Д-примитивной эквивалентности а назовем /^-примитивными

копиями, а а — свидетелем копий X и У.

О. п. множества X и У называются обобщенно примитивными

ко­

пиями (о. п. копиями), если у них имеется общая образующая эквивалент­ ность, а основы X* и У* являются копиями. Свидетель Д-примитивных копий X* и У* называется свидетелем о. п. копий Jf и У. Пусть а — Д-примитивная эквивалентность, /3 — примитивная экви­ валентность, dom а С dom/З. Эквивалентность на множестве (doma)/(/3fl Па), определенную эквивалентностью а, назовем обобщенно примитивной эквивалентностью

(о. п. эквивалентностью) и обозначим через а//3.

Формула Ф(х,у,г) называется (х,у)-рефлексивной, если /(х) = /(у) и выполняется Г Ь (Ф(х, у , s) -» (3»Ф(х,х,z) Л ЗгФ(у, у , z))).

ЗАМЕЧАНИЕ 1. Нетрудно проверить, что если теория Т примитив­ но нормальна и (х, у)-рефлексивная формула Ф(х,у) содержит свободно только переменные из кортежей х, у, то она определяет эквивалентность, ОПРЕДЕЛЕНИЕ. Пусть о. п. множества X, У — о. п. копии, а — их образующая эквивалентность. 1) Будем говорить, чтоX связано cY с помощью

формулыФ(х,у,z),

если существует кортеж элементов с и выполняются следующие условия: (a) для любых a 1 G -X"* и b 1 G У* существуют такие а 2 £ X* и Ь 2 € У*, что в С истинны Ф(а х ,Ь 2 ,с) и Ф(а 2 ,Ь 1 ,с); (b) для любого а Е X* множество Ф(а, С, с) является (а \ У*)-замкнутым и не содержит У*; (c) для любого b G У множество Ф(С, Ь,с) является (а \ Х*)-замкнутым и не содержит -X"*.

149

Примитивно связные теории

2) Будем говорить, что X примитивно связано с У, если существует (х,у)-рефлексивная формула (x,y,z) такая, что X связано с У с помо­ щью формулы <&(x,y,z). ОПРЕДЕЛЕНИЕ. Теория Т называется примитивно связной, если она примитивно нормальна и любые о. п. копии X, У либо примитивно связны, либо обе одноэлементны. Теорема, о которой говорилось в начале введения и доказательству которой посвящена данная статья, звучит так: Т Е О Р Е М А 1. Каждая примитивно связная полная теория Т до­ пускает элиминацию

кванторов до примитивных

формул, т. е. любая

формула языка теории Т эквивалентна в Т булевой комбинации

прими­

тивных формул. Напомним, что теория Г, допускающая элиминацию кванторов до примитивных формул, называется примитивно базируемой. Из теоремы 1 вытекают С Л Е Д С Т В И Е 2. Каждая примитивно связная теория

является

стабильной. С Л Е Д С Т В И Е 3. Каждая примитивно связная теория

является

нормальной. Следствие 3 вытекает непосредственно из теоремы 1 и определения нормальной теории (см. [5]), а следствие 2 — из следствия 3, так как любая нормальная теория согласно [5] будет стабильной. В силу компактности из теоремы 1 получаем С Л Е Д С Т В И Е 4. Если каждое пополнение неполной теории Т при­ митивно связно, то Т допускает элиминацию кванторов до примитив­ ных формул и произвольных

предложений.

В модуле М над ассоциативным кольцом R о.п. копии являются клас­ сами смежности некоторой подгруппы абелевой группы Мп/Н

вида W/H,

где W, Я являются Д-примитивными подгруппами абелевой группы мо­ дуля Мп. Поэтому теория модуля М примитивно связна. Класс примитивно связных теорий в отличие от класса теорий моду-

150

Е. А. Палютин

лей замкнут относительно многих операций, что позволяет строить новые примеры примитивно связных теорий. Например, можно брать дизъюнкт­ ное объединение любого семейства S примитивно связных теорий или раз­ множать примитивно связную теорию Т с помощью новой эквивалентно­ сти а и изоморфизма / между а-классами. Одноразмерные (см. [6]) хорновы теории (не обязательно полные) являются примитивно связными. Заметим, что даже категоричные хорно­ вы теории не могут быть параметризованы с помощью семейства моду­ лей. Таким образом, в элиминации кванторов для одноразмерных хорновых теорий.нельзя использовать теорему Баура—Гараваглиа—Монка. Так как одноразмерные хорновы теории имеют немаксимальные спектры, то для них элиминация кванторов до примитивных формул и произвольных 1-местных формул показана в [7, 8]. В дальнейшем, если не оговорено противное, мы предполагаем, что Т — полная примитивно связная теория.

§ 1. Определения, п р е д в а р и т е л ь н ы е результаты ОПРЕДЕЛЕНИЕ. Пусть X — о.п. множество, a — его образующая эквивалентность. Если для (a \ Х*)-замкнутого множества У имеет место (X* П У ) ^ 0 и н е выполняется X* С У, будем говорить, что У делит X. Л Е М М А 1.1. Пусть даны две пары о. п. копий Х\)Х2

и Ух, У2. Если

Хх С Ух и (Х2 П У2) Ф 0, то Х2 С У2. ДОКАЗАТЕЛЬСТВО. Достаточно доказать лемму для Д-примитивных копий. Предположим, что лемма неверна, т. е. У2 делит множество Х2. Пусть 7 — свидетель копий Х\ и Х2. Рассмотрим минимальную Д-примитивную эквивалентность а С ) , для которой существуют такие кортежи а, Ь € dom а, что a G Х\ и У2 делит множество a b . Пусть (х, у)-рефлексивная примитивная формула Ф связывает а а и a b . Из-за минимальности а множество У2 является (а П уФ)-замкнутым. По теореме компактности найдутся такие две пары примитивных копий Х\,Х2

и YUY2^ а также

(х,у)-рефлексивная примитивная формула Ф(х,у,с1), что выполняются

151

Примитивно связные теории

условия: 1) 0 ф Х\ С Yi; 2) У2 делит Х 2 ; 3) Ф связывает Х\} Х2 и 4) Уз замкнуто относительно уф. Возьмем такие a € Х\ и с, что Ф(а,а,с). Рассмотрим множества У = {е | е G -Х"ь Ф(е, f, с) для некоторого f G Х\}, Z = {а | а б -Xi, Ф(а, b, d) для некоторого b € (-Х*2 П Yi)}Из примитивной нормальности теории Т следует V = Х\. Ясно, что Z — собственное непустое подмножество множества Х\. Так как Х\ С Ух, то V и i? являются копиями. Это противоречит примитивной нормальности. Л Е М М А 1.2. Пусть а,/3 — Д-примитивные X — /^-примитивное

эквивалентности,

множество и X С (dom а П dom/3). Тогда эгсви-

валентности а \ X и /3 \ X перестановочны. ДОКАЗАТЕЛЬСТВО. Возмем кортежи a, b , c G X с условиями а(а, Ь) и /3(Ь,с). Для доказательства леммы необходимо найти d £ X такой, что выполняются условия /3(а, d) и a ( d , c ) . В силу теоремы ком­ пактности достаточно найти такой d для примитивных эквивалентностей а, /3 и примитивного множества X, Пусть X = Ф(С,е) для примитивной формулы Ф(х,у). Рассмотрим формулу Ф(х,х 1 ,у) = Зх 2 (а(х 1 ,х 2 )Л/3(х 2 ,х)ЛФ(х 2 ,у)). По условию, имеем Ф(с,а, е). Поскольку а и /3 рефлексивны, получа­ ем Ф(с,с,е) и Ф(а, а, е). В силу примитивной нормальности справедливо Ф(а, с, е). Лемма доказана. ОПРЕДЕЛЕНИЕ. Пусть X — о. п. множество, а — его образующая эквивалентность, Ф(х, у, z, u, v) — примитивная формула, с — кортеж эле­ ментов, 1(c) = /(v). (1) Будем говорить, что формула Ф(х,у,г,и, с) определяет терм Мальцева на Х1 если выполняются следующие условия: (а) для любых а, Ь, с G X* найдется d G X* такой, что Ф(а, Ь, с, d, с); (Ь)аГХ*С((хФ)П(уФ)П(2Ф)); (c) а \Х* = {иЪ) \Х*-} (d) Ф(а, а, Ь, Ь, с), Ф(а, Ь, Ь, а, с) для любых а, b G X*.

152

Е. А. Палютин (2) Будем говорить, что формула Ф(х,у, z,u, с) определяет аффин­

ную группу на X, если выполняются условия (а)—(с) предыдущего пункта и существует абелева группа (Х;+) такая, что Ф(х, y,z, u, с) определяет на X отношение u = ( x - y + z ) , которое называется аффинным сложением на X, Л Е М М А 1.3. Пусть X — о. п. множество, Ф ( х , у , г , и , у ) — при­ митивная формула, с — кортеж элементов, 1(c) ~ /(v). (1) Следующие условия равносильны: (a) Ф(х,у,г, и, с) определяет терм Мальцева на X; (b) Ф ( х , у , г , и , с) определяет аффинную группу на X . (2) Если примитивные формулы Ф(х, у, z, и, с) и Ф(х, у, z, и, d) опре­ деляют термы Мальцева на X, то они эквивалентны на X*. (3) Если примитивная

формула Ф(х,у,г,и, с) с параметрами с

определяет терм Мальцева на X, то найдется примитивная

формула

Ф(х,у,г, и) без параметров, определяющая терм Мальцева на X. ДОКАЗАТЕЛЬСТВО. (1) и (2) получаем благодаря примитивной нормальности теории Г, (3) вытекает из (2). ОПРЕДЕЛЕНИЕ. 1) Будем говорить, что о. п. копии Х} У е-связаны, если они связаны с помощью примитивной формулы Ф(х,у), определяю­ щей эквивалентность. 2) Будем говорить, что X аддитивно связано с У, если они связаны с помощью такой (х, у)-рефлексивной формулы Ф(х,у,г), что для любых а Е I * и b Е У* найдется такой с Е С , ЧТО Ф(а, Ь, с). ЛЕММА

1.4.

Пусть о. п. копии X,Y

аддитивно связаны

и

Ф(х,у,г) удовлетворяет условиям предыдущего определения. Пусть /3 = = хФ и Ф*(х,у,и, v) = (хуФ)(ху, uv). Тогда выполняются условия: (1) если a , b E (X* U У*), то справедливо Ф*(а, b , a , b); (2) существует примитивная формула Ф(х,у, u , v ) , определяющая аффинные группы на X* /ft

uY*/fi;

(3) существует такая формула Ф*(х,у,и, v), что /3 = хФ* = уФ* = иФ* = уф*,

Примитивно связные теории

153

для любых Z\,Z2 Е {X*,У*}, а Е Z\9 b Е Z
(*)

Возьмем произвольные а Е X*, b Е У*. Рассмотрим множества R = {с | с Е X* и Ф*(с, d, a, b) для некоторого d E У*}, 5 = {с | с Е X* и Ф*(с, d, а, а) для некоторого d E X*}, Из условий аддитивной связанности X и У получаем Д = X*. Поскольку X* и У* являются копиями, X* и S также являются копиями. По усло­ вию (1) имеем а Е 5 . Из примитивной нормальности теории получаем 5 = X*. Рассмотрим множество Z = {с | с Е У* и Ф*(с, d, b, b) для некоторого d E У*}, оно будет копией множества 5 . Поскольку X* С 5 и b E <£, то по лемме 1.1 получаем Z = У*. Возьмем в качестве Ф(х,у, u, v) формулу Эу / Зи , (Ф*(у,у , ,х,х)ЛФ*(и,и , ,х,х)ЛФ*(у,и , ,х,у / )). Из условий (1), (*) и равенств S = X*, Z = Y* вытекает, что послед­ няя формула определяет терм Мальцева на множествах Х*//5 и У*//?. (3) Рассмотрим формулу Ф(х,у,и,у) = Зу / (Ф*(х,у , ,и,у)ЛФ*(у,у , ,у,у)). Ясно, что для любых Zx,Z2

Е {Х*,У*}, а Е Zx, Ь Е 2*2 формула

Ф(х,у,а,Ь) определяет биективное отображение Zi//3 на ^ / / З и /3 =

154 =

Е. А. Палютин хФ

=

уФ

=

иФ. Имеет место также Ф(а, b , a , b). Формула

Ф*(х, у, и, v) = (хуф)(ху,1гу) сохраняет все свойства формулы Ф, и вы­ полняется /3 = УФ*. Образ терма Мальцева на Zi//3 при примитивном биективном отображении будет термом Мальцева на множестве Z2//3. Из леммы 1.3 получаем требуемое утверждение. Лемма доказана. Про формулу Ф*(х,у,и,у) из предыдущей леммы будем говорить, что она аддитивно связывает X и У. Если j — носитель множества X, то, согласно леммам 1.4 и 1.1, свойство быть аддитивно связанными с помощью этой формулы оказывается эквивалентностью на семействе 7-классов, определенном формулой Ф*(х,х, х,х). Л Е М М А 1.5. О. п. копии X, У тогда и только тогда примитивно связаны, когда они либо е-связаны, либо аддитивно связаны. ДОКАЗАТЕЛЬСТВО. Пусть (х, у)-рефлексивная формула Ф(х, у, z) примитивно связывает X с У и с — такой кортеж элементов, что для Ф(х, у, с) выполняются условия (а)—(с) определения связанности. Если для любого a G X* справедливо У* С ЭгФ(а, С, z), то X и У аддитив­ но связаны. В противном случае формула ЗгФ(х*,х 2 ,г) связывает X и У, а по замечанию 1 из введения она определяет эквивалентность. ОПРЕДЕЛЕНИЕ. 1) О. п. множество X называется аддитивным, ес­ ли некоторая примитивная формула Ф задает аффинную группу на X. 2) О. п. эквивалентность а/0 называется аддитивной, если существу­ ет примитивная формула Ф, задающая аффинную группу на каждом ее классе. Л Е М М А 1.6. Пусть X — о.п. множество, У — его о. п. подмно­ жество и примитивная формула Ф(х, у, z, u) определяет аффинную груп­ пу на X. Тогда У является аффинной подгруппой этой группы, т.е. Ф определяет аффинное сложение на У. ДОКАЗАТЕЛЬСТВО. По теореме компактности можно считать, что X*,Y* — примитивные множества. Пусть Ф(х,у,и) = 3 v ( $ ( x , y , u , v ) Л v G У*). Предположим, что лемма неверна. Тогда для некоторых а, Ь, с из У*

Примитивно связные теории

155

имеет место -пф(а, Ь,с). Поскольку У* С Ф(а, а, С), из примитивной нор­ мальности теории следует равенство (Ф(а, Ь, С)ПФ(а, а, С)) = 0 . Получили противоречие с условиями b 6 Ф(а, Ь, 6) и b G Ф(а, а, С). ОПРЕДЕЛЕНИЕ. О. п. множество X называется

мультиаддитив-

ным, если существует конечная последовательность примитивных эквивалентностей O*Q С . . . С ап такгш, что выполняются условия: (1) Ofo является образующей эквивалентностью множества X; (2) X* содержится в некотором «„-классе; (3) для каждого г < п эквивалентность c^+i/a, аддитивна. Последовательность (с*о, ...,а п ) называется мультиаддитивной X , а минимальное такое число п — степенью мультиаддитивности

для мно­

жества X. ОПРЕДЕЛЕНИЕ. Пусть X — о. п. множество, а — его образующая эквивалентность. 1) Пусть /3 — эквивалентность и (а \ X*) С /3. Мощность множества Х*//3 назовем индексом /3 в X и обозначим через [X : /3]. 2) Множество X называется распадающимся, если существует при­ митивная эквивалентность /3 с условием (а \ X*)

С /3 и конечным

неединичным индексом в X . Если, кроме этого, некоторое 0-определимое (/3 f Х*)~замкнутое примитивное множество Y делит X , то будем гово­ рить, что множество X огпмеченно распадается, a (Y П Х*)/а

назовем

отмеченным подмножеством множества X. 3) Множество X называется приводимым, если существует конечное семейство 0-определимых (а \ X*)-замкнутых примитивных множеств 5 такое, что X* С ( J S и X* <£. Y для каждого Y e S. 4) Множество X называется аддитивно разложимым, если суще­ ствует примитивная эквивалентность /3 с условием (а \ X*) С /3 и Х*//3 является более чем одноэлементным аддитивным множеством. Если тако­ го /3 не существует, то X называется аддитивно неразложимым. 5) Примитивное множество Y называется глобальным в X , если су­ ществует примитивная эквивалентность у такая, что (а \ X*) С у и (YHX*) = (Х*П2Г) для некоторого 7-класса Z. Эквивалентность 7 назовем

156

Е. А. Палютин

глобальным носителем Y в X. 6) а \ Х*-класс а £ X называется свободным в X, если для любой примитивной формулы Ф(х) из (аП Ф(С)) ф 0 следует (6 Г) Ф(С)) Ф 0 для любого Ь 6 X, Л Е М М А 1.7, Пусть X — о.п. множество, Y — примитивное мно­ жество, а — образующая эквивалентность множества X, и множество Y является (а \

X*)-замкнутым.

(1) Если а — свободный элемент X и a CY,

то Y глобально в X.

(2) Если X — аддитивное множество, то Y глобально в X. ДОКАЗАТЕЛЬСТВО. (1) Пусть /3 - носитель множества У. По­ скольку элемент а свободный, из леммы 1.1 получаем (а \ X*) С /3. Таким образом, /3 — глобальный носитель Y в X. (2) Следует из леммы 1.6. Л Е М М А 1.8. Непустое о. п. множество X тогда и только тогда неприводимо, когда существует свободный в X элемент а G X . ДОКАЗАТЕЛЬСТВО. Пусть а — образующая эквивалентность мно­ жества X. Если X неприводимо, то по теореме компактности найдется такой а € X*, что а £ Ф(С), если X* £ Ф(С) и Ф(С) является (а \ X*)замкнутым. Предположим, что X* П а а не свободен в X , т.е. найдутся такие Ь,с 6 X* и такая примитивная формула Ф(х), что а(а, Ь), Ф(Ь) и (X* П а с П Ф(6)) = 0 . По теореме компактности для некоторой примитив­ ной эквивалентности S имеем (а \ X*) С S и (6сП Ф(С)) = 0 . Это проти­ воречит выбору а, если взять формулу Ф(х), определяющую ^-замыкание множества Ф(С). Другая часть утверждения тривиальна. Л Е М М А 1.9. Пусть X — /^-примитивное

множество, А — его

носитель, т С а — примитивные эквивалентности, X С dom г, прими­ тивная формула Ф(х,у, u, v) определяет аффинное сложение па множе­ ствах (ХПаЬ)/т,

b G X. Пусть Ф — примитивная формула, аддитивно

или е-связывающая все множества вида X П аа, а € X и т С хФ. Пусть Y — это 0-определимое

примитивное множество, для любого а 6 X

множество ( У П Х П а а ) непусто и не делится хФ-классами. Тогда суще­ ствует примитивная эквивалентность /3, связывающая все множества

157

Примитивно связные теории вида J f l a a , a. £ X, т \ X С /3 и множество (YnX)

целиком содерсисится

в некотором /3-классе. ДОКАЗАТЕЛЬСТВО. По теореме о компактности существуют при­ митивная эквивалентность А* такая, что А С А * , для а* = (а П А*) вы­ полняется г С а*, а для любого a G X имеют место [а* a : хФ] > 1 и [(ГПе**а) :хФ] = 1. С л у ч а й 1: Ф определяет аддитивную связь. Рассмотрим формулу /3(х, у) = ЗиЭуЗу'(Ф(х, у', u, v) Л Ф(у, у', v, v) Ли е Y Av e У Л а * ( х , и ) Л а * ( у , у ) ) . Ясно, что эта формула (х,у)-рефлексивна; следовательно, она является эквивалентностью (замечание 1). Из примитивной нормальности теории следует, что эта формула имеет искомые свойства. С л у ч а й 2:Ф определяет е-связь. Нетрудно проверить, что искомы­ ми свойствами будет обладать /3(х,у) = 3 u 3 v 3 y ' 3 v ' ^ ( / i , v ; ) Л Ф(х,у') Au£Y

Av

£YA

Aa*(x,u)/\a*(y,v)A*(y,,v',v,y)). Л Е М М А 1.10. Пусть X — мультиаддитивное неприводимое о. п. множество, а — его образующая эквивалентность и Z — 0-определи­ мое (а Г X*)-замкнутое

примитивное множество и X* £ Z. Тогда су­

ществует такая примитивная эквивалентность /3, что (а \ X*) С /3, X*lfi

~ нетривиальное аддитивное множество и ZПХ*

содерсисится в

некотором /3-классе. ДОКАЗАТЕЛЬСТВО проводится индукцией по степени п мультиаддитивности множества X. Если п == 1, то утверждение следует из лем­ мы 1.7(2). Пусть («о, ..., а п) ~" мультиаддитивная последовательность для X, г = {oin-\ П 7) и a* = (« П 7)? г Д е 7 ~ носитель множества X. По лемме 1.8 существует свободный в X элемент а = а*а, где а Е X*, Рас­ смотрим множества Y = га и V = (Z П У). Если V = 0 , то по теореме компактности существует такая примитивная эквивалентность £, что т С 6 и ( 2 П < 5 а ) = 0 . Тогда множество W — &Z будет r-замкнутым и, по лемме

158

Е. А. Палютин

1.7(2), глобальным в X. В качестве /3 возьмем носитель W в X. Предпо­ ложим, что V ф 0 . По индукционному предположению существуют такие примитивная эквивалентность s и примитивная формула Ф(х, у, u, v), что (a \ Y) С £, |У/е| > 1, Ф задает на Y/s аффинное сложение и V содержит­ ся в некотором £>классе. Поскольку элемент а свободен, то X* С dom£. По примитивной связности теории Г, лемме 1.5 и теореме компактности су­ ществуют такие примитивные формулы Фо> -, Ф*» ч т о ДОЯ любого b E X* найдется г ^ к такой, что множества Y/s и тЪ/s аддитивно или е-связаны формулой Ф,-. Поскольку а свободен в X, все предыдущие свойства имеют место при замене У на любой r-класс r b , b G X*. По замечанию после лем­ мы 1.4, лемме 1.6 и лемме Ноймана [9] найдутся такие j ^ к и примитив­ ная эквивалентность А конечного индекса т в 1 , что г С А и для любых А-эквивалентных Ь, с Е X* формула Ф^ связывает тЬ/s и тс/s. ПО лемме 1.9 существует примитивная эквивалентность /3', связывающая r b / e , rc/s для любых Ь, с € (X* П Аа) и Z П Аа содержится в некотором /З'-классе. Поскольку а свободен, по лемме 1.1 предудущие свойства /3' выполняются с заменой а на произвольный d E -X"*. Если га = 1, то в качестве /3 возьмем /3'. Доказательство завершаем индукцией по га, используя леммы 1.8, 1.9, 1.1 и тот факт, что а свободен.

§ 2. Основные леммы Л Е М М А 2.1. Пусть X, Y — о. п. копии, а — их образующая эквивалентностъ, /3 — примитивная эквивалентность, а С /3 и /3 имеет конечный индекс в X. Тогда индексы /3 в X uY

совпадают.

ДОКАЗАТЕЛЬСТВО. Предположим, что лемма неверна и индекс п = [X : /3] является минимальным среди всех контрпримеров к утвер­ ждению леммы. Из определения примитивной связанности теории следует, что копии одноэлементного множества не более чем одноэлементны. Сле­ довательно, п > 1. Так как множества Х/0 и Y//3 примитивно связаны и имеют различную мощность, то найдутся их подмножества, образующие контрпример к лемме с меньшим упомянутым индексом.

159

Примитивно связные теории

Л Е М М А 2.2. Пусть X — о.п. множество, Хо, ...,^fc — глобальные в X примитивные множества, X* С |J{Xo, ...,Х*} и X* <£. \J{X\, ...,Х&}. Тогда существует примитивная эквивалентность /3, являющаяся носи­ телем множества Хо в X и имеющая конечный индекс в X. ДОКАЗАТЕЛЬСТВО. По лемме 1.2 ограничения о. п. эквивалентностей на множество X образуют решетку перестановочных эквивалентностей. По основной теореме из [10] Х 0 имеет конечный мультииндекс в X. По лемме 2.1 из конечности мультииндекса следует конечность индекса. Лемма доказана. ОПРЕДЕЛЕНИЕ. 1) Если Z является Д-примитивным множеством, то через Z+ обозначим множество {Ф(х) | Ф — примитивная формула и (Ф(С) П Z) ф 0 } . 2) Д-примитивные копии X и У называем примитивно

эквивалент­

+

ными и пишем X « У, если выполняется (Х)+ = ( У ) . Если {а} » {Ь}, то пишем а « Ь. 3) Для о.п. копий X, У пишем X « У, если (X*) « (У*). Л Е М М А 2.3. Пусть X,Y

— о.п, копии, а — их образующая экви­

валентность, X конечно, X « У и а € X*. Тогда (а Г Х*)а « (а Г У*)Ь для некоторого Ь £ У *. ДОКАЗАТЕЛЬСТВО. Рассмотрев вместо X* и У* их пересечения с (а \ Х*)-замкнутыми 0-определимыми примитивными множествами Z, для которых а € Z, можно считать, что (а \ Х*)а свободен в X . По лемме 1.8, X неприводимо. Из леммы 2.1 и условия X « У получаем, что для любого 0-определимого (а \ Х*)-замкнутого примитивного множества V мощности множеств (X*C\V)/a и (Y*C\V)/a совпадают. По лемме о покры­ тиях конечного множества (см. [1, лемма А]) множество У неприводимо. По лемме 1.8 найдется свободный в У элемент (а \ У*)Ь. Из леммы 1.1 следует, что (а \ Х*)а « (а \ У*)Ь. ОПРЕДЕЛЕНИЕ. Пусть X", У — о.п. копии и примитивная формула Ф аддитивно или е-связывает X и У. Тогда эквивалентность хФ (совпада­ ющая с уф) называется ядром этой связи.

Е. А. Палютин

160

Л Е М М А 2.4. Пусть а, /3 — ^-примитивные X — ^-примитивное

эквивалентности,

множество и X С dom (а П /3). .Бели для некото­

рого a € X выполняется (X П аа) = (X П /За), т о
формула

Ф(х, у, u, v) определяет аффинное сложение на множестве X и истинно Ф(Ь, Ь, Ь, Ь) для некоторого b G У*. Тогда Ф(х,у, u, v) определяет аффин­ ное сложение на множестве У. ДОКАЗАТЕЛЬСТВО. В силу леммы 1.3(1) достаточно показать, что Ф(х,у, u,v) определяет терм Мальцева на множестве У. Из леммы 1.1 следует Ф(Ь, Ь, Ь, Ь) для любого b £ У* и а \ X* = хФ \ X* = уФ Г X* = иФ Г X* = уф Г X*. Так как дая любых с, d E X* имеем Ф(с, с, d,d) и Ф(с, d , d , c ) , из Ф(Ь,Ь,Ь,Ь) и леммы 1.1 получаем Ф(а, a, b,b) и Ф(а, b , b , a ) для любых a, b 6 У*. Лемма доказана. Л Е М М А 2.6. Пусть X — о, п. множество, а — его образующая эквивалентность,

/3 — примитивная эквивалентность и (а \ X*) С /3.

Пусть а 6 X*, X* П /За — свободный элемент в Х*//3 и множество Y = = (X* П /За)/а? отплсеченко распадается. Тогда X отмеченно распадается. ДОКАЗАТЕЛЬСТВО. По условию существует примитивная экви­ валентность 7 конечного неединичного индекса п в Y и 0-определимое, (7 Г У*)-замкнутое множество Z, делящее множество У. Будем считать, что такое п минимально. Поскольку Х*П/За — свободный элемент в X*/(i, то X* С dom 7- По теореме компактности можно считать, что а С 7 Q /5. Пусть а* = о: Г -X"*, 7* = а Г X*, /3* = а Г X*. Множество У/7 обозначим через С/. По лемме 2.1 для любого b G X* множество 11ъ = /5*Ь/7 содержит п элементов. Так как множество 17 примитивно связано с множеством С/ь для любого b 6 X*, то по теореме компактности, лемме 1.5 и замеча­ нию после леммы 1.4 существует такое покрытие множества X* конечным семейством /3*-замкнутых примитивных множеств ZQ, ...,Z*, содержащих

Примитивно связные теории

161

У*, что для каждого г ^ к существует примитивная формула Ф,, адди­ тивно или е~связывающая множества 11ъ и Uc для любых Ь, с 6 Zi. Будем считать, что ZQ существенно в этом покрытии. Поскольку а Е Z,-, г ^ &, то, в силу свободы /3*а в Х*//3, множества Z,, г ^ fc, глобальны в X, По лемме 2.2 существует носитель S множества Z0 в X конечного индекса в X. Поскольку /3*а свободен в Х*//3, по лемме 2.4 формула Фо связывает любую пару ^-эквивалентных /3*/у-кла,ссов. С л у ч а й 1:Фо аддитивно связывает ^-эквивалентные /3*/у-классы. Можно считать, что ядро этой связи содержится в /3. Рассмотрим формулу 0(х, у) = 3u3v3y'(u € Z Л v G Z Л Ф 0 (х, у', u, v) Л Ф 0 (у, у', v, v)). Из определений аддитивной связанности и примитивной нормальности следует, что в определяет примитивную эквивалентность конечного ин­ декса в X*. В силу минимальности индекса п множество, определимое формулой Ф(х) = 3u(u 6 Z Л Ф 0 (и, х, и, и)), будет делить множество Х/в. С л у ч а й 2: Фо определяет эквивалентность ??, е-связывающую ^-эк­ вивалентные /3*/7~классы. Можно предполагать, что //-классы являются 7-замкнутыми и 7] С S. Поскольку для b 6 X* множества /3*Ь/7 конечны и индекс 8 в X конечен, то индекс т) в X* также конечен. С л у ч а й 2а: (X* HZ П т/а) = 0 . По теореме компактности найдется примитивное множество Хх, содержащее X*, для которого выполняется (Хх П Z П г}&) = 0 . Пусть щ — носитель множества Хх и щ = (rj П 7/i). Тогда 0-определимое примитивное множество

У =

{Ь\(гПтюЬ)ф0}

будет делить множество Х/т). Таким образом, X/r/ — конечное отмеченное множество. С л у ч а й 26: (X* П ZП г/а) ф 0 . Определим эквивалентность 0(х, у) = 3u3v(u Е Z A v е Z А т/(и, v) Л /3(х, и) Л /3(у, v)).

Е. А. Палютин

162

Поскольку индекс г} в любом ^-классе конечен, то индекс в в любом ^-классе также конечен. Тогда индекс и = (г) П в) в X также конечен. Из примитивной нормальности теории следует, что для любого элемента b E G X* либо (ZDxb)

= 0 , либо каждый (7/Пу8)-класс, содержащийся в x b ,

имеет непустое пересечение с Z. Из минимальности п получаем (ZHxa)

=

= 0 , следовательно, Х / х является конечным отмеченным множеством. Л Е М М А 2.7. Пусть Х) У —о. п. гсогаш. Если Х} У не являются е-связанными и X неприводимо, то X

мулътиаддитивно.

ДОКАЗАТЕЛЬСТВО. Пусть а — образующая эквивалентность ко­ пий X , У , /3 — носитель множеств Х*,У* и а* = (а Г) /3). По лемме 1.8 существует такой а 6 X*, что а*а — свободный элемент множества X. Возьмем произвольный кортеж b 6 Y*. Рассмотрим

максимальные

последовательности

А-примитивных

множеств (X,- | г < A), (Yi \ г < А) и примитивных эквивалентностей (#,-4-1 | г + 1 < А), где А — ординал, со следующими свойствами:

(1) Хо = х\ у0 = У*; (2) Xi = P K ^ i I J < г ) и YJ = fK*j I 3 < г ) дая предельного г < А; (3) а С a i + b t + l < A; (4) Х 8Ч 1 = рГ,- П а,-+1а) и l-+i = (Yi П a i + i b ) , г + К (5) а,-+1 — ядро аддитивной связи Xi/а и 1^/а,

А;

г + 1 < А.

Предположим, что А — предельный ординал. Считая Х\ = fli-^i I г < А} и Уд = П { ^ I * < ^}? получаем противоречие с максимальностью данных последовательностей. Таким образом, А = \i + 1. Покажем, что Хц = а*а и YJj = a*b. Если хотя бы одно из этих равенств не выполняется, то по лемме 1.5 множества Хц/а

и У ^ / а были бы е-связаны или аддитивно

связаны. Если эти множества е-связаны, то поскольку ога свободен и в силу леммы 2.4, множества X , У также е-связаны. Это противоречит условию леммы. Пусть а\ — ядро аддитивной связи Х^/а = (ХмПа\а)

и Y^/a. Полагая Х\ =

и Уд = (У^ПадЬ), получаем противоречие с максимальностью

последовательностей (Xi | % < А), (У; | i < А) и (a,*+i | г + 1 < А). Предположим, что лемма неверна и А — минимальный ординал среди всех контрпримеров к данной лемме.

Примитивно связные теории

163

С л у ч а й 1: ц — предельный ординал. По теореме компактности най­ дется такой ординал у < д, что Ху = (X* П аа) и У 7 = (У* П аЪ). Это противоречит условиям (4) и (5). С л у ч а й 2: /л = у + 1. По лемме 1.3 существует примитивная фор­ мула 3>(x,y,z, u), определяющая терм Мальцева на множестве Х у / а , и а \Ху

= (хФ) ГХ 7 . С л у ч а й 2&: у = 6+1. Так как Л минимален, Х*/ау

является муль-

тиадцитивным. Пусть (Ai,..., Ап) — мультиаддитивная последовательность для Х*/^.

Поскольку аа свободен, выполняется Ф,(а,а,а,а) для всех

а 6 X*. Из леммы 2.5 следует, что (А0, Ai,..., А„) является мультиаддитивной последовательностью для А", где Ао = (Ai П а ) . Случай

26: у — предельный ординал. По теореме компактно­

сти найдется такой непредельный S < у, что Ф(х, y , z , u ) определяет терм Мальцева на множестве Xs/a. Х*/а$

Из минимальности А получаем, что

является мультиаддитивным. Пусть (Ах,...,Ап) — мультиаддитив­

ная последовательность для Х*/а$. Поскольку а а свободен, выполняется 4>t*(a, а, а, а) для всех a G X*. Из леммы 2.5 следует, что (А0, Ai,..., Ап) будет мультиаддитивной последовательностью для X , где Ао = (Ai П а ) . Л Е М М А 2.8» Пусть X, Y — о. п. копии, которые аддитивно нераз­ ложимы и X примитивно неприводимо. Пусть S — их образующая экви­ валентность, у — их носитель, Хо,...,Х„ — 0-определимые

(бПу)-зам-

кнутые примитивные множества и выполняются условия:

(а) У* С L№,...,*„}, (b)i^U№,..,U (c) (*)+ С (У)+, (d) (X* П Xi) ф 0 для каждого i ^ п. Тогда X примитивно отмеченно распадается. ДОКАЗАТЕЛЬСТВО. Пусть \ = (уПб).Т1о

лемме 1.8 существу­

ет свободный в X элемент а = Аа, где а 6 I * . По условию (Ь) имеем а 6 (X*\U{-^o» —1 Хп}). В доказательстве данной леммы под глобальными множествами будем понимать глобальные в X примитивные множества, под их носителями — их носители в X. Глобальные множества X,-, Xj назо-

Е. А. Палютин

164

вем подобными, если множества (X*HXi)

и (X*f)Xj)

являются копиями.

В силу леммы 2.4 подобие глобальных множеств A*,-, Xj равносильно тому, что ограничения их носителей на множество X* совпадают. В частности, отношение подобия является эквивалентностью на семействе глобальных множеств среди Х$,..., Хп. Пусть к — число классов этой эквивалентности. Докажем лемму индукцией по числу (п + к). Будем считать, что любое из множеств Хо, ...,-^п существенно в покрытии множества У*. С л у ч а й 1: существуют такие г,j ^ п, что Xi — глобальное мно­ жество с носителем а и (X* П Xj П аа)

ф 0 . Будем считать, что

(X* П Хт П аа) = 0 для т ^i s и (X" П Х т П аа) / 0 для 5 < т ^ п. По теореме компактности найдется носитель а* множества X, в X такой, что (Хт П а* а) = 0 для всех т ^ s. Для каждого т ^ s рассмотрим множе­ ство -Х"^ = а * Х т . Если У* С LK-^СР —J-^"?}» ТО

в

силу s < п утверждение

леммы следует из индукционного предположения. Если это покрытие не имеет места, то для некоторого b G У* выполняется

(Y*n«*bnU{*o°,-,*°})=0Тогда имеет место

y*Ha*bc|J{X e+1 ,...,X n }. Применяя индукционное предположение к копиям (X* П а*а)/<5, (У* П Па*Ъ)/6 и множествам A"s+i, . , Х П , получаем, что (Х*Па*а)/5 примитив­ но отмеченно распадается. Применение леммы 2.6 завершает рассмотрение случая 1. С л у ч а й 2: множества X , У инъективно 6-связаны, т.е. существует примитивная эквивалентность а, связывающая множества X, У и являю­ щаяся их образующей эквивалентностью. Так как У* С U{-^o, - Д п } , то найдется такой j ^ п, что (У* П аа) С Xj. Пусть примитивная формула Ф(я) определяет множество Xj. Пусть у является пересечением примитив­ ных эквивалентностей {ji | г Е / } . Рассмотрим эквивалентность ао(ж,у), определенную пересечением примитивных эквивалентностей (ji(x,y)

ЛЗиЗю(Ф(и) А Ф(и) Aji(u, v) A a(x,u) Ла(у,и)))

Примитивно связные теории

165

для г 6 J. В силу примитивной нормальности теории Т, множества (X* П Xj) и (У* П Ху) являются ао-классами. Поскольку а свободен в X , получаем X* С domao. Таким образом, множество Xj — глобаль­ ное. В частности, к ^ 1. Будем считать, что Х о , . . . , Х т — глобальные, а X m + i , . . . , X n — неглобальные множества. Если для некоторого г ^ п найдется b 6 (Xt- П dom7) такой, что выполняется а(а, Ь), то множество {с j с G X*, а(с, d) и 7(d, b) для некоторого d G X,} будет копией множества (X* П X t ) и содержит а. Элемент а свободен, поэтому X, — глобальное множество. По теореме компактности найдется такое 0-определимое примитивное множество Z, что dom j С Z и (aa П ПХг Г) Z) — 0 для всех i > т. Таким образом, заменив а на а \ Z, можно считать, что все неглобальные множества а-замкнуты. С л у ч а й 2а: к = 1. Пусть /3 — общий носитель глобальных мно­ жеств. Из свойства (с) и леммы 2.4 получаем, что множества (У* П X,), г ^ т , являются (/3 П 7)-классами. Если неглобальных множеств нет, то индекс /3 в У не превосходит (т + 1) и утверждение леммы следует из леммы 2.1. Поскольку случгьй 1 уже рассмотрен, можно считать, что (X* П X; П /За) = 0 , г ^ п. По теореме компактности можно считать мно­ жества X*, г ^ п, ^-замкнутыми. Рассмотрим

и й = (У*ПаР). Так как множества X m+ i> -ч-Xn являются а-замкнутыми, то множество Д покрывается множествами Хо, ...,X m . Так как каждое из них существенно в покрытии множества У*, то множества (У* П ПХо),..., (У* Г)Х т ) попарно не пересекаются и индекс /3 в J? равен ( т + 1 ) . Поскольку а биективно отображает Р//3 на Rffi , то индекс /3 в Р также равен (ш + 1). Из свойства (с) получаем, что (X* П Х 0 ),..., (X* П Хт) по­ парно не пересекаются. Так как Р не покрывается этими множествами, то найдется j ^ ш, для которого выполняется условие (РП Ху) = 0 . Тогда

(х*пх,)си{хга+1,...,хп}.

166

Е. А. Палютин

В силу /3-замкнутости X,-, г ^ п, справедливо (X* П Ху) С Х8 для некото­ рого s £ { ( m + 1),...,п}. Так как

(¥*ПХ^^1){Хт+1,...,Хп}, это противоречит лемме 1.1 и условиям (с), (d). С л у ч а й 2Ь: к > 1. Будем считать, что W и Q — два различных класса подобия глобальных множеств среди Xo,...,X w . Пусть /Зо и /3i — носители множеств из W и Q соответственно. По лемме 1.2 и теореме компактности решеточное объединение е = ((7 П /Зо) V (7 П /3i)) является Д-примитивным. Если для любого Z £ (W U Q) выполняется а ^ eZ, то по теореме компактности найдется примитивная эквивалентность е* та­ кая, что е С е* и дня любого Z £ (W U Q) выполняется а ^ £*Z. Заменяя каждое Z £ (WUQ) на e*Z, получаем систему 0-определимых примитив­ ных множеств, удовлетворяющую условиям леммы и имеющую меньшее к. Поэтому можно считать, что для некоторого Z £ (W U Q) выполняется а £ eZ. Элемент а свободен, поэтому X* С eZ. Пусть /3,- — носитель Z. Из леммы 1.2 вытекает X* С (т П /3(i_,-))2. Следовательно, выполняются условия случая 1. С л у ч а й 3: пусть нарушаются условия случая 2. По леммам 1.5 и 1.4, X и У не являются аддитивно связанными. Возьмем минимальную Апримитивную эквивалентность <*, связывающую X и У. Пусть /3 =

(уПа).

По условию данного случая и теореме компактности |/За/£| > 1. Так как а свободен в /За/5, то по леммам 1.8 и 2.7 множество /За/5 мультиаддитивно. Рассмотрим множество 5 = { i | i < n, (Х,-П/За) = 0 } . В силу теоремы компактности найдется примитивная эквивалентность а* такая, что а С а* и для каждого i £ 5 справедливо (X, П /3*а) = 0 , где /3* = (7 П о?*). Сделав соответствующую замену, можно считать, что для каждого i £ 5 множества X,- являются /3*-замкнутыми. Если У* С Uies-^»* то, переходя от X, У к Х*/а*, У* £ U i € 5 ^ '

т о на

Y*/a*, получаем условие случая 2. Если

-йдется элемент b £ У*, для которого

/ЗЬ С \J{Xi \i^n,it

5}.

Примитивно связные теории

167

Поскольку а свободен в X , из условия (с) вытекает (/За)"1" С (/ЗЬ) + . Отсюда, в силу лемм 2.5 и 1.1, из мультиаддитивности /За/£ получаем мультиаддитивность /ЗЬ/£. По лемме 1.10 существуют 0-определимые глобальные в /За/<$ множества X/, i ^ n, г $ 5, для которых X,- С X/ и /За ^ ^ - По лемме 1.1 получаем глобальность Х[ в (ЗЪ/8. Поскольку а свободен, то

/За £ \J{X'i \i$n,ii

S}.

Так как /ЗЬ С l j { ^ , '

\i^n,i
и (Х,*П/За) ^ 0 , г; ^ п, г ^ 5, это противоречит следующему утверждению: Если выполняется посылка леммы 2.8 без условия аддитивной неразложимости X, то среди Хо, ...,Х П найдется неглобальное

(*)

множество. Предположим, что это не так и п минимально среди контрпримеров. Пусть oti — носитель Х{ и а * = (а, Г) 7)* Расширив, если необходимо, X,-, можно считать, что для любых i,j ^ п либо (е) Х{ является а^-замкнутьш, либо (/) (Х*иУ*) С ctjXi. Если для любых г, j ^ п выполняется (е), то все X,-, г ^ п, подобны, что противоречит условиям (с), (d) и лемме 2.1. Пусть для k,s ^ п выполняется (/). Пусть W состоит из aj-замкнутых множеств среди Хо,...,Х п . В силу минимальности п найдется b G У* с условием (У* П a s b) %, \JW. Ясно, что множества а*&/8 и а*Ь/£ вместе с Xi £ W, i ^ п, образуют контрпример с меньшим п. Получили противоречие с минимальностью гг. Л Е М М А 2.9„ Пусть X, У — Д-приштшвные яопгш, X но пеприводимо и X « У ' . Тогда У примитивно

примитив­

неприводимо.

ДОКАЗАТЕЛЬСТВО. Пусть а - свободный элемент в X и у - сви­ детель для копий X и У. Возьмем минимальную Д-примитивную экви­ валентность а с условиями: а С 7, a G dome* и а а « a b для некоторого b G У. Она существует по теореме компактности. Если |аа| = 1, то по лем­ ме 2.1 получаем | a b | = 1, и лемма доказана. Предположим, что |аа| > 1. С л у ч а й 1: а а аддитивно разложимо. Рассмотрим примитивную эк­ вивалентность /3, для которой a G dom/З и (аа)//3 аддитивно и более чем

168

Е. А. Палютин

одноэлементно. В силу а а « a b и леммы 2.5, множество Z = (о?Ь//3) также аддитивно. Из минимальности а следует, что Z приводимо. Это противо­ речит леммам 1.7(2), 2.2, 2.1 и лемме А из [1]. С л у ч а й 2: а а аддитивно неразложимо. Из а а • « a b и леммы 2.5 следует аддитивная неразложимость множества a b . В силу минимально­ сти а множество a b приводимо. В силу условия а а « a b найдутся такие 0-определимые примитивные множества Хо, ...,Х„, для которых выпол­ няются условия леммы 2.8 с заменой X и Y соответственно на а а и a b . По лемме 2.8 существует примитивная эквивалентность г\ с нетривиаль­ ным конечным индексом в аа. Из условия а а « a b и леммы 1.1 получаем a b С dom г). По лемме 2.3 найдется b 6 a b с условием (аПт])а » ( а П т ? ) Ь . Получили противоречие с минимальностью а.

§ 3. Доказательство теоремы 1 Утверждение теоремы 1 равносильно тому, что для любых кортежей а и b условие а « Ь влечет а = Ь . Пусть а = (ai,...,a n ), b = (bi,...,6„) и а « Ь . Возьмем произвольный элемент a n + i G С. По известному критерию элементарной эквивалентности достаточно найти такой элемент 6n+i б С, что (a,a n +i) « (b, b n +i). Пусть X = {{а, с) | t p + « a , a n + 1 » С t p + « a , c » } , Y = {(b,c) | t p + « a , a n + 1 » C t p + « b , c » } . Из условия а « Ь получаем JC « У. Ясно, что (а, an+i) является свободным элементом множества X, Поэтому X является примитивно неприводимым. По леммам 2.9 и 1.8 во множестве У существует свободный элемент (Ь, с*). Ясно, что в качестве b n +i можно взять с*. Теорема доказана.

ЛИТЕРАТУРА 1. М. Ziegler, Model theory of modules, Ann. Pure Appl. Logic, 1984, 26, N 2, 149-213.

Примитивно

2. Е.А.Палютин,

связные

теории

169

Элиминация кванторов для коммутативных теорий, До­

клады РАН, 363, N 3(1998), 301-303. 3. E.A.Palyutiriy

Commutative theories, in: Abstracts of Logic Colloquium'98,

Prague, 1998. 4. E.A.Palyutin,

Additive theories, in: Proceedings of Logic Colloquium'98

(Lectures Notes in Logic, 13), ASL, Massachusetts, 2000, 352—356. 5. A.Pillay, Countable models of stable theories, Proc. Am. Math, Soc, 89, N 4, 1983. 6. S. Shelah, Classification theory and the number of non-isomorphic models (Studies in Logic and the Foundations of Mathematics, 92), Amsterdam a. o., North-Holland, 2nd edition, 1990. 7. Е.А.Палютин,

Нормальность хорновых теорий с немаксимальным спек­

тром, Алгебра и логика, 24, N 5 (1985), 551—587. 8. Е.А.Палютин,

Элиминация кванторов в хорновых теориях с малым чис­

лом моделей, Алгебра и логика, 30, N 5 (1991), 513—516. 9. B.H.Neumann,

Groups, covered by permutable subsets, J. Lond. Math. Soc,

1954, 29, 236-248. 10. Е.А.Палютпин,

О покрытиях классами перестановочных эквивалентно-

стей, Алгебра и логика, 34, N 3 (1995), 316-322.

Адрес автора: П А Л Ю Т И Н Евгений Андреевич, РОССИЯ, 630090, г. Новосибирск, пр. Ак. Коптюга, 4, Институт математики. e-mail: [email protected]

Поступило 15 апреля 1999 г.