1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 32

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 32)

Приведем одну полезную характеризациюаксиоматизируемых классов.Теорема5.2.2.Класс К алгебраических систем сигнатуры Еаксиоматизируем тогда и только тогда, когда он замкнут отно­сительно элементарной эквивалентности и ультрапроизведений.До к аз ат ель ст в о.Пусть Каксиоматизируемый класс. Оче­-видно, что К замкнут относительно элементарной эквивалентности.Замкнутость К относительно ультрапроизведений следует из теоремы3.3.5.Пусть К замкнут относительно элементарной эквивалентностии ультрапроизведений.Пусть2tДостаточно показать, чтоЕKE(Th(K)). Для каждого ФЕ Th(2t) 1 t>Ф ----, Ф}. Ясно,ЕTh(2t)KE(Th(K)) <;К.рассмотрим множества=иФ = {Фчто семейство Х{иФ I Ф ЕЕ Th(2t)} будет центрированным.

По предложению 2.3.2 существуеттакой ультрафильтрФ ЕTh(2t)Dна множествеTh(2t),что Х<; D.Для любогосуществует система ~Ф Е К, на которой истинно Ф, так какв противном случае ~Ф ЕTh(K),что противоречит2tЕKE(Th(K)).Гл.154Теория моделей5.= D-prod ~Ф, и этим теорема будет доказана. ЕслиF Фо для всех Ф Е ИФо· Так как ИФ 0 Е D, то по теореме3.3.5 получаем D-prod ~Ф F Фо.

Если Q( F Фо не имеет места, тоQ( F ·Фо и по только что доказанному D-prod ~Ф F ·Фо. Следователь­но, D-prod ~Ф F Фо не имеет места.ОПокажем, что Q(Q(F Фо,то ~wПредложениеПересечение любого множества аксиома­5.2.3.тизируемых классов сигнатуры ~ и объединение конечного числааксиоматизируемых классов сигнатуры ~ являются аксиоматизи­руемыми классами.Доказательство.ПЕслиKi = K"E(Zi), iЕI,то очевидно, чтоК"Е ( U zi). Пусть Ki = K"E(Zi) и К2 = K"E(Z2). РассмотримiEJмножество Z = {Ф V Ф I Ф Е z,, Ф Е Z2}.

Покажем, что К1 U К2 =Ki =iEI= K"E(Z).Включение К1 U К2 <;;;и сигнатура Q( равначто Q(F ·Фо /\ 'Фо.Определение.= K"E(Z)K"E(Z)очевидно. Пусть Q(Тогда существуют такие Фо Е~-Так как ФоЕсли К-Z1fj.К, U К2и Фо ЕZ2,V Фо Е Z, то Q( fj. K"E(Z).Окласс алгебраических системдля некоторого конечного множества аксиомZ,и К=то класс Кназывается конечно аксиоматизируемым.Заметим, что если К конечно аксиоматизируем, то, взяв конъюнк­цию конечного множества{ Ф}аксиом для К, получим множество аксиомZдля К, состоящее из одного предложения Ф.Если К-класс алгебраических систем сигнатуры~.то через Кобозначим дополнение К в классе К"Е(125) всех систем сигнатурыПредложениесигнатуры~-5.2.4.Пусть К-~-класс алгебраических системКласс К является конечно аксиоматизируемым тогда итолько тогда, когда К и К являются аксиоматизируемыми.До к аз ат ел ь ст в о.Если класс К конечно аксиоматизируем, тоК = К"Е ({Ф}) для некоторого предложения Ф сигнатуры ~- ТогдаК= К"Е( {·Ф} ).

Пусть К и К аксиоматизируемы. Так как КК= 125,nК=K"E(Th(K))и К=K"E(Th(K)),то по теореме компактности суще­ствуют такие конечные множества Хне имеет модели. Так какTh(K)<;;; Th(K) и У<;;; Th(K), что Х U УиTh(K)замкнуты относительновзятия конъюнкций, то можно считать, что Хкак Ф/\Фмножества-={Ф} и У= {Ф}. Тактождественно ложная формула, то на всех моделях Q({ Ф} истинно предложение·w, т. е. Q( fj. К и,следовательно,Q( Е К. Значит, К= К"Е({Ф}).ООпределение. Формула Ф называется \/-формулой (3-формулой,\/3-формулой),еслиФ=\/х1...

\/xk Ф(Ф=3х1... 3xk Ф,Ф=§ 5.2.Аксиоматизируемые классы= \lxi ... \lxk:3Yi ... :3уп w),Калгебраическихгдебескванторная формула. Классw -систем155называется\1-аксиоматизируемым(:3-аксиоматизируемым, \1:3-аксиоматизируемым), если К=гдесигнатурыI:.Предложение(:3-формула)21)5.2.5.сигнатурысигнатуры 'Е,(вK'E(Z),множество \/-предложений (:3-предложений, \1:3-предложений)Z -ai, ... ,akа).'Е,Пусть{21i I iЕxk)\!-формула-алгебраические-Е А.

Тогда из истинности Ф(ai,следует истинность Ф(а~,б). ПустьФ(х 1 , ••• ,S:В21 <;;;... , ak)в21системы... ,ak)в S:В(в S:В).направленное семейство алгебраическихI} -систем сигнатуры 'Е и \1:3-предложение Ф сигнатуры 'Е истинно вовсех21i, iЕ J. Тогда Ф истинно в21 =U 21i.iEJДоказательство. а). Так как значение tQ!['Y] терма t при ин­терпретации 'У в А совпадает со значением t'В ['У], то а) выполняетсядля атомарных формул Ф. Для бескванторных формул утверждение а)получается индукцией по длине Ф. Теперь остается лишь воспользо­ваться определением истинности формул с кванторами\1и:3.б). Пусть предложение Ф =\lx1 ...

\lxk:3yi ... :3ynw(x1, ...... , Уп), где Ч1 - бескванторная формула, истинно на всехВозьмем произвольные а1,... , akЕ А. Тогда а1,... , ak,xk,Yt,···21i, i Е J.Е А для неко­F :3yi ... :3ynW(a1, ... ,ak,Yl,···,Yn)21 F :3у1 ... :3уп w(ai, ... , ak, Yt, ...торого i Е J и, следовательно, 21iTaк как 21i <;;; 21, то в силу а) имеем··· ,Уп).иОЛемма 5.2.6. Пусть Г Wo(xi, ... , Xk) - формула21 <;;;множество предложений сигнатурыI:сигнатуры 'Е. Если для любых моделейS:В множества Г, имеющих сигнатуру 'Е, и любых а 1 , ... , ak Е Аиз истинности. .

