1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 37
Текст из файла (страница 37)
(Указание. Добавитьв сигнатуру константы {с} U { саТ сZьмножеством= {v1~ сь} UIаЕ А}, рассмотрев теориюIааксиом D*(21) U {'с ~ Са{~v1~ СаIаЕ А}Е А}и типыи применить теорему обопускании типов.)2.Показать, что если в Ф или в Ф входит равенство, то в теореме5.4.7 б)тогда,нельзя потребовать чтобы равенство входило в Х толькокогда оно входит в Ф ипримеры с1 ~ с2 t>3.Ф.r(c1) V ~r(c2),r(c1)(Указание.А~r(c2)Рассмотреть[> с1 ~ с2.)Формулу Ф назовем отрицательной, если у формулы Ф 1, полученной из Ф заменой всех ее подформул вида Ф1-+~Ф1равенстваVФ2каждоевхождение символаотношенияиФ2 наявляется отрицательным. Показать, что доказуемые формулы немогут быть отрицательными.
(Указание.Отрицательная формула ложна в Ег,.)4.Из упражнения3вывести, что в теореме5.4.9условие недоказуемости Ф-+ ~Ф опустить нельзя.§ 5.5.Пусть ТСчетная однородность и универсальность-теория сигнатуры Е. Обозначим черезFn (Е)множество формул сигнатуры Е со свободными переменными из множества{vi, ... ,vn}. Если Ф Е Fn(E), то через IIФllт или просто через IIФII обозначаем множество {Ф Е Fп(Е)1Т t> (Ф-+ Ф) А (Ф-+ Ф)}.
Обозначимчерез ~п (Т) булеву алгебру с носителем Вп (Т)следующими операциями:а) IIФII U IIФII=IIФ V ФII;б) IIФIIn IIФII = IIФ А ФII;в) ТТФ1f=ll~ФII.= {11 Ф 111ФЕFn (Е)} иГл.1765.Корректность определенияl )-1 О)Теория моделейопераций,атакжепроверку аксиомбулевых алгебр оставляем читателю в качестве упражнения.Пусть в этом параграфе все рассматриваемые алгебраические системы и теории, если не оговорено противное, имеют сигнатуру Е,а мощность Е конечна или счетна.
Под моделью теории Т мы будемпонимать модель Т сигнатуры Е. Пустьсигнатуры Е и а1,... , ап2t -алгебраическая системаЕ А. Типом набора (а1,... , ап)в2tназовемследующий n-тип:Если2t, 23 - системы сигнатуры Е, а1, ... , ап ЕT(2t, а1, ... , ап) = Т(23, Ь1, ... , Ьп) будемто равенствоА,Ь1,... , ЬпЕ В,обозначать такжечерезОпределение.
Счетная алгебраическая система Е называется однородной, если для любых а1,... , ап, Ь1, ... , ЬпЕ А и любого элементаа Е А из(5.6)следует(2t,a1, ... ,an,a)= (2t,Ь1, ... ,Ьп,Ь)(5.7)для некоторого Ь Е А.Ясно, что если2t - однородная система и Х ~ А 2tx также является однородной.конечноемножество, то системаПредложение5.5.1.Для любой счетной системысчетное элементарное однородное расширение2tсуществует23 >- 2t.До к аз ат ель ст в о. Покажем сначала, что для любой счетной системы 2t существует такое счетное элементарное расширение 2tCI)что для любых а1,... , ап, Ь1, ... , Ьп, аЕ А из>- 2t,(5.6) следует(5.8)для некоторого Ь Е A(l).
Для каждого Х= {а1, ... , ап}~ А определяеммножествоОбозначим черезRобъединение всехмножество А. Ясно, чтоRR(X),где Х-конечное подимеет счетную мощность. Расширим сигнатуру Ел до Е1, добавив новые символы одноместных операцийJ,Счетная однородность и универсальность§ 5.5."fдля каждогоЕR.177Рассмотрим следующее множество предложенийсигнатуры Е1:Z = D*(2t) U {\fх(Ф(х, Са 1 , ••• , caJ-."( ЕR,a,, ... ,anИз определения множестваZ1Z<:;;;RФ(f,(х), с,а,,Е... , c,aJ)Ф(х,у,,dom"(,1..
·,Уn)ЕF(E)}.следует, что каждое конечное множествовыполняется в некотором обогащении системыz2t.Пусть2t1 -счетная модельи Qt(I) = 2t, r Е. Так как 2t - модель D*(2t), ТО попредложению 5.1.1 О а) можно считать, что 2t -< 2t (1). Если выполняется(5.6), то из истинности на 2t 1 предложений из Z следует выполнимость1 (а), где "f(a1) = Ь1, ... , "f(an) = Ьn.(5.8) для Ь =Определим последовательность систем {2ti I i Е w} следующим образом: 2to = 2t, 2tн1 = 2ti'), i Е w. По предложению 5.1.8 получаем2tk -< ~:Б = U 2ti, k Е w, в частности, 2t-< ~:Б.
Так как ~:Б = U2ti, то ~:Б -1::iEwсчетная система. Если ai, ... , an, Ь1,то а,,... , an, Ь1, ... , Ьn, аЕAi... , Ьn, адля некоторогоЕ В иiЕw. Так как 2ti -< ~:Б, тоимеем(2ti, а,, ... , an)= (2ti, Ь1, ... , Ьn).Из определения 2ti') = 2tн1 получаемдля некоторого Ь Е Ан1. Так как 2tн1(i:Б,a,,Таким образом, ~:БПредложение... ,an,a)>- 2t 5.5.2.-<~:Б, то= (~:Б,Ь,, ... ,Ьn,Ь).счетная однородная система.Пусть2t, ~:Б -Dсчетные однородные системысигнатуры Е. Тогда следующие условия эквивалентны:1)2)2i~i:в.в2tnЕи ~:Б реализуются одни и те же п-типы сигнатуры Е,w.До к аз ат ель ст в о.нумеруем А и В: А=1)===?2){ai I i Е w},построим конечные отображениясвойствами:an)если п-1-О, тоfn-1<:;;;fn;очевидно. Пусть выполняется2). За{bi I i Е w}.
Индукцией поп Е wfn: An-. В, An <:;;; А, со следующимиВ=Гл.1785.Теория моделей= 2k + l, то ak Е Ап;= 2(k + l), то bk Е fп(Ап);Ап = {e1, ... ,em}, тобп) если пВп) еслиnГп) еслиДля=fZJ условия ао) - во) тривиально выполнены. Условие го)2), так как Th(21) является О-типом. Пусть п = 2k + l иAn-1 = {е1, ... , em}- По индукционному предположению имеемfoследует из(5.9)Из условияв23,2)получаем, что тип Т(21, е1,... , em, ak)реализуетсяпоэтому(5.10)для некоторых d1, ... , dm+I ЕВ. Изпоэтому в силу однородностиВ силу(5.1 О)23(5.9)и(5. 10)получаемсуществует такой Ь Е В, чтотогда имеем(21, е1, ... , em, ak)= (23, fп-1е1, ...
, fп-lem, Ь),= fп-1 U { (ak, Ь)} будет удовлетворять= 2(k + 1) рассматривается аналогично.следовательно, отображение fпусловиям ап)-rп). Случай пИз условий ап)-rп), п Е w, получаем, чтомом21наf= U fпбудет изоморфиз-nEw23.Определение. Счетная алгебраическая системао21сигнатуры Е называется универсальной, если для любого п Е w в ней реализуютсявсе совместные ссистема21Th(21)п-типы сигнатуры Е. Счетная алгебраическаясигнатуры Е называется насыщенной, если для любогоконечного Х ~ А в 21х реализуются все совместные сTh(21x)!-типысигнатуры Ех.Ясно, что совместность n-типавыполнимостиZв21.ZсTh(21)равносильна локальнойОчевидно, что счетное элементарное расширениеуниверсальной системы является универсальной системой.
Ясно также,что если система21насыщена, то система 21х также насыщена длялюбого конечного Х ~ А.§ 5.5.Счетная одн.ородн.ость и ун.иверсальн.остьПредложение5.5.3.Длясчетной179алгебраической системы21следующие условия эквивалентны;1) 21насыщена,2) 21 универсальна и однородна.Доказательство.циейпо п Ес Th(2t) п-типв21(п -Пусть система21насыщена. Индуксигнатуры Е. Если пZo= 1,то выполнимостьследует из определения насыщенности.
Пусть п> 1.ZoРассмотрим1)-типТак какz,жению типчто1)===}2).w покажем, что в 21 выполняется любой совместныйv,локально выполним вZ 1 реализуетсяв2121,то по индукционному предполоэлементами а,,не входит связано в элементыZo.достаточно рассмотреть только такие п-типыZ2Ясно, что 1-типБудем считать,Zo.4.2.6 б)Рассмотрим 1-тип= {(Ф)х,,1 ... ,Хn-1,ХпI ф Е Zo}.,CanСа, ...l ,Vtлокально выполним вZ2...
, ап-1 ·В силу предложения2t{a,, ... ,an-i}· В силу насыщен2t{a,, ... ,an-i} тип Z2.ности 2( существует элемент а Е А, реализующий вТогда п-типZoреализуется вПокажем однородность21.21элементами а,,Пусть а,,... , ап-1, а.... , ап, Ь1, ... , Ьп, а ЕА и(5.11)Рассмотрим 1-типZo = {Ф(v1) l 2t{a 1, ••• ,an}Из(5.11)F Ф(а),ФЕ Fi(E{a 1 , ••• ,an})}.следует, что 1-типZ1 -- {(Ф1)х,,...
,х,n \ (Ф1)х,,... ,х,n Е Z О, Ф 1(х 1, ... , Х п, v1) Е F(E)}сь,, ... ,сьnса,, ... ,Саплокально выполним в 2t{ь,, ... ,ьп}· Так как21насыщена, тоz, реализуетсяв 2t{ь,, ... ,ьп} элементом Ь Е А. Ясно, что тогда имеет место(21,щ,... ,ап,а)= (2t,Ь1, ... ,Ьп,Ь).2)===} 1). Пусть 2( универсальна и однородна, а,, ... , ап Е А иZo - локально выполнимый в 2t{а,, ... ,ап} 1-тип сигнатуры Е{а,, ... ,ап}·Без ограничения общности можно считать, что все связанные переменные в элементахz, = T(2t, а,, ...
, ап)Z2 = Zi U { Ф1Zoи (п(отличны отv,, ... , Vn+I.Рассмотрим n-тип+ 1)-типФ )~:·i:·:.~~~:~;;/ ЕZo, Ф( v,, ... , Vп+I)Е F(E)} ·Гл.1805.Теория моделейИз локальной выполнимостиZo в 21{а 1 , ••• ,ап} следует локальная выполZ2 в 21. В силу универсальности 21 имеет место выполнимость Z2 в 21 некоторыми Ь1, ... , Ьn+I Е А. Так как Z1 ~ Z2, тонимостьИз однородностиполучаем21для некоторого а Е А.
Очевидно, что а реализуетПредложение5.5.4.Если21и113 21тарно эквивалентные системы, тоДо к аз ат ел ь ст в о.предложенийные с5.5.2иTh(21) = Th(113)так как в21в21{ а 1 , ••• ,an}.Осчетные насыщенные элемен~Предложение5.5.3,Zo113.непосредственноиследуетизреализуются все совмест113п-типы.ОТаким образом, между полными теориями Т, имеющими счетныенасыщенные модели, и счетными насыщенными моделями Т существует взаимно однозначное с точностью до изоморфизма соответствие.В силу предложения5.5. lлюбая теория Т имеет счетную однороднуюмодель. Однако не все теории Т имеют счетную насыщенную модель(см. упражнение2).Следующее предложение характеризует полныетеории Т, имеющие насыщенные модели.Предложение5.5.5.
Дляполной теории Т, имеющей бесконечныемодели, следующие условия эквивалентны:l)Т имеет счетную универсальную модель;2) Т имеет счетную насыщенную модель;3) для любого п Е w булева алгебра 113n(T) имеет счетное числоультрафильтров.До к аз ат ель ст в о.1)===?2). Пусть 21 - счетная универсальная5.5. l существует счетная однородная мопредложения 5.5.3 получаем, что 113 - насыщеннаямодель Т. По предложениюдель113 >- 21.Измодель Т.2)===?3).Пустьсчетная насыщенная модель Т, п Е21 -ультрафильтр алгебры113n(T).T(U)Ясно, что Т(И)-=21.Если И1, И2-I IIФIIЕ И,Ф Е=и И-Fn(E)}.совместный с Т п-тип.
Так както существует набор а(И)в{Фw,Рассмотрим п-тип(а1,21универсальна,... , an), который реализует тип Т(И)два различных ультрафильтра113n (Т),то для§ 5.5.Счетная однородность и универсальность181некоторой Ф Е Fn(E) имеем IIФII Е И, и ll~ФII Е И2. Следовательно,а(И1) =!= а(И2).
Таким образом, существует разнозначное отображениемножества всех ультрафильтров алгебры !Бп(Т) в счетное множестволп. Это дает условие3).3)==? 1). Пусть {ИГ- 1 i Е w} -множество всех ультрафильтров!Бп(Т) и сигнатура Е 1 получается добавлением к Е новых попарно различных констант { c.i·iI n, iЕ w, 1 ::;; j ::;; п }. Тогда счетное множествопредложений сигнатуры Е:совместно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
