1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 53
Текст из файла (страница 53)
7).определения изОбозначим через а* расширение сигнатуры ао, полученное добавлением символов для всех Е-функций на П и константных символовдля всех элементовw,а через П*Из рассуждений, проведенных в- соответствующее обогащение П.§ 5.8, 5.9 (см. предложение 5.9.4),вытекаетСледствие(а) П*7.2.7.Справедливы следующие утверждения:- ограниченная алгебраическая система сигнатуры а*,(б) предикат Q <:: : wk (функция f: wk----+ w) является Е-предикатом(Е-функцией) на П* тогда и только тогда, когдаQ (f)естьЕ-предикат (Е-функция) на П.Теорема7.2.8(Ганди).
Пусть Ф(х, р+)-Е-формула сигнатурыа* U (Р 1 ), в которую предикатный символ Р входит позитивно.Тогда наименьшая неподвижная точка Г * <:: : w оператора Г~[х] является Е-подмножеством на П*.До к аз ат ель ст в о. Рассмотрим последовательность подмножествмножестваw:Го==; 121, Г n+I ==; Г~[х](Г n), n Е w.Имеем Го<::::: Г1 <:: : ... <:: : Г n <:: : ••• <:: : Г *· Согласно предложению 5.9.3 всеГ n являются Е-подмножествами множестванию5.9.4w.Поэтому по предложеГл.2627.ВычислимостьОпределим последовательность конечных подмножеств множества(.<.)следующим образом:Лос:::;0,Лп+I с=; {k j k ~ п + 1, (П*, Лп)1= :3и ~ п + 1Ф(и)(k)},пЕ(.<.),Легко проверить, чтоЛnS::Г n,nЕ(.<.},Докажем, что предикат Л с=; { (п,m)1mЕ Лп, п, т Е(.<.)}являетсяЕ-предикатом.
Для этого рассмотрим Ло-формулу сигнатуры а*:W(xo,x1,x2) с=; (:3и ~ хоФ(и)(х1,Р+))f(х 2 ,х 3 );:::,s(О))[х 3 ](считая, что переменные х1,х2 не встречаются в :3uФ(и)(х,Р+)), которая получается из Ло-формулы :3и ~ хоФ(и) (xi, Р+) заменой каждойатомарной подформулы видаP(t)формулой Г(х2,t),:::: s(O).Индукцией по построению Ф проверяется справедливость следующего утверждения:ПустьQ с=; wn· [хо, х1, х2] s;;характеристическая функцияXQ(.<.) 3 .ПосколькуQ - Л-предикат, егоесть Л-функция.Определим трехместную функцию Н примитивной рекурсией:Н(п,k, О)= с(О, XQ(n, О, п)),H(n,k,l+ 1) =ch(H(n,k,l),XQ(k,l+ 1,n),k+ 1).ПоложимУстановим равенство Fн(n,k,l)функцииchиндукцией поl=Лn,k,l· Из определения Н и свойствполучаем, чтоГ(Н(п, k, l), i) = {п),XQ(k, l,О, i > l.Из этих соотношений и свойства формулыравенство Fн(n,k,l)= Лn,k,l·i~Wl,вытекает требуемое§ 7.2.
°L.-предикаты и °L.-функции на ППусть функция Н': w2---+263w определена так: H'(n, k) с'с=; Н(п, k, k).Очевидно, что Н' является ~>функцией. Определим функцию Н*: w ---+---+w примитивной рекурсией:Н*(О)Н*(п= О,+ 1) = Н'(Н*(п), п + 1).Установим, что Fн•(n) = Лn для всех= Fн•(О)· Пусть Лп = Fн•(n)· ТогдаЛn+I с'с=; {l j l:,;; n + 1, (П*, Лп)п Еw.Имеем до=(ZJ= Fo =F 3u:,;; n + 1Ф(и)(l)} == Лн•(n),n+l,n+l = Fнcн•(n),n+l,n+I) == Fн'(H*(n),n+l) = Fн•(n+I)·ТаккакН*Е-функция,-изравенствад=(Г(Н*(х),у) ~~ s(0)) 11 * [х, у] следует, что д является Е-предикатом (д-предикатом).Заметим, что Лп= {т1(п, m)Ед}, п Еw, и Д* ;=Е-множеством, так какЛ*=U ЛпявляетсяnEw(Зх(Г(Н*(х),у) ~ s(0))) 11 .[y].Воспользуемся теперь принципом Е-параметризации (см.§ 5.9)для доказательства вложения Г~[х](д*) ~ Л*.
Поскольку Л* - Е-множество,по предложению5.9.4,Г~[хJ(Л*) = Г~~Ф<")[хJ(Л*).Пусть k Е Г~~Ф<")[х](Л*). Тогда (П*, Д*) F 3uФ(и)(k) и существуетинтерпретация 1 : {х,и}---+ w такая, что ,(х) = k и (П*,Л*) F ф(и)[,].По принципу Е-параметризации существует ko Е w такое, что(П*,Л1со)ПустьF ф(и)[,].k1 ~ ko,k,,(u). Тогда из дkо ~ Лk 1 следует(П*,Лk 1 )(Л*,Лk 1 )F ф(и)[,],F 3и:,;; k1Ф(u)(k).Поэтому k Е дk 1 +1 ~ Л*, и свойство Г~[хJ(Л*)(= Г~~Ф<")[хJ(Л*)) ~ Л*установлено.Как отмечено в § 5.9, если Г~[х](д*) ~ Д*, то для наименьшейнеподвижной точки Г * имеем Г * ~ д *. Но тогда из соотношенийЛ*=UЛп ~UnEwnEwЕ-подмножеством w.Гп= Г. следует, что д* = Г* и Г.
являетсяОГл.2647.ВычислимостьТеорема Ганди сформулирована и доказана выше для случая одноместных предикатов. Однако она справедлива и в общем виде.Теорема7.2.9(общая форма теоремы Ганди). Пусть Ф(Р+)-Е-формула сигнатуры а* U (Pk), в которую предикатный символР входит лишь положительно, и пусть х =хо,... , Xk-1-попарно различных переменных. такой, что FV(Ф) <;;;; {х}.списокТогданаименьшая неподвижная точка Г * <;;;; wk оператора Г~[х] являетсяЕ-предикатом на П*.До к аз ат ель ст в о может быть получено сведением к случаю=lk=с помощью следующих без труда проверяемых фактов.Пусть k> 1.Определим Е-функции ck: wk --+ w:=.
с(хо,х1),с2(хо,х1)Ck+I (хо,... , Xk-1, Xk)~ c(ck(Xo, ... , Xk-1 ), Xk),w --+ w, i < k:и Е-функции Pk,i:Pk,o(x)=. Цх, k),Pk,i(x) ~ r(Цх, k - i Тогда для любых х, хо,... , Xk-1Е w(k1)), i >О.> 1)ck(Pk,o(x), ... ,Pk,k-1 (х))= х,(14) Пусть k > 1, Q <;;;; wk,c(Q) ~ТогдаQ является{ck(io, ... ,ik-1) 1 (io,Е-предикатом тогда и только тогда, когда с( Q)является Е-подмножеством множестваПусть х =хо,... ,ik-1) Е Q}.... , Xk-1-w.список различных переменных такой, чтоFV(Ф) <;;;; {х} для Ф, и Фс(х) =.
(Ф)Pk:o(x),.".".",'Pk:~~(x)· Ясно, что еслиФ Е-формула сигнатуры а*, то Фе также является Е-формулойсигнатуры а*.(15)Пусть Ф(Р+) и х=хо,... , Xk-1такие же, как в теореме Ганди. Тогда для наименьших неподвижных точек Г~ и Г;операторов Г~[х] и Г~~[х] справедливо соотношение Г; = с(Г~),где Ф~(Q+) - Е-формула сигнатуры а* U (Q 1), определенная так:Ф*(Q+)~(Ф с )Рс~Q(ck(YD,•••,Yk-I))[yo, ...
,yk-l]·§ 7.3."'Е-определимость истинности "'Е-формул на П265Упражненияl.sg: wДоказать, что функции--+sg: wиw--+w,определенныесоотношениямиsg(O) =sg(n) = l,О,sg(O) = 1, sg(n) =О,п>О,п>О,являются Е-функциями.2.Пустьf: w--+иwg: w--+двеw -функции,почтивсюдуравные нулю, и пусть п 0 , n1 Е w таковы, что fлхГ(nо, х),g лхГ(п1, х). Если f ~ g (т.
е. f(m) ~ g(m) для всех т Е w), то==по~§ 7 .3.n1.:Е-определимость истинности :Е-формул наПредположим, что множество{ Хо, Х\, .•. }Vnвсех переменных есть= {Х; 1 iЕ W }.Тогда с функцией Г можно связать нумерацию всех (полных) интерпретаций тV--+которые почти всюду (за исключением конечногоw,числа переменных) равны нулю. Именно, пусть п Е w и 'Уп:(сигнатуры ао), у= уо,список различных переменныхw.Если Ф ---+ w -i), i... , Yk-1 ( Е V) -ЕVинтерпретация такая, что 'Уп(х;) ==т Г(п,Е-формулатакой, что FV(Ф) ~ {у}, то k-местный предикатФn[у] ={а= (ао, ...
, ak-1) 1 а Е1= Ф[та]}wk, Пявляется Е-предикатом по определению. Однако с Ф можно связатьтакже следующий одноместный (подмножествоw)предикат ТrФ, независящий от выбора списка у:ТrФ ==тПредложение7.3.1.{n I П1= Ф['Уп]}.Для любой Ло-формулы (Е-формулы) Ф сигнатуры ао множество ТrФ является Ло-подмножеством (Е-подмножеством) w на П* (и Л-подмножеством (Е-подмножеством) на П).Сначала установим следующую лемму.Лемма7 .3.2.Для любого термаtсигнатуры ао функция Vt: w --+--+w такая, что Vt(n) ==т tn['Yn], п Е w, является Е-функцией.Vt==т ЛпГ(п,ТОVtДоказательство. Еслис=;Vt 0i);+ Vtесли t1(Vt= s(to),с=;Vt 0•tесть О, то Vt ==т О; еслито Vt ==т s(vt0 ); если tVt 1 ).t есть Xi, то= to + t1 (t = to · t1),0266Гл.7.ВычислимостьДоказательство предложенияИндукцией по постро7.3.l.ению Ф будем строить Ло-формулу (~-формулу) ФФ(хо) сигнатуры а*такую, что ТrФЕслиФ= w~· [хо).естьto ~ t1(to ~ t1), тоФФестьVt 0 (xo) ~ Vt 1 (хо)(vt 0 (xo) ~ Vt 1 (хо)).Если для Фа и Ф1 формулы ФФ 0 и ФФ 1 уже определены, то полагаемWФ 0 vФ 1 ==; ФФо V ФФ 1 ,WФ 0 лФ 1 ==; WФ 0 Л WФ 1 ,Фзх;Фо о=т 3хп(ФФо):~(хо,Хn,i)'Фзх;,;;;tФо ==; 3хп ~ Vt(Xo)(\J!Фo):~(xo.xn,i)'Фvх;,;;;tФо ==; '<lхп ~ Vt(Xo)(ФФo):~(xo.xn,i)'где п Е(.<.)-наименьшее число такое, что п>О и Хп не встречаетсяв ФФо· Проверка того, что предложенные формулы удовлетворяют соответствующим заключениям, довольно проста.
Для примера рассмотримслучай, когда Ф есть:Jxiдля подходящего п Е(.<.).П*~ tФо. ТогдаПусть k ЕF 3хпСледовательно, существуетП*Напомним,чтоk' ==; ch(k, т, i)Fmимеетw~· [хо).Тогда~ Vt(k)(ФФo):~(k.xn,i)"m Е(.<.)такое, что~ Vt(k) Л (ФФ0 ):~(k,m,i)"месторавенствоvt(k) = trl['Yk], а числотакое, что')'Yk' (J={ ')'k(j), j =1- i,m(~ trl['Yk]), j = i.По индукционному предположению соотношениеП*означает, чтоk' Е ТrФ 0 ,F (ФФ0 ):~(k,m,i) = WФ 0 (k')т. е.
П F Фо['Уk'].Таким образом, для интерпре,ации ')'k существует интерпретация"fk' такая, что "fk' (j)= "fk (j)для j =f- i и "fk' ( i)= т ~ tп ['Yk],ПF Фа ['Yk'].~-определимость истинности ~-формул на§ 7.3.1=Поэтому Пп·ФФ [хо] ~ ТrФ.:3xi ~ tФо[т'k] и k Е Тrзх,,,;tФо=267!1ТrФ. Следовательно,ПроверимП1= :3xiобратноевключение.Пустьk Е Тrзх,,,;tФо, т. е.~ tФ0[1'k]. По определению истинности существует интерпреi- i, т :=; 1''(i) ~ trl[1'k],,, отличается от т'k лишь для одногоk' Е (.<.) такое, что ,,, = т'k'. Более того,тация 1'':V-..
(,) такая, что 1''(j) = т'k(j) для j(= Vt(k))и П1= Фо(1''].Так какзначения аргумента, существуетk'= ch(k, т, i).по индукционному предположению имеемно тогдагде k Еw~· [хо].П*1= mП*F :3хп~ Vt(k) А (ФФ0 ):~(k,m,i)'~ vt(k)(\J!Фo):~(k,xп,i)'Таким образом,гдеЕсли Ф есть Ло-формула (~-формула) сигнатуры ао, то легко проверить, что ФФ есть Ло-формула (~-формула) сигнатурыао U (vfIt- терм сигнатуры ао) U (Г 2 , ch 3 ) ~ а*.ОНиже будет установлено значительно более сильное утверждение,означающее <<равномерность,> построения ФФ по Ф.
Предварительноследует определить гёделеву нумерацию всех термов и RQ-формулсигнатуры ао.Если Т(ао)-множество всех термов сигналы ао иRQF(ao) G-множество всех RQ-формул сигнатуры ао, то гёделева нумерацияэто отображениеG:Т(ао) URQF(ao)-..(.<.),удовлетворяющее следующим соотношениям:G(O) =G(xi)G(s(t)) =G(to + t1) =G(to · t1) =G(to~ t1)с(О,1),= c(l,i),iс(2,Е(.<.),G(t)), t Е Т(ао),с(З, c(G(to), G(t1))), to,t1Е Т(ао),с(4, c(G(to), G(t1))), to, t1 Е Т(ао),= с(5, c(G(to), G(t1))), to, t1Е Т(ао),268Гл.G(tot1) =~7.Вычислимостьс(б, с( G(to),G(t1)) ), to, t1Е Т(ао),= с(7, с(G(Фо), G(Ф1))), Фо, Ф1 Е RQF(ao),G(Фо V Ф1) = с(8, с(G(Фо), G(Ф1))), Фо, Ф1 Е RQF(ao),G(Фо-.
Ф1) = с(9, с(G(Фо), G(Ф1))), Фо, Ф1 Е RQF(ao),GГФ) = c(lO, G(Ф)), Ф Е RQF(ao),G(:Jxi ~ tФ) = c(l 1, сз(i, G(t), G(Ф))), i Е v.J, t Е Т(ао), Ф Е RQF(ao),G(Vxi ~ tФ) = с(12, сз(i, G(t), G(Ф))), i Е v.J, t Е Т(ао), Ф Е RQF(ao),G(:3xiФ) = c(13,c(i,G(Ф))),i Е v.J,Ф Е RQF(ao),G(VxiФ) = с(14, c(i, G(Ф))), i Е v.J, Ф Е RQF(ao).G(Фо/\Ф1)Основным результатом настоящего параграфа являетсяТеорема7 .3.3(Е-определимость истинности Е-формул). Следующий двуместный предикат является Е-предикатом на П:ТrЕ==. {(п, k)1 п,kЕv.J, п -гёделев номер Е-формулы Фсигнатуры сто (т.
е. G(Ф)= п)и П1= Ф[,k]}.До к аз ат ел ь ст в о. Предварительно установим ряд вспомогательных утверждений. В доказательстве этих утверждений, а также в доказательстве основной теоремыщей форме (см. теорему(1)Т(п)Следующая функция Т:={7.3.3,используется теорема Ганди в об7.2.9).vJ-.vJ:1, существует терм t Е Т(ао) такой, что G(t)= п,О в противном случаеявляется Е-функцией.Предполагая,чтоРдвуместныйпредикатный символ,соот-ветствующий графику Гт функции Т, можно выписать следующуюЕ-формулу Фт(хо, х1, р+) сигнатуры а* U (Р 2 ), в которую Р входитпозитивно и для которой Гт является наименьшей неподвижной точкой!1*оператора Г Фт[хо,х~]:Фт(хо, х1)==.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
