1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 55
Текст из файла (страница 55)
Полученноепротиворечие доказывает теорему.ОУпражнения1. Доказать, что функция Fr F: w2 -+ w:Frp(n, i)если п1,={-гёделев номер RQ-формулы Ф,и Xi Е FV(Ф),0в противном случае,является I:-функцией.2.Доказать, что функцияесли п - гёделев номер некоторогоRQ-предложения сигнатуры О"О,1,Sen(n)=Sen: w -+ w:{Ов противном случае,является Е-функцией.3. Доказать, что функция Sub: w3 -+ w такая, что если п - гёделевномер некоторой формулы Ф (терма t), m - гёделев номер некоторого терма to, то Sub( п, т, i) - гёделев номер формулы ( Ф )f0'(терма (t)f0; ) и Sub(n, m, i) = О в противном случае, являетсяI:-функцией.4.
Доказать, что функция FE,.: w -+ w (п > О):1,если существует Еп -формула ФОв противном случае,F,, .. (k) = {сигнатуры О"о такая, что k= G( Ф ),является I:-функцией.§ 7 .4.Универсальные ~-предикаты, универсальныечастичные ~-функцииДля любых (k+ !)-местного Е-предиката Q ~ wk+ 1 (k > О)и п Е wследующий k-местный предикат является I:-предикатом:Qп ~ { (n1, ... , nk)Действительно, если Q=1(n1, ... , nk) Е v.Jk, (п, п,, ... , nk) Е Q}.Фn[хо, ...Qп,xk] и Ф ~ (Ф)~0 • то= Wf!* [x,, ... ,xk]-2787.Гл.Определение.сяЕw}+ !)-местный(kуниверсальным{Qп I nдля~>предикат Q ~ wk+ 1 называетk-местныхz',-предикатов,еслисемействосостоит из всех k-местных z',-предикатов.+ !)-местногоДля (kВычислимостьпредиката Q ~ wk+ 1 через OQ обозначиммножество{ (n1, ...
, nk)1(n1, ... , nk) Е wk и существует n Е w такой, что(n1, ... , nk, n) Е Q}.Предложениечто ТrЕгда (k=Пусть7.4.l.k >О,ФЕ-z',-формулатакая,1 (ОФ~[хо,х1], Фk(хо, х1, ... , xk) ~ (ФЕ)хCk+l)· ToLJ,Xk,Xk-l,•••,Xl+ l )-местныйz',-предикат uk+I ~ Ф~· [хо, х1, ... , xk] являетсяуниверсальным.До к аз ат ель ст в о.ПустьQ ~ wk -мула сигнатуры ао такая, что Q=z',-предикат и Ф -форФf![хо, ... , Xk-1] Обозначим через по~ G(Ф) гёделев номер формулы Ф. Заметим, что для любыхn1, ...
, nk Е w если m ~ Ck+I (О, nk, nk-1, ... , n1), то ,'m(xi)i < k и 1'm(xi) = О для i ~ k. Имеем(по,m)= nн1дляЕ ТrЕ ~ Пр= Фа(nо, т) ~~ П*F Фk(no,n1, ... ,nk)~~ Пр=Ф[1'm] ~~ (n1, ... ,nk) Е Фn[xo, ... ,Xk-1] ~~ (n1, ... ,nk) Ет.е. Q= и~: 1 •Для (kk >Q,+ !)-местной0частичной z',-функции F: D-+ w (D ~ wk+I,О) и любого п следующая k-местная частичная функцияFn: Dn -+-+ w является частичной z',-функцией:Орп ~ Dп ~ {(i1, ... ,ik)Fп(i1, ... , ik)=1(i1, ...
,ik) ЕF(n, i1, ... , ik),wk, (n,i1, ... ,ik)Е D},(i1, ... , ik) Е Dп.Определение. (k + !)-местная частичная z',-функция F: D-+ w,D ~ wk+I, называется универсальной для k-местных частичныхz',-функций, если семейство { Fn I n Е w} состоит из всех k-местныхчастичных z',-функций.Прежде чем переходить к доказательству существования универ·сальных частичных z',-функций, установим общий факт, имеющий самостоятельный интерес.§ 7.4. Е-предикаты и Е-функцииПредложение279(теорема об униформизации). Пусть7.4.2k >Ои Q <:;:; wk+ 1 - "J:,-предикат на П.
Тогда существует k-местнаячастичная "J:,-функция h: 8 - w, 8 <:;:; wk, такая, что Гh <:;:; Q,8h=дQ= {(io, ... , ik-1)1существует i Е w такое,чтоДо к аз ат ель ст в о. Пусть Ф(хо,... , xk) -У:,-формула такая, чтоТак как П - ограниченная алгебраическая система,по принципу У:,-рефлексии имеем Фn(:3uФСи)). Следовательно,Q= Фf![хо, ... , xk]-(io, ...
,ik-1,i) Е А}.=Формула ф(и) является Ло-формулой, поэтому характеристическаяфункция х Ло-предиката (Ф(и))f![хо, ... , Xk, и] является У:,-функцией.Рассмотрим следующие функции:ho(xo, ... , xk) =. х(хо, ... , Xk-1, l(xk), r(xk)),h1 (хо, ... , xk-1) =. µxk(sg(ho(xo, ... , xk))= О),h2(xo, ... , Xk-1) =. l(h1 (хо, ... , Xk-1)).Функцииhoиsg(ho)получены из Х,l, r, sg подстановкой, следоh1 получена из sg(ho) мивательно, являются У:,-функциями.
Функциянимизацией, следовательно, является частичной У:,-функцией. Функцияh2получена изlиподстановкой, следовательно, является частичнойh1У:,-функцией.Проверим, что частичная У:,-функцияh2удовлетворяет заключениюпредложения. Пусть (io, ... ,ik-t) Е 8h 2 и i =. h2(io, ... ,ik-1).
Тогда(io, ... , ik-1) Е 8h,. Пусть j =. h1 (io, ... , ik-1). По определению h1 получаем sg(ho(io, ... , ik-1,j)) = О, поэтому ho(io, ... , ik-1,j) = 1:ho(io, ... , ik-1, j)=x(io, ... , ik-1, l(j), r(j))= 1.Следовательно, (io, ... , ik-1, l(j), r(j)) Е (ФСи))f![хо, ... , Xk, и],ПF ф(u)(io, .. ,,ik-1,l(j),r(j)),Пт.е.F :3иФ(и)(iо, ... , ik-1, l(j)),(io, .. ,,ik-1,l(j)) Е Q, ноl (j)= l (h1 (io, ... , ik-1)) = h2( io, ... , ik- 1),т.е.
(io, ... ,ik-1,h2(io, ... ,ik-t)) ЕQ и Гh 2<:;:;Q.Гл.2807.ВычислимостьПусть (io, ... , ik-1) Е wk такова, что существует i Е w такое, что(io, ... , ik-1, i) Е Q. Тогда из Q = (:3иФ<и)) 11 [хо, ... , xk] следует, чтоП F :3иФ< и) ( io, ... , ik-1, i) и существует j Е w такое, чтопL ф(Л(·ZO,нI·... , Zk-1,Z·) .Поэтомуx(io, ... ,ik-1,i,j) = 1,ho(io, ... ,ik-1,c(i,j)) =x(io, ... ,ik-1,i,j) = 1,sgho(io, ... ,ik-1,c(i,j)) =0.Итак, функция= t5h 1 •h1определена для (io, ... ,ik-1) и (io, ... ,ik-1) Е t5h 2Предложение7.4.2доказано.=ООтметим еще одну связь между Е-множествами и Е-функциями.Предложение7.4.3.Тогда существует==т{f(n) 1 nЕПустьЕ-функцияR<;;;; w -f:непустое Е-множество.w -+ w такая, чтоR=PJ==тw}.Доказательство.
Фиксируем по Е R. Пусть R = (:3uФ(и)) 11 [хо],где ф(и) - до-формула. Определим функцию f: w -+ w так, что длялюбого п Еw,f(n)==т {l(n),по,Легко проверить, что PJ=П F ф(r(n))(l(n)),П F ~ф(r(n))(l(n)).R и Гf= w11 [xo, х,],где Е-формула Фопределена так:Ф(хо, х,) ==т ф(r(хо)) (l(xo))/\ х, ~ l(xo)V ~ф(r(хо)) (l(xo))/\ х, ~ по.оПредложение доказано.Предложение 7.4.4. Пусть k > О; Uk+ 2 - (k + 2)-местный предикат, универсальный для (k + 1)-местных Е-предикатов; иk+' (k + 1)-местная частичная Е-функция такая, что Г uk+1 <;;;; Uk+ 2 идuk+1= {(io, ...
, ik)1существует i Е w такое,что. ... ,Zk,Z. .)(io,(такая функция существует в силу предложения7.4.2).Еuk+2}Тогда функция uk+I универсальна для k-местных частичных Е-функций.'f:.-предикаты и 'f:.-функции§ 7.4.281Доказательство. Действительно, пусть h: 8---. uJ,k-местная частичная Е-функция. Тогда ее график Гh ~+ l )-местный(k8 ~ uJk, uJk+I естьЕ-предикат и в силу универсальности Е-предикатаuk+ 2 существует n Етакое, чтоuJ. .
)!(n,i1,.г h-uk+2_{(.- пZl,•••,lk,Zk+I. . )... ,Zk,Zk+IЕuk+2} .Проверим, что для этогоn функция h совпадает с функцией u~+I2Так как Г uk+I ~ uk+ , имеем Г u~+I ~ и~+ 2 = Гh, т. е. h - расширениефункции u~+I. Поэтому достаточно показать, что бh ~ 8и~+1. Пусть(i,, ... ,ik) Е бh. Тогда(i,, ... ,ik,h(i1, ... ,ik)) ЕГh ~u~+ 2,. ... , Zk,. h(.i1, ... , ik. ))(n, i1,Еuk+2 ,(n,i,, ...
,ik) Е дuk+1.Но тем самымДля(k+ 1)-местнойция Fn: uJk---.. . . , ik)(i1, ... , ik) Е би~+1, что и требовалось доказать.для всехЕ-функцииF,гдеk >О, и любогоопределенная так, что Fп(i,, ... ,ik)uJ,i1, ... , ikDфункn= F(n,i,, ...Е uJ, является, очевидно, Е-функцией. Поэтому естественно задаться вопросом о существовании универсальныхЕ-функций. Однако, в отличие от класса частичных Е-функций, ситуация здесь другая.ПредложениеF:uJ 2 ---. uJ7.4.5.Несуществуетдвуместнойпринимающей в качестве значений лишь О илитакое, чтоFnl,uJ---. uJ,существуетnЕ uJ= h.До к аз ат ель ст в о.ществует.
ПустьnЕ-функциитакой, что для любой одноместной Е-функции h:Е uJ. Ясно, чтоh: uJh -Предположим,---. uJ такова,чточтоh(n)такая;=сфункцияsgF(n, n)Fсудля всехфункция, принимающая в качестве значенийl. Тогда существует по Е uJ такое, что Fn 0 = h. Однакоh(no) = sgF(no,no) = Fn0 (no) = F(no,no), что невозможно, посколькуsgk -:/= k для всех k Е uJ.
Полученное противоречие завершает доказательство предложения.Dлишь О иСледствиецияh7 .4.6.Существует двуместная частичная Е-функтакая, что не существует двуместной Е-функциичто Гh ~ Г 9(g -Е-доопределениеДо к аз ат ель ст в о. Пусть и 2 ция,g:gтакой,h).двуместная частичная Е-функуниверсальная для одноместных частичных Е-функций.uJ 2 ---. uJЕслитакова, что Г uz ~ Г 9 , то g является универсальной для282Гл.одноместныхh: w----, w~>функций,7.т. е.ВычислимостьдляЕ-функцией по предложениюСледствиеhодноместной= 9п·Е-функцииОднако g не может бытьО7.4.5.Существует двуместная частичная Е-функция7 .4. 7.принимающая значения О илиh,любойсуществует п Е w такое, что1ине имеющая Е-доопределения.До к аз ат ель ст в о. Как и выше, устанавливается, что в качестветакой функции можно взять функцию sg(u 2 ).Следствиецияho,ОСуществует одноместная частичная Е-функ7 .4.8.принимающая значения лишь О и1ине имеющая Е-доопределения.Доказательство.
Пусть h такая же, как в следствии 7.4.7,ho(x) '==; h(l(x), r(x)), х Е w. Если go - Е-доопределение ho, тоg(x, у)'==; go(c(x, у)) - Е-доопределение h, что невозможно.ОиОпределение. Два непересекающихся Е-подмножестваJlo, R1называются Л-неотделимыми, если не существует д-множества~w такого, чтоСледствиеIloиJlo~DиD~n R1 = IZJ.Существуют7.4.9.~ wDд-неотделимыемножестваR1.До к аз ат ель ст в о. Пустьhoтакая же, как в следствииIlo'==;{пI п Е дh0 , ho(n) = О},R1'==;{пI п Е дh 0 , ho(n) =7.4.8,и1}.В этом случаеIlo и R1 - непересекающиеся Е-множества (еслиГhа = Ф!1[хо,х1], то Ilo = ((Ф)~ 1 )!1[хо] и R1 = ((Ф);(о))!1[хо]).
Если D ~~ w такое, что Ilo ~ D и D n R1 = IZJ, то характеристическая функцияXD доопределяет ho, т. е. Гhо ~ Г xv. Но если D - Л-множество, тоXD - Е-функция. Поэтому не существует Л-множества D такого, чтоIlo~DиDПR1=IZJ.ООпределение. Пусть А, В ~w. Будем говорить, что А т-сводитсяf: w ----, wк В (обозначается А ~m В), если существует Е-функциятакая, чтоnEAили, что равносильно,{=>f(n)EB, nEw,1- 1 (В) = А.Отметим некоторые простейшие свойства m-сводимости.(1)Для любых А, В, С~ w верно А ~m А; если А ~m В и В ~m С,то А ~m С.Теорема Чёрча и теорема Гёделя о неполноте§ 7.5.Множество А m-сводится к А тождественной функцией283idw.Если f и g - Е-функции такие, что А= 1-'(В), В= g- 1(C), тоА= (gf)- 1 (С).(2)Если А ~т В и ВЕ-множество (д-множество), то А-является Е-множеством (д-множеством).Еслиf -Е-функция такая, что А= 1-'(В) и В= Фn[хо] дляЕ-формулы Ф, то А= ((Ф)f(xo))n* [хо].§ 7 .5.Теорема Чёрча и теорема Гёделя о неполнотеПусть Амножество предложений сигнатуры ао-= (О, s, +, ·, ~).Введем следующие обозначения:Mod(A) - класс всех алгебраических систем Qt сигнатуры ао таких,!2t f= Ф для любого Ф Е А;Th(K) (теория класса К) - множество всех предложений Фчтосигнатуры ао таких, что Qtf=Ф для любой системы Qt из класса Калгебраических систем сигнатуры ао.Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
