1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 57
Текст из файла (страница 57)
Пустьhj(n) = с(12, с(п + 2, c(c(l, О), c(lO, h1'(n))))), п Е w.Тогда hj(n)= G(Vxn+2~ хо ~w~(хп+2)), п Е w. Пусть0h'(п) = с(lЗ, с(О, с(7, c(h (n), hj(n))))),Тогда h'(n)п Еw.тельно=п Еw.G(:3хо(Ф~(хо) 1\ Vxn+2 ~ xo~\J!~(xn+2)))=Полагаемh: w--+G(Лп), гдеh(n) ~ с(9, c(No, h'(n))), где No ~ G(Aj). Следоваw-искомая Е-функция.Вернемся к доказательству предложения7.5.6.Предположим, чтокласс К алгебраических систем сигнатуры ао таков, что существует2tЕ К такая, что2tрAjиTh(K)разрешима, т. е.G(Th(K))Л-множество.РассмотримЕ-функцияимножествоDЛ-множество. Покажем,0п Е Та 0 ~D ~ h- 1 (G(Th(K))). Поскольку hк д-множеству G(Th(K)), то Dчто Ro ~ D и D n R 1 = 0. Если п Е Ro,m-сводитсятоTh(K).
Следовательно,G(0п)= h(n)Е G(Th(K)), п Е h- 1 (G(Th(K))= D,Ro ~ D. Пусть п Е R1. Тогда 2( F ~еп и 0n ~ Th(K), G(0п) == h(n) ~ G(Th(K)), п ~ h- 1 (G(Th(K))) = D, т. е. R 1 n D = eJ. Носуществование такого Л-множества D противоречит выбору неотделимых Ro и R1.От. е.Следующее утверждение является просто переформулировкой предложения7.5.6.Предложениечто2tрAj,7.5.7.то теорияЕсли2t - алгебраическая система такая,Th(2t) является наследственно неразрешимой.Из предложения7.5. 7непосредственно следует теорема Чёрча. Длядоказательства теоремы Гёделя установим следующееПредложениеА разрешима.7 .5.8.Если А-перечислимая полная теория, тоТеорема Чёрча и теорема Гёделя о неполноте§ 7.5.До к аз ат ель ст в о.Если Аuoпредложения Ф сигнатурылибо ~Ф Е А. Пусть А289полная теория, то для любого-имеет место альтернатива: либо Ф Е А,перечислимая полная теория и Ф(хо)-:Е-формула такая, что G(A)=Ф 11 [хо].
Следующая :Е-формулабудет определять характеристическую функцию множества(Sen(xo);::::;л(Ф(хо)функцияSen;::::;О) VПредложениеи7.5.67 .5.9.О);;::::;о2 § 7.3.следует теорема Гёделя о неполноте.7.5.8Если АTh(Mod(A)),G(A):Sen(xo);::::; 1/\Ф(с(lО, хо))/\ х,1Vопределена в упражненииИз предложенийжений и В=/\ х 1;: : ;О/\ х,-\J!(xo, х,)перечислимое множество предло-то Вперечислимая теория.-Набросок доказательства. Используя теорему о полноте длягильбертовского исчисления RQ-формул (см.
конец§5.7),можно описать множество В как семейство тех RQ-предложений Ф, для которыхсуществует доказательство из А, т. е. последовательность Фо,=RQ-формул такая, что ФnФ и для любогоi~n... , Фnвыполнено одно изследующих четырех условий:Фi-аксиома, т.е. имеет вид одной из аксиомили аксиом11'или12'(см.1-14(см.§4.5)§ 5.7),Фi принадлежит А,j, l < i такие, что Фi1 (см. §4.5),существует j < i такое, что Фiправил вывода 2, 3 (см. §4.5), 2'существуютполучена из Фj и Ф1 по правилувыводаДоказательство Фо,...
, Фnk, n Е w такой, что Г(k, i)G(B)'=i {тЕ(k, n)= G(Фi),существуютw,3'(см.по одному из§5.7).из А можно кодировать паройчиселImполучена из Фjилиk,nЕwтакие, чтокодирует доказательство Фотакое, что Фn-(k, n)i ~ n. Тогда... , Фnиз АRQ-предложение и G(Фn)= m}.Далее остается только рутинное доказательство того, что{ (k, n)1k, n Е w, (k, n) кодирует некоторое доказательство из А} ~ w 2является :Е-предикатом, если Аний.Предложениенеречислимое множество предложео7.5.9позволяет сформулировать теорему Гёделя в следующей форме.10-Ю. Л. Ершов, Е. А.
ПалютинГл.290Теорема7.5.107.Вычислимость(вариант теоремы Гёделя о неполноте). Еслинепротиворечивая теория В содержитAjи имеет перечислимуюсистему аксиом, то она неполна.В заключение рассмотрим предикатный вариант а}{ сигнатурыuoи предикатные варианты модели П и теории, определяемой предложениемAj.ПустьП.,..;:::;S,гдеА,s: "-' ----+ "-',М-предикаты,(w, О, S, А, М, ~).соответствующие+: w2 ----+ "-', ·: w2 ----+графикамфункцийw. Заметим, что функции s,+и ·являются до-определимыми в П.,...
Поэтому П и П.,.. имеют одинаковыеI;-предикаты и I;-функции.Для п Е "-', [п]= {О, l, ... , п}полагаем П~Рассмотрим следующее семействоl)2)3)4)5)6*)7*)8*)9*)Aj;:::;П.,.. ~ [п).формул сигнатурыUo:Хо~ ХО,хо ~ х, /\ х, ~ х2хо ~ х,----+хо ~ х2,/\ х, ~ хо ----+ хо ~ х,,хо ~ х, V х, ~ хо,О~ хо,S(xo,x,)----+ хо~ х, /\~(хо~ х,),хо~ х, /\~(хо~ х1)----+ 3x2(S(xo,x2) /\х2 ~ х,),Ad(xo, О, хо)/\ (Ad(xo, х,, х2) /\ ~(х, ~О)----+ хо~ х2 /\~(хо~ х2)),(Ad(xo, х,, х2) /\ S(x,, хз) /\ S(x2, х4) ----+----+ Ad(xo, хз, х4)) /\ (Ad(xo, х,, х2) /\ S(хз, х,)----+----+ 3x4(Ad(xo, хз, х4) /\ S(x4, х2))),10*) Ml(xo, О, О),l l *) (Ml(xo, х,, х2) /\ S(x,, хз) /\ Ad(x2, хо, х4) ----+----+ Мl(хо,хз,х4)) Л (Ml(xo,x1,x2) /\ (Ml(xo,x1,x2) Л S(хз,х,) ----+----+ 3x4(Ml(xo,x3,x4) I\Ad(x4,xo,x2))),12) S(xo,x1) /\ S(xo,x2)----+ х, ~ х2,13) Ad(xo,x1,x2) /\Аd(хо,х,,хз)----+ х2 ~ хз,14) Ml(xo,x1,x2) /\Мl(хо,х,,хз)----+ х2 ~ хз.Пусть ЛАj(хо,х,,х2,хз,х4) - конъюнкция формул l-5, 6*-ll*,12-14.
Полагаем Л7";:::; \:/хо\:/х1\:/х2\:/хз\:/х4 ЛА,. Заметим, что Л7" предложение СИГНаТурыUo.Имеет место следующий аналог предложенияПредложение7.5.3.7 .5.11. Пусть !2i - алгебраическая система сигнатурытакая, что !2i F Л7". Если !2i конечна и IAI = п + l, то!2t ~ П~. Если !2i бесконечна, то она имеет концевую подсистему!2to ~end !2t, изоморфную П.,...UoТеорема Чёрча и теорема Гёделя о неполноте§ 7.5.291До к аз ат ель ст в о. Как и при доказательстве предложенияпопытаемся построить для каждого п Е w отображение hп: [п]7.5.3,----,Атак, чтобы выполнялись условия:hп(О)(hп(k), hп(k= 021 ,hп([п])-+ 1))Е 8 21 , k< n,начальный сегмент линейно упорядоченного множества(А, :(21),hп- изоморфизм между П~Для п=1(О, S, :()О такое отображениеhoиI hп([п])) 1 (О, S, :().(2tсуществует. Предположим, чтодля некоторого п Е w требуемое отображение hп уже построено.
Еслиhп([п]) = А, тоIAI =п+ 1,и hп+I не может быть построено.Пусть hп([n]) =1- А и а Е А\ hп([п]). Так как hп([п])сегмент А и hп(n) - его наибольший элемент, то hпl:;!;)ку формула7* входит конъюнктивно в Л Aj и 2tПусть а' Е А таков, что2t- начальный< 21 а.F А1 ,ПоскольтоF S(hп(n), а'). Заметим, что согласно форму+ле 12 такой а' единствен. Полагаем hп+I (п1)для k :( п. Нетрудно проверить, что hп+I: [п'==;а' и hп+I (k) = hп(k)----, А удовлетворя+ 1]ет сформулированным выше условиям. Итак, еслиh'==;Uhп:nEwсегмент А иw ----,h-А отображаетwизоморфизм междунаw''==;2t бесконечна, тоh(w); w' - начальныйn1r 1(О, S, :() и (2t I w') 1(О, S, :().Покажем, что если отображение hп определено, то оно являетсяизоморфизмом между П~ и12tI hп([п]).Сначала установим, что hпIизоморфизм между П~ (О, S, Ad, :() и (2t hп ([п]))этого достаточно доказать утверждения ( 1), (2).(1) Если k, l, k + l :( n, то (hп(k), hп(l), hп(k-1(О, S, Ad, :().
Для+ l))Е Ad 21 .Предположим, что утверждение неверно, и пусть (ko, lo) - парас наименьшим номером (т. е. c(ko, lo)) такая, что ko, lo, ko + lo :( пи (hп(ko), hп(lo), hп(ko + lo)) е/:. Ad2l. Заметим, что lo не может равняться нулю, так как8*.
Таким образом, lo > О и lo = l + 1 (дляlo - 1). Поскольку c(ko, l) < c(lo, lo), имеем (hп(ko), hп(l), hп(ko ++ l)) Е Ad2l, ko + lo :( п. Поэтому ko + l <пи (hп(ko + l), hп(ko + lo)) Ечто следует из формулыl=Е52t_ Кроме того, (hп(l), hп(lo)) Е 52t_ Ввиду первой конъюнкции формулы 9* справедливо соотношение (hп(ko), hп(lo), hп(koчто противоречит выбору ko, lo.10*+ lo))Е Ad 21 ,7.Гл.292(2) Если k, l ~ п, k + l >(hп(k), hп(l), hп(т)) Е Ad2t.Вычислимостьп, то не существует т ~ п такого, чтоПредположим, что утверждение неверно, и пустьпара(ko, lo) -ko, lo ~ п, ko + lo > п и существует(единственное) т ~ п такое, что (hп(ko), hп(lo), hп(т)) Е Adot.
Ясно,что lo > О. Пусть lo = l + 1. Тогда (hп(l), hп(lo)) ЕВвиду второйс наименьшим номером такая, чтоsot.конъюнкции формулы9*имеем2t р 3x4(Ad(hп(ko),hn(l),x4) /\S(x4,hп(m))).Если а Е А таков, что (а,hп(т)) Е>sot, (hп(ko),hп(l),a) Е Adot, тот>+ 1 = т.О и а= hп(т') длят' такого, что т'Рассмотрим два возможных случая.1: ko + l = п. Согласно (1) имеем (hп(ko), hп(l), hп(ko +Е Adot, hп(т') =а= hп(ko + l) = hп(п), т' < т ~ n(= ko + l).Случай+ l))Приходим к противоречию.Случай 2: ko<п, пара(ko, l)+l >п. В силу (hп(ko), hп(l), hп(т')) Е Adot, т' <ko, l ~ п, ko + l > п итакже удовлетворяет условиямсуществует т' ~ п такой, что(hп(ko), hп(l), hп(т')) Е Adot, c(ko, l) < c(ko, lo),что противоречит выбору парыИтак,(2t(2)доказано,hпr hп([п])) r (О, s, Ad, ~).(ko, lo).естьизоморфизмП~f(О,S, Ad, ~) иУстановим теперь, ЧТО hп есть изоморфизм2t f hп([п]).
Для этого достаточно доказать утверждения (3)(3) Если k, l, k · l ~ п, то (hп(l), hп(k), hп(k · l)) Е Mlot.П~ иПредположим, что утверждениес наименьшим номером такую, чтоневерно. Выберем паруko, lo, ko · loи(4).(ko, lo)~ п и(hп(ko), hп(lo), hп(ko · lo)) .f. м12t.Заметим, чтоlo=/=- О, так как по формуле10*(hп (ko), hп (О), hп (ko ·О)) = (hп (ko), oot, oot) Е Mlot.Тогда lo = l + 1 и (hп(ko), hп(l), hп(ko · l)) Е Mlot, поскольку c(ko, l) <и п ~ ko · lo = ko(l + 1) =< c(ko, lo). Далее, (hп(l), hп(lo)) Е= ko · l + ko влечет по доказанному вышеsot(hп(ko · l), hп(ko), hп(ko · lo)) Е Adot.Согласно первой конъюнкции формулы11 *имеем(hп (ko), hп (lo), hп (ko · lo)) Е Ml2t,что противоречит выбору пары(ko, lo).§ 7.5.
Теорема Чёрча и теорема Гёделя о неполноте(4)Еслиk·l >~ п,k, l293п, то не существует т ~ п такого, что(hп(k), hп (l), hп (т)) Е MlQ!.Предположим, что утверждение неверно именьшим номером такая, чтоko · lo >ko, lo~ пп и существуетm-пара с наи~ п такое, что(hп(ko), hп(lo), hп(т)) Е MlQ!.Ясно, что lo-1-О. Пусть lo= l + 1.второй конъюнкции формулыQ(11 *Тогда (hn(l), hп(lo)) Е SQ! и ввидуимеемF 3x4Ml(hп(ko), hп(l),x4) /\ Ad(x4, hп(ko), hп(т)).Если а Е А такой, что (а, hп(ko), hп(т)) Е AdQ!, (hп(ko), hп(l), а) ЕЕ MlQ!, то а <QI hп(т) по формуле 8* и а= h(m') для m' такого, чтоm'<m.Рассмотрим два возможных случая.Случай 1:=ko · lп.
СогласноЕ MlQ!, hп(т') =а= hп(п), т'Случай 2: ko · lпара(ko, l)(3)имеем (hп(ko), hп(l), hп(n)) Е< т ~ п. Приходим к противоречию.> п. Ввиду (hп(ko), hп(l), hп(т')) Е MlQ!, m' ~ п,ko, l ~ п, ko · l > п и сущетакже удовлетворяет условиюствует т' ~ п такое, что (hп(ko), hп(l), hп(т')) Е MlQ!. Это противореc(ko, l) < c(ko, lo).rl~ и Qt r hп([п]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
