1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 43
Текст из файла (страница 43)
Действительно, если Ф= Уо, ... , У1 Фее=;: :3z((Ф)¾tСправедлив следующий аналог предложенияПредложениетуры а,а-У:.-формула и у=переменные такие, что Г 9 = ФQl[y], то для "'5:.-формулы/\ ~Yl ~ z) легко проверить равенство ФQl[y] = А 1 +' \Г 9 .5.8.6.Пусть Q( -5.8.4.алгебраическая система сигна-U \Jo/ ,!о , ... , Jlmpkopks)no _ /nrQ о, ...т , 0 , •.. ,\'-", go, ... , 9m,, '"" 8а' -обогащение Q( такое, что gi, i ~ т, - "'5:.-функция на' --а. . .
, Qs) Qj,j ~ s, -Qt,д-предикат на Qt. Тогда любой "'5:.-предикат на Qt'является "'5:.-предикатом наQt.Нам понадобится следующий вариант леммы5.8.Леммаможно5.8. 7.Длялюбой"'5:.-формулыФэффективнонайти "'5:.-формулу Ф той же сигнатуры такую, что Ф = s Ф иFV(Ф) = FV(Ф), любая атомарная подформула формулы Ф является атомной, Ф не содержит импликации, все отрицания в Ф встречаются только перед атомными формулами, а любой ограниченныйквантор Ф имеет вид :3х ~ у или Vx ~ у.До к аз ат ел ь ст в о. Не уменьшая общности, можно считать, чтоФ не содержит импликации и отрицания в ней встречаются лишь передатомарными подформулами.
Так же, как в лемме5.8.5,можно получитьформулу с теми же свойствами, все ограниченные кванторы которойимеют вид :3х ~ у илиVxФ в Ф' (если ранг р(Ф)~ у. Далее определяется преобразование>О), как в лемме5.8.5,со следующимиуточнениями:- подформулу Р( to, ... , tk- l), если онаp(P(to, ... , tk-1)) > О, заменяем формулой:3хо ...
:3xk-l (/\ Xii<kположительно входит в Ф и~ ti /\ Р(хо, ... ,Xk-1)),§ 5.8. Формульная определимостьа подформулу вида~P(to, ... , tk-1) -207формулой:3хо ... ::Jxk-1 (/\ Xi :=::; ti /\ ~Р(хо, ... , Xk-1 )) ;i<k- подформулу t :=::; f(to, ... ,t1-1) (или J(to, ... ,t1-1)::::; t), если онаположительно входит в Ф и p(f(to, ... , t1-1)) > 1 (или p(t) = p(f(to, .... . . , t1-1)) = 1), заменяем формулой:3х:3хо ... :3х1-1 (х :=::; t /\ /\ Xi :=::; ti /\ х :с: ; !(хо, ...
, х1-1)),i<lа подформулу ~t:=::;условиями на рангиf(to, ... , t1-1)- формулой(или ~f(to, ... , t1-1) ::::; t)с теми же:3х:3хо ... :3х1-1 (х ~ t /\ /\ Xi ~ ti /\ ~ х ~!(хо, ... , Х1-1)).i<lПослеFV(Ф)=этих замен получаем ~-формулу Ф' такую, что Фs Ф',FV(Ф'), р(Ф') < р(Ф), удовлетворяющую тем же условиям,=что и формула Ф.
После п ~ р(Ф) шагов находим требуемую формулуф=ф(п)_ОДо к аз ат ел ь ст в о пред л о же н и я 5.8.6. Достаточно рассмотреть два случая: а' = а u (Р/;0 ) и а' = а u иJ0 ).Случай а'= а U (Р/;0 ). Пусть ср 0 , ср 1 - ~-формулы (сигнатуры а) ипеременные у= Уо, ... , Yko-1 таковы, что Qo=ср~[у] и Ako \ Qo= cpr[y].- ~-формула сигнатуры а' и z = zo, ... , Zk-1 - список различных переменных такой, что FV(Ф) ~ {z} и Q ~ ФQl'[z] ~ Ak ~-предикат на Qt'. Не уменьшая общности, будем предполагать (см.Пусть Флемму5. 7.2),что формула Ф не содержит импликации и отрицаниявстречаются в ней только перед атомарными формулами. Предположимтакже, что все связанные переменные формул сро и ер, не встречаютсяв Ф. Образуем ~-формулу Ф, заменяя в Ф каждое положительное вхож·дение под ф ормулыфвидаYD,···,Yko-1...
, tko-l ) на ( сро )ta, ..,.tko-i , а каждое~р, () на ( '{)1 )YD,···,Yko-1о to, ... , tko-lto, ... ,tko-i . 0 тме-р,о (to,вхождение под ф ормулы видатим, что FV(Ф) ~ FV(Ф).Индукцией по построению Ф без труда устанавливается следующееутверждение: для любой интерпретациисоотношение (Qt,Qo)F Ф[,]~ QtНетривиальными являютсяФ= ~Po(to, ... , tka-1).А-(Флишь случаиА имеет место=(Ql,Qo) Ф).Ф = Po(to, ...
, tk0 -1)= ~Po(to, ... , tko-1).Пусть1:интерпретация. Тогда(Qt, Qo)иОба они рассматриваются одинаково. Поэтомуограничимся рассмотрением Ф---.1 : FV (Ф) ---.F Ф[,JF Ф[,J~ (t~[,J, ... , tt_,[,J) rJ. Qo ~FV(Ф)---.208Гл.5.Теория моделейСледовательно, Q = ф(2l,Qo) [z] = Ф 21 [z] - ~-предикат на Qt.Случай а' = а U (!6°). Пусть а' = а U (!6°) и Qt' = (Qt, go). Предположим, что ~-формула (сигнатуры а) ер и переменные у= Уо,таковы, что Г 90ер 21 [у].... , Ylo=Пусть Ф - ~-формула сигнатуры а' и z = zo, ... , Zk-1 списокразличных переменных такой, что FV(Ф) ~ {z} и Q ее=;: Ф 211 [z] ~-предикат на Qt'.
Предположим, что все связанные переменные формулыерневстречаютсявформулеет заключению леммы5.8.7.заменяяположительноевФкаждоеФипоследняяудовлетворяОбразуем ~-формулу Ф сигнатуры а,вхождениеподформулывида и::::; fo(uo, ... ,U/0 -1) (или !о(ио, ...
,и10 -1)::::; и) формулой (ер)Ки•акаждоевхождениеподформулы вида~и::::;fo(uo, ... , и1 0 -1) (илиформулой :3x((ep)ixl\~u::::;x). Как и выше, индукцией устанавливается следующее утверждение: для любой интерпретации ,: FV(Ф) ----.
А имеет место соотношениеQt' = (Qt,go) р Ф['У] {::::::::> Qt р Ф['У]. Следовательно, Ф 21 '[z] = Ф 21 [z],и Q = Ф 21 ' [z] является ~-предикатом на Qt. Предложение 5.8.6 дока~fo(uo, ... ,u1 0 -1)::::;u) -зано.ОПредложениеПусть Q( -5.8.8.ограниченная алгебраическая си-fl"' P.kopks) , nrt("rстема сигнатуры а,а U (J,lo'"" -_'-", go, ...O , .•• , m , 0 , ... , 8... ,gm,Qo, ...
,Qs) - а'-обогащение Q( такое, что gi, i ~ т, ~-функция на Qt, Q 1 ,j ~ s, - д-предикат на Qt. Тогда Qt' - ограниа '_-ченная алгебраическая система сигнатуры а'.До к аз ат ель ст в о.Требуетсяпроверитьдо-формулысигнатурылишьдляпредложениюдля любой ~-формулы (не только до-формулы)5.8.6а'.Нопринципд 0 -ограниченностисогласноФ сигнатуры а' существует ~-формула Ф сигнатуры а такая, чтоФ = 21' Ф.Следовательно, '</х ~ t:3уФ = 21' '</х ~ t:3y\JJ.~-ограниченности (см.§ 5.7)имеем '</х ~ t:3y\JJПо=21 :3v'r:/xпринципу~ t:3y ~ v\JJ.Но тогда'</х ~ t:3уФ =21' '</х ~ t:3y\JJ =21' :3v'r:/x ~ t:3y ~ v\JJ =21' :3v'r:/x ~ t:3y ~ vФ.Предложение5.8.8доказано.оПозитивные формулы и монотонные операторы§ 5.9.§ 5.9.209Позитивные формулы и монотонные операторы.Определение.
RQ-формула Ф сигнатуры а называется позитивной,если она не содержит ни импликации, ни отрицания, ни ограниченныхкванторов всеобщности.Основноесемантическоесвойствопозитивныхформулуказанов следующем предложении.Предложение5.9.1. Пусть Qt, 113 - алгебраические системы113 - эпиморфизм (гомоморфизм ((на»), Ф формула, ,у: FV(Ф) - А - интерпретация в А.
Тогдасигнатуры а, а: Q( -позитивная(5.14)До к аз ат ель ст в о.Применим индукцию по построению формулы Ф. Для атомарной формулы Ф соотношение(5.14)справедливо поопределению гомоморфизма.Если(5.14) справедливо для Фо и Ф 1 , то легко проверить, что (5.14)также справедливо для ФоПустьV Ф1и Фо Л Ф,.(5.14) справедливо для Ф и Qtинтерпретация,': FV (Ф) -F VхФ[,'].В такова, чтоПредположим, что,' r FV (Ф) \ {х}=а: 1 .Поскольку а есть отображение А на В, существует элемент а Е Атакой, что а(а)=,'(х).такая, что 1 * r FV(Ф)как Qt\lхФ[,], верноFположению113F Ф[а: 1 *]Пусть\ {х}Qt F(1131 *:FV(Ф)-А-интерпретация=1и ,*(х) = а.
Тогда а,* = ,'. ТакФ[,*], и согласно индукционному предF Ф[,']).Итак, для любой интерпретации,': FV(Ф) - В такой, что,' r FV(Ф) \ {х} = а,, имеем 113Поэтому113F VхФ[а: 1 ]и \lхФ удовлетворяетЕсли Ф обладает свойствоми :3х ~ tФ обладают свойствомFФ[,'].(5.14).(5.14), аналогично проверяется, что :3хФ(5.14).ОФормула Ф может не быть позитивной, но возможно, что некоторыепредикатные символы входят в нее позитивно. В этом случае справедлив некоторый вариант предложенияПусть Ф-5.9.1.формула сигнатуры а такая, что Ф не содержит импликации и отрицания в ней встречаются только перед атомарнымиподформулами.
Будем говорить, что предикатный символ Р сигнатурыа входит позитивно в Ф (обозначаем Ф(Р+)), если Ф не имеетподформул вида ~P(to, ... , tk-l) ни для каких а-термов to, ... , tk-1.Пусть Р входит позитивно в Ф, ао =;а\ (Pk), Qto - алгебраическаясистема сигнатуры ао, Q ~ А~. Тогда (Qto, Q) есть алгебраическаясистема сигнатуры а ( (Qto, Q) - обогащение Qto до а и p'l!Q). При=сделанных предположениях справедливоГл.2105.Теория моделейПредложение 5.9.2.
Если предикат R ~ Ag таков, что Q ~ R,1 : FV(Ф) - t Ао имеет место имплито для любой интерпретациикация(12to, Q)р Ф[,]=* (12to, R)До к аз ат ель ст в о.р Ф[,].Как при доказательстве предложения5. 9.1,применим индукцию по Ф. Отличия состоят лишь в базисе индукции.Если Ф-атомарная формула или отрицание атомарной формулы и Фне содержит Р, тоЕсли Ф содержит Р, Ф должна иметь вид(12to, Q)==}Предложение0 [,], ... ,Поэтомуt~~I [,]) Е Q =*(t~0 [ 1 ], ... ,t~~ 1[,]) Е R==? (12to,R)5.9.2ПредложениепозитивныеF Ф[,] =* (t~P(to, ...
, tk-1).F Ф[,].доказано.5.9.2вхожденияопозволяет связыватьформулами,предикатного символа,некоторыеимеющимиинтересныемонотонные операторы.Пусть формула Ф позитивно содержит k-местный предикатный символ Р, и пусть х=хо,... , Xk- l -список попарно различных переменных такой, что FV(Ф) ~ {х} (такой список может быть пустым).С формулой Ф(Р+), списком х и алгебраической системой12toсигнатуры ао =а\ (Р) свяжем оператор г:(х] на множестве P(Ag) всехk-местных предикатов на Ао следующим образом: для Q ~ Ag полагаемг:[xJ(Q) ~ ф(Q\o,Q)[x] = {(ao, ...
,ak-1)1(12to,Q) F Ф[,о](= Ф(ао, ... ,ak-1))}.Из предложения5.9.2вытекает монотонность этого оператора:С оператором г:[х] свяжем последовательностьГо.Г,,.. ,,Га,···(а-ординал)k-местных предикатов на Ао следующим образом:Го~ 0, Г a+I ~ г:[хJ(Г а), Га~U Гrз,(З<а§ 5.9.где аПозитивные формулы и монотонные операторыпредельный ординал. Заметим, что а ~-/3влечет Г °'Действительно, в противном случае предположим, что аоший ординал, для которого существует ординалiи Г <>оiГ <>о-Г rз, и /Зо/3211-<;;;Г rзнаименьтакой, что ао ~/3наименьший ординал, для которого ао ~ /Зо иГ rза · Ясно, что аоным, так как иначе Г <>< /Зо,=1- /Зо, т.
е. аои ао не может быть предельГ rзо для всех а< ао (по выбору наименьшего<;;;ао). Следовательно,г <>о =uг<> <;;; г rзо'<><<>очто невозможно. Таким образом, ао= а+ 1 дляподходящего а. Покажем, что ординал /Зо также не может быть предельным. Действительно,если /Зо предельный, тоГао<;;;u Гrз = Гrзо,(З<(Зочто невозможно. Таким образом, /Зоа ~/3,= /3 + 1для подходящего/3ино тогдаПришли к противоречию.Если Г <> = Г <>+ 1 для некоторого а, то Г rз = Г °' для всехЗаметим, что найдется ординал а такой, что Г rзординал такой, что Г 7D7=;=1- Г 7 +1 для всех ,Г 7+1\Г 7 , 1 < /3,< /3D=/3~ а.Га· Пусть/3 -иП Dт=;-у<(ЗТак какfЕDD 7 =1- 0такой, что, < /3,дляf:/3 -+по аксиоме выбора существует элементАо и при ,оГ 70 с Г 70 +1вытекает разнозначность функцииесли а-<<;;; Г 71f.,1 < /3из соотношенияс Г 71 +1Следовательно,1/31~IAol-Тогда,ординал такой, что его мощность больше мощности Ао, тоГа= Га+!·Обозначим через Г * множество Га для наименьшего ординала атакого, что Г a+I =Га·Множество Г * являетсяратора г:[х], т.
е. г:[хJ (Г *)таков, что г:[х](д) = д.наименьшей неподвижной точкой опе= Г * и Г * <;;; Л, если предикат д <;;; А~Первое свойство имеет место по определению Г *· Для доказательства второго свойства индукцией по а устанавливается, что дляГл.2125.Теория моделейлюбого предиката Л ~ А~ такого, что г:r,п(Л) ~ Л, верно соот·ношение Г °' ~ Л. Действительно, Го = {ZI ~ Л. Если Г °' ~ Л, тоГ a+I = г:[х](Г а) ~ г:[х](Л) ~ Л. Если ординал а предельный иГ ,в ~ Л для всех (3 < а, то Г °' = U Г ,в ~ Л.,6<аТаким образом, Г * является предикатом на Ао, однозначно опреде-ленным формулой Ф(Р+) (и набором х). Это определение безусловносложнее формульного определения предикатов, приведенного вОднако в§ 7.2§ 5.8.будет рассмотрен важный случай, когда для Е-формулыФ(Р+) предикат Г * окажется Е-предикатом.В заключение параграфа укажем некоторые свойства ограниченныхсистем по отношению к Е-формулам Ф(Р+).ПредложениеПусть5.9.3.произвольная алгебраическая210 -система сигнатуры ао, предикатный символ Р входит позитивнов Е-формулу Ф сигнатуры а= ао U (Pk)и х =хо,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