. , ak). . . , xk)в21Wo(ai, ... , ak)в S:В (в21)следует истинностьWo(ai, .. .Xo(xi, .. .Wo).(в S:В), то существует \!-формула (:3-формула)сигнатуры 'Е, для которой Г 1>До к аз ат ель ст в о. Вместо и1,новых констант,w1 = (wo)~.ем символов констант из(wo---.Хо)/\ (Хо---.пишем и. Пусть... , ukсигнатура 'Е' получается изdиZ = {Ф I Ф - \/-предложение сигнатуры 'Е' и ГРассмотрим множество ГU Z U {'Ч11}.существуют Фа, ... , Фп Е Z такие, что Г 1>!>w1 ---.Ф }.Если оно несовместно, то(Л Фi ---.

Ч11). Тогдаi~nг 1> ( _Л Фi - w1) А (w1 - Л Фi)·i~nd - наборI: добавлени­i~nГл.156ПустьDo -Теория моделей5.дерево доказательства секвенцииГо f-- ( _Л Фi--+ w1) А (w1--+ _Л Фi),i~nгде Го-i~nподходящая конечная последовательность элементов множе­ства Г. Так как эта секвенция не содержит свободных переменных, томожно считать, чтоне встречаются вxi, ... , XkDo.Сделаем подста­новку (Do)~(:::::~~. Это снова дерево доказательства секвенцииОстается заметить, что формула Л (Фi)~ эквивалентна 'v'-формуле.i~nПредположим, что ГU Z U {'w 1}совместно имножества предложений.

Установим, что Гтельно, если SВ-модель множества Гморфное вложение r.p моделиноw1,r.p(Qt)Qtто по условию леммыв SВw1~ SВ, а следовательно, и вмоделей SВ для Гимеем ГU D(Qt)С>U D(Qt)·w1.1-- ЛДействи­Если бы в SВ было истин­что невозможно. Итак, для всехSВ С>·w1.По теореме ополнотеСуществуют конечная последовательность Гоэлементов множества Г и предложения Хо,секвенция Гомодель этого·w 1.было бы истинно и в подсистемеQt,имеемС>то существует изо­U D(Qt),r "Е'.Qt -U D(Qt)Xi--+ ·q,1...

, ХпЕD(Qt)такие, чтодоказуема. Заменяя константы вида са наi~nпеременные, не входящие в формулы из Го и вWo,и навешивая на этипеременные кванторы существования, получим доказуемую секвенциюТогда доказуема секвенцияСледовательно, \/у· ( _Л (Xi)}a) Е Z, Qt F \/у· ( _Л (Xi)}a), что пpoi~nтиворечит тому, что Хо,... , Хпi~nЕD(Qt).Второй вариант леммы получается из первого заменой формулына·wo.WoО§ 5.2. Аксиоматизируемые классыТеоремаПусть К5.2.7.157аксиоматизируемый класс алгебраи­-ческих систем сигнатуры :Е.а). К 3-аксиоматизируем{==}К замкнут относительно надси­{==}К замкнут относительно подси­стем.б).

