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

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

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

[l(xo):::::: О/\ (хо::::::11\ х1 :::::: 1 V ~хо:::::: 11\ х1 :::::: O)]vV[l(xo):::::: 11\ XJ:::::: l]Vv[l(xo) :::::: 2 /\ P(r(xo), х1 )]v§ 7.3."Е,-определимость истинности "Е,-формул на~~л(P(l(r(xo)),l)лЛP(r(r(xo)), 1) Л х, ~ 1 V (P(l(r(xo)),O)Vv[(l(xo)3 V l(xo)4)VP(r(r(x 0 )),0))v[Б::;;l(x 0 )kO)]v-+w:Е w и существует термтакой, чтот. е. Т(п)269л х, ~ О].(2) Следующая функция valт: ,,./если п,лх 1 ~r2G(t)tЕ Т(ао)= п,= 1,в противном случае,является Е-функцией.Выпишем соответствующую Е-формулу Ф(хо, х,, х2, р+) сигнатурыа*U (Р 3 ), в которую Р входит позитивно и для которой график Г valт ~~ w3 является наименьшей неподвижной точкой оператора Г~[xo,xi,xiФ(хо,х1,х2) ~ [Т(хо) ~ Олх2 ~v[l(x 0 )v[l(xo)v[l(xo)~~ О л х2 ~O]vO]v~ 1 Лх2 ~ Г(x1,r(xo))]V2 л Т(хо)~ 1 л :3хз(Р(r(хо)х,, хз)ЛЛх2 ~ s(xз))]vV[l(xo)~3 л Т(хо)~ lлЛ:3хз:3х4(Р(l(r(хо)), х,, хз)ЛЛP(r(r(xo)), х,, х4) Л х2 ~ хзV[l(xo)~4 л Т(хо)+ x4)]v~ lлЛ:3хз:3х4(Р(l(r(хо), х,, хз)ЛЛP(r(r(xo)), х,, х4) Л х2 ~ хз · х4)].(3)Следующая функцияFo(n)=Fo: w -+ w:1,если существует Ло-формула ФОпротивном случае,сигнатуры ао такая, что G(Ф){является Е-функцией.= п,Гл.270Вычислимость7.Выпишем Е-формулу Ф(хо, х1, р+) сигнатуры и* U (Р 2 ), <<определя­ющую•> ГF0 :Ф(хо, х1) с:::;v[(l(xo)~[(l(xo) :( 4 V 13 :( l(xo)) /\ х1~5 V l(xo)I\T(r(r(xo)))~11\ х1~~VT(r(r(xo)))v[(l(xo)~ 76) /\ (T(l(r(xo)))V l(xo)v[l(xo)v[(l(xo)~0) /\ х1~ 8~Fr:.(n)=11\OV~ 9)/\V l(xo)/\х1 ~P(r(r(xo)), О))/\ х 1~10 /\ P(r(xo), x,)]v~lVO)]v11 V l(xo) ~ 12) /\ ((T(r(l(r(xo)))) ~ O)v~Следующая функция Fr:.:1,~O]vO)]VVVT(r(l(r(xo))))(4)~1 V (T(l(r(xo)))l\(P(l(r(xo)), 1) I\P(r(r(xo)), 1)v(P(l(r(xo)), О)~11\ P(r(r(xo)), х1)].w -.

w:если существует Е-формула Ф сигнатуры иотакая, что G(Ф) = п,{Ов противном случае,является Е-функцией.Следующая Е-формула Ф(хо, х,, Р+) сигнатуры и*U (Р 2 ) ~опреде­ляен ГFЕ:Ф(хо, х,) с:::;[(l(xo) :( 4 V 14 :( l(xo)) /\ х1v[Fo(xo)V[(l(xo)~~ 711\ х1V l(xo)~V[(l(xo)V~ 8)/\P(r(r(xo)), О))/\ х 1~11 V l(xo)l\(T(r(l(r(xo))))VT(r(l(r(xo))))V[l(xo)~~O]Vl]vl\(P(l(r(xo)), 1) /\ P(r(r(xo)), 1) /\ х,V(P(l(r(xo)), О)~~~lV~O)]v12)/\~О/\ х, ~OV11\ P(r(r(xo)),x,))]v13 /\ P(r(r(xo)), х1)].§ 7.3.

Е-определимость истинности Е-формул на Q(5)Следующая функцияl,For(n)271For: w-+ w:если существует RQ-формула Ф сигнатуры о-отакая, что п = G(Ф),={Ов противном случае,является Е-функцией.Следующая Е-формула Ф(хо, х 1 , р+) сигнатуры о-* U (Р2 ) <<опреде­ляет,> ГFor:Ф(хо, х1) ~[(l(xo) ~ 4 V 15 ~ l(xo)) л х1 ~ O]Vv[Fo(xo) ~ l л х1 ~ l]VV[(l(xo)~7 V l(xo)Л(P(l(r(xo)),8 V l(xo)~ 9)лP(r(r(xo)), l)Л х1 ~l)VV(P(l(r(xo)), О) V P(r(r(xo), 0))Л х1 ~O)]V1)v[l(xo)v[(l(xo)~11 V l(xo)Л~~~10 Л P(r(xo), x1)]v12)Л~lVT(r(l(r(xo))))(T(r(l(r(xo))))Л~ О л х1 ~OVP(r(r(xo)), x1))JvV[(l(xo) ~ 13 V l(xo) ~ 14) Л P(r(r(xo)), х1)].(6) Следующая функция Тr 0 : w2 -+ w:l,Тro(n,k) = {0если существует Ло-формула Фтакая, что п=G(Ф) и ПF Ф[,k],в противном случае,является Е-функцией.Следующая Е-формула Ф(хо, х1, х2, р+) сигнатуры а* U (Р 3 ) <<опре­деляет» ГТr 0 :Ф(хо, х1, х2) ~[Fo(xo) ~ О Л х2 ~ О] V Fo(xo) ~ lЛЛ[l(хо) ~5Л(valт(l(r(xo)), х1) ~~ valт(r(r(xo)), х1) Л х2 ~lVv~valт(l(r(xo)), х1) ~ valт(r(r(xo)), х1) Л х2 ~V[l(xo)~6Л(valт(l(r(xo)), х1) ~O)]V272Гл.7.Вычислимость~ vaiт(r(r(xo)), х1) Л х2 ~1Vv·(vaiт(l(r(xo)),x1) ~~ vaiт(r(r(xo)), х1)) Л х2 ~~V[l(xo)ЛP(r(r(xo)), х1,7 Л (P(l(r(xo)),x1, l)Л1) Л х2 ~ 1 V (P(l(r(xo)), х1, O)VVP(r(r(xo),x1,0))V[l(xo)~O)]VЛх2 ~O)]V8 Л (P(l(r(xo)), х1, 1) V P(r(r(xo)), х1, 1)) Л х2 ~ 1VVP(l(r(xo)), х1, О)~v[l(xo)лP(r(r(xo), х1, О))VP(l(r(xo)), х1, 1)~ЛЛх2 ~~л х2 ~O)Jv1)Лх2 ~lVx1)P(r(r(xo)), ch(x1, хз,l(l(r(xo)))), О)12 ЛO)Jv11 Л (:3хз ~ vaiт(r(l(xo)),VVxз ~ valт(r(l(xo)),~Л х2 ~10 л (P(r(xo), х1, О) Л х2 ~ 1Vx1)P(r(r(xo)),ch(x1,xз,l(l(r(xo)))),V[l(xo)lVP(r(r(xo)), х1, О)VP(r(xo),x1, 1)V[l(xo)O)Jv9 л ((P(l(r(xo)), х 1 , O)vVP(r(r(xo)),x1, 1))V[l(xo)л х2 ~Л х2 ~O)Jv(Vхз ~ valт(r(l(xo)),ch(x1,xз,l(l(r(xo)))),1)x1)P(r(r(xo)),Лх2 ~lVV:3хз ~ vaiт(r(l(xo)),x1)P(r(r(xo)),ch(x1, хз, l(l(r(xo)))), О)Л х2 ~ О)]}.Приступим непосредственно к доказательству теоремы 7.3.3.

Выпи­шем ~-формулу ФЕ(хо,х1,Р+) сигнатуры а* U (Р 2 ) такую, что преди­кат ТrЕ будет наименьшей неподвижной точкой оператора г~: [xo,xi]ФЕ(хо,х1) :с=;V[l(xo)V[l(xo)FE(xo)~ 7Л~ 8лV[l(xo)~1 Л ([Fo(xo) ~ 1 л Тrо(хо,х1) ~ l]VP(l(r(xo)), х1)ЛP(r(r(xo)), x1)]v(P(l(r(xo)), х1) V P(r(r(xo)), x1))Jv~ 11 Л :3хз ~ vaiт(r(l(r(xo))), х1)P(r(r(xo)), ch(x1, хз, l(l(r(xo))))Jv:§ 7.3. 'Е-определимость истинности 'Е-формул на Q273V[l(xo) ~ 12 Л Vхз ~ valт(r(l(r(xo))), х1)P(r(r(xo) ), ch(x1, хз, l(l (r(xo)))) )]VV[l(xo) ~ 13 Л 3xзP(r(r(xo)), ch(x,, хз, l(l(r(xo)))))])).Докажем, что для любогоQ~ТrЕ,= {(n,k) 1(П*,Q) F ФЕ(п,k)} ~ ТrЕ.пустьQ ~ ТrЕ и (П*, Q) F ФЕ(п, k).r~:(xo,xi](Q)Действительно,F FE (п)П*~1, т. е. п -Тогдаrёделев номер некоторой ~-формулы Ф.Далее, должен быть истинен один из дизъюнктивных членовFo(n)l(n)l(n)~~~1 Л Тrо(п, k)~1,7 Л (l(r(n)), k) Е Q Л (r(r(n)), k) Е Q,8 Л ( (l(r(n)), k) Е Q V (r(r(n)), k) Е Q),l(n)~11 Л 3хз ~ valт(r(r(l(n))), k)( (r(r(n)), ch(k, хз, l(l(r(n)))))) Е Q),l(n)~12 Л Vхзl(n)~ valт(r(r(l(n))),k)( (r(r(n)), ch(k, хз, l(l(r(n)))))~ 13 Л 3xз((r(r(n)),ch(k,xз,l(l(r(n)))))ЕЕQ),Q).Рассмотрим возможные случаи.СлучайТro(n,k)Fo(n) = 1.Тогда= 1 влечет П F Ф[1k]Ф естьЛо-формула.l(n) = 7.

Тогда Ф имеет вид (Фо Л Ф1) и= r(r(n)). Следовательно, (l(r(n)), k) Е Q ~Фо[1k], а (r(r(n)), k) Е Q ~ Тrr: влечет П F Ф1 [1 k],Случай= l(r(n)),FG(Ф1)чет ПП(Фо Л Ф1)[ 1 k] и (п, k) Е ТrЕ,FСледовательно,и (п, k) Е ТrЕ.G(Фо)=ТrЕ вле­Поэтомуl(n) = 8 рассматривается аналогично предыдущему.Случай l(n) = 11. Тогда Ф имеет вид 3xi ~ tФо, где i = l(l(r(n))),G(t) = r(l(r(n))), G(Фо) = r(r(n)). ПоэтомуСлучайvaiт(r(l(r(n))), k)= tn[1 k]-Ecли m ~ tП[1'k] такое, что (r(r(n)), k') Ето ПФо[1~] и ПФ[1k], (п, k) Е ТrЕ,FQ~ТrЕ для k' ~ ch(k, т,i),FОстальные случаи рассматриваются аналогично.Из доказанного следует, что г~: [xo,xi] (ТrЕ) ~ ТrЕ.

Тем самым Г * ~~ ТrЕ, где С обозначает наименьшую неподвижную точку операторагn·ФЕ[Хо,х1]·Установим теперь, что ТrЕ ~ Г *. Предположим, что это не так, т. е.ТrЕ\Г*#fZJ. Пусть по Е w -наименьшее число, для которого суще-Гл.2747.Вычислимостьствует k Е w такое, что (по, k) Е ТrЕ \ Г *' и пусть ko - наименьшее изтаких k. Так как (по, ko) Е ТrЕ имеем FE(no) = 1. Если Fo(no) = 1, то(по, ko) Е ТrЕ =? П=? Тro(no,ko) = 1,F Ф[1'k0 ],[где G(Ф) =по],=?[так как Ф- Ло-формула],=?п·=? (по, ko) Е Г1 = ГФЕ[хо,х~](.0)что невозможно. Итак,Fo(no) =О. Тогда<::;; Г.,Еl(no){7, 8, 11, 12, 13}.Рассмотрим для примера два случая.Случайl(no) = 7.Тогда Ф =Фа/\ Ф1, где Фчто по= G(Ф) и G(Фо) =(по, ko) Е ТrЕ =? Пl(r(no)) <F Ф[,'k 0 ]по, G(Ф1) ==? П~-формула такая,-r(r(no)) <F Фо[1'kо]И Ппо,F Ф1 [,'k0]=?=? (l(r(no)), ko), (r(r(no)), ko) Е ТrЕ =?=? (l(r(no)), ko), (r(r(no)), ko) Е Г * [по выбору по].Но тогда существует s Е w такое, что(l(r(no)), ko), (r(r(no)), ko) Е Гs<::;; Г *'п·Поэтому (по, ko) Е Г s+I = Г ФЕ[хо,х~] (Г s) <::;; Г *' что невозможно.Случай l(no) = 12.

Тогда Ф = Vxi ~ tФо, где Ф - ~-формула такая,что G(Ф) =по.Заметим, что i = l(l(r(no))), G(t) = r(l(r(no))), G(Фо) == r(r(no)) < по. Тогда(по, ko) Е ТrЕ =? П=? Vm ~ t 11 [1'k0 ](ПF Ф[')'k0 ] =?F Фo[1'ch(ko,m,i)])=?=? Vm ~ t 11 [1'ko]((r(r(no)),ch(ko,m,i)) Е ТrЕ) =?=? Vm ~ t 11 [1'k0 ]((r(r(no)),ch(ko,m,i)) Е Г*)[по выбору по].Пусть s Е w такое, что(r(r(no)), ch(ko, О, i)), (r(r(no)), ch(ko, 1, i)), ... ,(r(r(no)), ch(ko, t 11 [,'k0 ], i)) Е ГsНо тогда ввиду выбораs,<::;;С.указанных свойств и вида формулы Ф,п•(no,ko) Е Гs+I = ГФЕ[Хо,х1](Гs)Приходим к противоречию.

Случайl(no) = 12<::;;г*.невозможен.§ 7.3. Е-определимость истинности Е-формул на Ql(no) = 8, 11, 13.Случаи275Так же как выше, устанавливается, чтоэти случаи невозможны.Полученное противоречие доказывает, что ТrЕ ~ Г * и ТrЕТеорема7.3.3будут указаны в= Г *.Оимеет многочисленные следствия, некоторые из них§ 7.4;здесь же мы ограничимся следующим утвержде­нием.Следствие7.3.4.Существует Е-подмножествоR~ u.1, не являю­щееся Л-подмножеством.До к аз ат ель ст в о.ПустьФЕ (хо, х1)Е-формула-такая,что ТrЕ = ФШхо, х1], и пусть Ф(хо) ~ (ФЕ?(10 ) Е-формулаи R ~ wri· [хо] Е-подмножество u.1.

Предположим, что R СЛ-множество,Ru.1 \=т. е.u.1 \такжеRявляется,ХОЕ-множеством,иФ~[хо] для подходящей Е-формулы Фо (сигнатуры ао). Пустьпо~ G(Фо)-rёделев номер Фо ипринадлежит ли пара (по,n1)n1~ с(О, по). Попробуем выяснить,множеству ТrЕ.Если (по, n1) Е ТrЕ, то П р Фо['Уп 1 ], так как по= G(Фо), 'Уп 1 (хо)== Г(n1, О)= r(n1) = по. Следовательно, по Е Ф~[хо] = u.1 \ R, по i R == wri·[xo], П* F ·w(no), П F ·ФE(no,c(O,no)), П F 'ФE(no,n1),(по,Пn1)iТrЕ; приходим к противоречию.iFiFЕсли (по, n1)ТrЕ, то П·ФЕ(по, n1), П*·w(no), по R,Фо(nо), Пр Фо[1п 1 ], (по, n1) Е ТrЕ; опять приходим к противоре-FЧИЮ.Итак,является Е-множеством, но не Л-множеством.RоВ заключение параграфа отметим, что Ло-формулы и Е-формулыявляются начальными классами иерархии формул, определенной так:Определение.

Ео-формулы-это в точности Ло-формулы.Пусть класс Еп-формул определен. Определим Лп+l -формулы иEn+l -формулы.Лn+1-формулы:-любая Еп-формула является Лп+I -формулой;если Фи Ф-Лп+1-формулы, то ·Ф, (ФV Ф),(Ф/\Ф), (Ф-+ Ф)суть Лп+I -формулы;если хи Ф--переменная,t -терм, не содержащий переменную х,Лп+1-формула, то :3х ~ tФ,Vx~ tФ суть Лп+1-формулы.En+I -формулы:любая Лn+l -формула является Еп+I -формулой;еслиФиФEn+I -формулы;-Еп+1-формулы,то(ФV Ф), (Ф /\ Ф) суть276Гл.еслихt -переменная,-ную х, и ФВычислимость7.терм,несодержащийперемен­Еп+1-формула, то :3х ~ tФ, \/х ~ tФ, :3хФ суть-En+I -формулы.Замечание7.3.5.Из определения видно, что Л1 -формулыв точности Ло-формулы и Е1-формулыЗамечание7 .3.6.--этоэто в точности Е-формулы.Индукцией по построению формулы Ф нетрудноустановить, что для любой RQ-формулы Ф (сигнатуры ао) существуютn>О и Еп -формула \]i такие, что ФОпределение.ПредикатQ ~= 11 \]i.wkназываетсяЛп -предикатом(Еп-предикатом) на П, если существует Лп-формула (Еп-формула) Фтакая, что Q= Ф 11 [хо, ...

, Xk-1].Имеет место следующее обобщение основной теоремыТеоремалюбогоn>7.3.77.3.3.(Еп-определимость истинности Еп-формул). ДляО следующий двуместный предикат является Еп -преди­катом на П:ТrEn ~ { (m,k) 1 m, kЕw, m -гёделев номер Еп-формулы Фсигнатуры ао (т. е.G(m)=Ф) и П ~ Ф[1'k]}.До к аз ат ель ст в о аналогично доказательству теоремы о Е-опре­делимости истинности Е-формул и проводится индукцией потим,что еслиan+I -n.Заме­расширение сигнатуры ао символами для всехЛn+l -предикатов на П, а Пп+l-соответствующее обогащение П, тоПп+I является ограниченной алгебраической системой сигнатуры an+I,так что можно применять теорему Ганди.ОКак и выше, получаем следствие, которое сформулируем в видетеоремы.Теорема7.3.8(об иерархии).

Для любогоЕn+1-подмножествоRnЕ w существует~ w, не являющееся Лп-множеством.Важным следствием теоремы об иерархии являетсяТеорема7.3.9(теорема Тарского о неопределимости истинно­сти в Щ. Следующий двуместный предикат не является ао-фор­мульным на П:Тr ~ { (m,k) 1 m, kЕ w,m -гёделев номер RQ-формулы Фсигнатуры ао (т. е. G(Ф)= т), П~ Ф[1'k]}.До к аз ат ел ь ст в о. Допустим, что утверждение неверно, и пустьФ(хо, х,) -RQ-формула сигнатуры ао такая, что Тr=Ф 11 [хо, х1].Е-предикаты и Е-функции§ 7.4.277Можно считать, что Ф есть Еп-формула для подходящего плиR~ w -Ф(хо) ->О. Ес­Еп+2-подмножество, не являющееся Лп+1-множеством,I:п+2-формула, определяющая R (R=то I:п-формула Ф(kо, с(О, хо)) также определяетwn[xo]), ko ~ G(Ф),R в П.

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

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