1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 56
Текст из файла (страница 56)
Множество А предложений сигнатуры ао называетсятеорией, если А-теория некоторого класса К.Заметим, что А является теорией тогда и только тогда, когда А== Th(Mod(A)).Теория А называетсянепротиворечивой, если-полной, если А-разрешимой, еслит. е. А=жеством-Th( {!2!})w,Mod(A)-/с 0;теория класса, состоящего из одной системы,-для подходящей системыG(A)={G(Ф)1!2!;Ф Е А} является Л-подмнои неразрешимой в противном случае;наследственно неразрешимой, если любая теория Ао, содержащаяся в А, неразрешима.Определение. Множество А предложений сигнатуры ао называется-системой аксиом для теории В, если В=перечислимым, еслиG(A)Th(Mod(A));w.есть Е-подмножествоФормулируемые ниже теоремы являются наиболее принципиальными утверждениями об алгоритмической природе теорий.Теорема7.5.1(А.
Чёрч). Наименьшая теория Та 0 сигнатуры ао,состоящая из всех тождественно истинных предложений сигнатуры ао, является неразрешимой.Теоремаложение7.5.2(теорема Гёделя о неполноте). Существует предсигнатуры ао такое, что Пf=Ai, и если А - непротиворечивая перечислимая теория сигнатуры а0 такая, что Aj Е А,Aiто А не является полной.284Гл.7.ВычислимостьНачнем с некоторых предварительных рассмотрений, которые приведут к доказательству этих теорем.Рассмотрим семейство А, формул сигнатуры ио:1)хо~хо,2)3)4)5)6)7)8)9)10)11)хо~ х, /\х1 ~ х2---4хо~ х2,хо ~ х,---4хо ~ х,,/\ х,~ хохо ~ х1 V х1 ~ хо,О~ хо,хо~s(xo)/\~(хо~хо~ х, /\~(хо~ х,)s(xo)),---4 s(xo)~ х,,хо +о~ хо,хо+s(x,)~s(xo + х,),хо· О~ О,хо·s(x,)Пусть А,~(хо· х,)-+ хо.конъюнкция формул1-11иAjс:=;\lxo\lx1\lx2A1 -предложение сигнатуры ио.Предложение7 .5.3.
Пусть 2t 2t F Aj. Тогдаалгебраическая система сигнатуры ио такая, чтома П' ~enct2t,изоморфная П.До к аз ат ель ст в о.ние ~ 21 -существует концевая подсистеИз истинностиAjв2tследует, что отношелинейный порядок на А (следствие формул 1-4), Ощ-наименьший элемент в А относительно этого порядка (следствие изи для любого а Е А, а~ 21 s 21 (a),а =f.
sщ(а)(т. е. а< 2t s21 (a))5)иs2t(a) ~2t Ь, если а < 21 Ь.Определим отображениеh: w---4А по индукции:h(O) с:=; 021 , h(п+ 1) с:=; s2t(h(n)).Покажем, чтоw'с:=;h(w) -начальный сегмент А иh -изоморфизммежду(w, ~) и (w', ~ 21 1(w')2). Докажем индукцией поп Е w, что если[п] с:=; {О, 1, ... , п }, то h([п]) <:;;: w' - начальный сегмент А и h 1[п] изоморфизм между ([п], ~ 1[п] 2 ) И (h([п]), ~ 21 1(h([n])) 2 ).Так как h(O) = 02t - наименьший элемент А, сформулированноевыше утверждение справедливо для п=О.Пусть п Е w таково, что для [п] верно следующее:чальный сегмент А и h(h([п]), ~ 21 1(h([п])) 2 ),1 [п] -[п+1] =h([n]) -наизоморфизм между ([п], ~ 1 [п]2) и[п]U{п+1},h([n + 1]) = h([п]) U {s 21 (h(n))},§ 7.5.Теорема Чёрча и теорема Гёделя о неполноте285h(n) <2( s'lt(h(n)),гдеи hh(n) -наибольший элемент вh([n]).Поэтомуs2t(h(n)) .J. h([п])r [п + 1) разнозначно. Если а Е А и а h(k), ТО по индукционномупредположению а Е h([n]) ~ h([n + 1]) в случае k ~ п; а Е h([п + 1])в случае k = п + 1 и а= h(n + 1).
Если а <ot h(n + 1) = sot(h(n)), то~2(а ~2t h(n). Действительно, либо а ~2t h(n), либо h(n) <2t а. Во второмслучае s2l(h(n)) ~2t а и h(n + 1) = s2t(h(n)) ~2t а, что невозможно.Следовательно, а ~2t h(n) и а Е h([n1)). Итак, h([п 1]) - началь+ный сегмент А иh+переводит наибольший элемент пв наибольший элемент s2t(h(n)) в h([п+ 1)).+ 1 в [п + 1]r [п + 1) -Поэтому hизоморфизм соответствующих линейно упорядоченных множеств.Из приведенных рассуждений следует, что1.;./~h(1.JJ) -начальный сегмент А и h - изоморфизм между (1.JJ, ~) и (1.JJ', ~2tr (1.JJ') 2 ).Покажем, что h(n + т) = h(n) +2t h(m) и h(n · т) = h(n) .2t h(m) для1.JJ.
Предположим противное: пусть по, то Е 1.JJ такие, чтоh(no + то) =f. h(no) +2t h(mo) и по Е 1.JJ - наименьшее п, для которогосуществует т Е 1.JJ такие, что h(no + т) =f. h(no) +2t h(m), а то наименьшее m такое, что h(no + то) =f. h(no) + 2th(mo). Покажем, чтото =f. О. Действительно, если то = О, толюбых п, т Епоh(no) +2t h(mo)так как 2(+ то = по + о = по,= h(no) +2t h(O) = g(no) +2t 02t = h(no),F \lxo(xo +О~ хо).Таким образом, то=f.О, то= т+ 1 = s(m)и, ввиду минимальности то,h(no + т)h(no +то)= h(no= h(no) +2t h(т),+ s(m)) = h(s(mo + п)) == sot(h(no + т)) = s2t(h(no) +2t h(m)) == h(no) +Q( sot(h(m)) = h(no) +'! h(то)(соотношение s'l!.(h(no)+2t h(т)) = h(no)+ш s2t(h(m)) вытекает из соF \lxo\lx, (хо+ s(x,) ~ s(xo + х, ))).
Полученное противопоказывает, что h(n + т) = h(n) +Ш h(m) для всех п, т Е 1.JJ.отношения 2(речиеДоказательство равенстваh(n · т)= h(n) .2t h(т)Из вышеприведенных рассуждений видно, чтомкнуто относительно операций sш,изоморфна П(h:+2t , ·21П --+ П'). Кроме того,Следовательно, П' ~end 2i.1.JJ1аналогично.1.JJ 1= h(1.JJ)~ А заи подсистема П' ~ 2(-r 1.JJ'начальный сегмент А.D286Гл.Следствие7.ВычислимостьДля любых 'У:.-предложения Ф сигнатуры сто7 .5.4.иалгебраической системы Q{ сигнатуры стоQ{F Ai-> Ф.из ПFФ следуетF Ф. Если Q{ F ~Aj, то Q{ p Ai-, Ф.F Ai, то по предложению 7.5.3 существует П' ~end Q{ такая,F Фи Q{ F Ф, так как Q{ - концевое расширение П', а Ф -Доказательство.
Пусть ПЕсли Q{что П'(~ Щ'У:.-предложение (см. предложениеВ§ 7.4было'У:.-множествRo, R,установлено~w,О5.7.1).существованиенепересекающихсяне отделимых Л-множествами.Пусть :JxoФ(xoJ(x1), :JхоФ(хо)(х1)- 'У:.-формулы такие, чтоRo =(:JxoФ(xo))r![x1],=(:JxoФ(xo))r![x1].R1Определим следующие последовательности 'У:.-формул:Фо(хо, х1) ~ ф(хо) (х1 ),Ф8(хо) ~ (Фо)~',Фп+I (хо, Хп+2) ~Ф~+l (хо)~:Jxn+I ~ s(хп+2)(хп+I(Фп+1)~n+ 2 (=::::!s(Хп+2):Jxn+I ~ s(O)(xn+I::::J/\ Фп(хо, Хп+1)),s(O) /\ Фп(хо, Хп+1))),Фо(хо,х1) ~ q;(xo)(x1),Ф8(хо) ~ (Фо)~',Фп+1(хо,Хп+2) ~ 3хп+1 ~ s(xn+2)(xn+I::::!s(хп+2) /\ Фп(хо,Хп+1)),Ф~+ 1 (хо) ~ (Фп+1)~п+2,Лп ~ :Jхо(Ф~(хо) /\ \iхп+2 ~ Хо ~ч:,~(хп+2)),0п ~где п Еw.Предложение7.5.5.(а). Если п ЕRo,то предложениеR1и Q{ -(т.
е.0nF Aj,Справедливы следующие утверждения.0nтождественно истинноЕ Та0 ).(б). Если п ЕQ{Ai _, Лп,то Q{алгебраическая система такая, чтоF ~еп.До к аз ат ель ст в о. Из определений формул Ф~, Ф~ следует, чтодля любой алгебраической системы Q{ сигнатуры сто и а Е А справедливы эквивалентностиТеорема Чёрча и теорема Гёделя о неполноте§ 7.5.287~ р Ф~(а) ~ ~ р ф(а)(n);здесьn ;=; s( ...
s(O) ... )."-v-'п разПусть п Е'R,Oи ~произвольная алгебраическая система сигнату-ры ао. Если~ р ~лj, то~ рсистема П'Aj---.Лп. Если~ рAj,то существуетизоморфная П. Ввиду соотношения П р :3хоФ(хо) (n)для некоторого а Е ,,./ имеем П' р ф(а)(n), ~ р ф(а)(n), так как ф(хо) Ло-формула. Если Ь ~ot а, то Ь Е 1.;/ и П' р ~w(Ь)(n), в противномслучае П' р :3хоФ(хо)(n) и п Е R1 n 'R,O = 0.
Но тогда ~ р ~w(Ь)(n) и~ р :3хо(Ф(хо)(n) /\ 'v'Хп+2 ~ xo~w(xn+ 2 >(n)), ~ р Лп И~ р Aj---> Лп.~end ~.Пустьжем,п Ечтоиа Е АП'~end~R1~ ртакой,-и~~лп.система-такая,Действительно,чточто~ рпредположим,Aj.чтоПока~ р Лп~ р Ф~(а) /\ Vхп+2 ~ а~Ф~(хп+2).Пустьподсистема, изоморфная П. Если а Е ,,/, то П' р Ф~(а),П' р ф(а)(n),П' р :3хоФ(хо)(n),n R1 = 0,Следовательно,'R,O(и п Еа1.J.Так как п Е R1, верно Пр :3xoФ(xoJ(n) и П' р :3x0 w(xoJ(n),iсуществуетR1).Поэтому п ЕП р :3хоФ(хо)(n).п Еа' Е 1.;/такой,'R,Oчточто невозможно.
ПустьП' р w(a')(n),П' р Ф~(а')и~ р Ф~(а'). Однако 1..,/ начальный сегмент А. Следовательно, а' ~Qt а. Поэтому ~ р ~(Ф(а)(n) /\ Vхп+2 ~ a~w(xn+ 2 J(n)),~ р ~(Ф~(а) /\ Vхп+2 ~ а~Ф~(хп+2)).показывает, что~F ~лпи ~ПолученноеF ~еп.В качестве следствия предложенияпротиворечиеD7.5.5докажем утверждение, изкоторого вытекают две основные теоремы.Предложение(сигнатуры ао)теорияTh(K)7 .5.6.Еслисодержиткласссистему ~Калгебраическихтакую,что ~ рсистемAj,токласса К неразрешима.До к аз ат ель ст в о.Установим сначала, что функция h: 1.JJ ---.
1.JJh(n) = G(8n) для любого п Е 1.JJ, является :Е-функцией.Пусть то;=; G(Ф(хо)(х1)) = G(Ф(хо, х1)), m~ ;=; G(Ф8(хо)) и функция ho: 1.JJ ---. 1.JJ определена примитивной рекурсией:такая, чтоho(O)=то,ho(n + 1)= c(l 1, сз(п + 1, с(2, c(l, п + 2)),с(7, с(с(5, c(c(l,n + l)c(2, c(l, п + 2)))), ho(n))))).Легко проверить, что ho(n) = G(Фп) для всех п ЕПусть h~: 1.JJ ---. 1.JJ определена так, чтоh~(O) = т~,1.JJ.288Гл.7.Вычислимостьh0(n+ 1) =c(ll,cз(n+ 1,с(2,с(О, 1)),с(7,с(с(5,с(с(1, п0 = G(Ф~)Тогда h (n)+ 1), с(2, с(О, 1)))), ho(n))))).для всех п Е w.Аналогично определяется Е-функция= G(\J!~)для всех п Е w. Пустьh1: w--+ wтакая, чтоh1(п)=h1'(n) ~ Sub(h'(n), c(l, п + 2), О), п Е w.Напомним, что функциятим, что h1'(n)определена в упражненииSub= G((\J!~);~+z),3 § 7.3.Замеп Е w.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