К \;/-аксиоматизируемстем.До к аз ат ель ст в о.Утверждения ===} следуют из предложения5.2.5.а). Покажем сначала, чтодля любого предложениясуществует такое предложение ФФ ЕTh(K),Ф Ечто t>ФФ--.Th(K)Ф и для123 алгебраических систем сигнатуры :Е из Q( F Ф Ф123 F Ф. Предположим, что это не так, т. е. существует та­кое Фа Е Th(K), что для любого Ф Е Th(K) существуют системы12t,i, ~ 123,i, сигнатуры :Е, для которых из С> Ф --. Фо следуют l2t,i, F Фи 123,i, F 'Фа. Пусть D ультрафильтр на множестве Th(K), со­держащий центрированное семейство Х = {UФ I Ф Е Th( К)}, гдеUф = {Ф Е Th( К) 1 С> Ф --. Ф}.

Рассмотрим системы 12to = D-prod l2t,i, и!Во = D-prod 123,i,. Так как 12t,i, ~ 123,i, для всех Ф Е Th(K), то суще­ствует 12t, ~ !Во, l2t1 ~ 12to. Из теоремы 3.3.5, включения Х ~ D и изтого, что 12to ~ l2t1, получаем l2t1 Е KI:(Th(K)) = К и !Во F ·Фа. Этолюбой пары Q( ~следуетпротиворечит замкнутости К относительно надсистем.Для любого предложения Ф Е={ФФV ·Ф}и Фо=Отсюда получаем, что ХФи в силу {Ф, ФФ} ~Th(K)по лемме5.2.6(полагаем Г=Ф) существует такое 3-предложение ХФ, что--.Th(K)ство 3-предложений {ХФФ-тождественно истинное предложениетакже ХФ ЕI Ф Е Th(K)}Th(K).Следовательно, множе­будет системой аксиом для К.Для того чтобы получить доказательство б), нужно в доказатель­стве а) заменить Q( ~123иl2t,i,~123,i,наственно и применить другую часть леммыОпределение. Предложение вида \:/х,123 ~ Q(5.2.6.и... \;/xkQ,123,i,~l2t,i,соответ·ОгдеQ -атомарнаяформула, называется тождеством.

Предложение вида(5.3)гдеQo, Q,, ... , Qп -атомарные формулы,называется квазитожде­ством. Аксиоматизируемый класс К называется многообразием (ква­зимногообразием), если существует система аксиомщая из тождеств (квазитождеств).Zдля К, состоя­Гл.158Таккактождество\lxi ... \lxk+l (xx+lR:;;Xk+l5.Теория моделей\lxi, ... \lxkQ эквивалентно квазитождествуQ), то многообразие является квазимного­---+образием.ры= ({0}, vEE)Систему Er.I;, если= {0}µ(s)vEE(s)Условиеназовем единичной системой сигнату­определяет систему(5.4)для всех s ЕEr.R.(5.4)однозначно, так как на одно­элементном множестве для любого п Еwсуществует только однаn-местная функция.Предложение5.2.8.а). Любое квазимногообразие К сигнатурыI; замкнуто относительно фильтрованных произведений и содер­жит единичную системуEr..б). Любое многообразие замкнуто относительно гомоморфныхобразов.Доказательство.а) Так как вEr.

истинно Qo(0, ... ,0), дляQo(xi, ... , Xk) сигнатуры I;, то в Er. истинно(5.3). Для того чтобы показать замкнутость Клюбой атомарной формулылюбое квазитождествоотносительно фильтрованных произведений, достаточно показать, чтолюбое квазитождество(5.3)труВ силу леммына множествеусловно фильтруется по любому филь­формула3.3.3 достаточно показать, чтоQo)(xi, ... ,xk) условно фильтруется по D.ПустьиDI.((Q1 /\ ... /\Qп)---+fi, ... , fk Е I-prodAiПредположим, что в. .

Характеристики

Список файлов книги