1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 66
Текст из файла (страница 66)
\:/хп(f>(х1, ... , хп)-+ "ip(x)). Установим следующий факт.Множество Т* = {1.р 1 <р - предложение сигнатуры ао, <р* Е Th(K1)}является такой теорией сигнатуры ао, что Т* ~Th(K0 ).Действительно, обозначим через К0 класс таких алгебраическихсистем 9Л сигнатуры ао, что для 9Л существуют алгебраическая система 91 Е К1 и элементы а1, ... an Е N, удовлетворяющие условиям{l )-(3) в определении относительной элементарной определимости.Тогда по условию теоремы Ко ~ К0 . А из определения отображенияследует, что <р ЕTh(K0)<==;, <р* ЕTh(K1)*для любого предложения <рсигнатуры ао.Отмеченнаяэквивалентностьвытекаетизследующегообщегоутверждения, проверяемого индукцией по сложности формулы <р:§ 8.6.Пусть !J1 Е К, и а,,Неразрешимые теории...
, апЕN335таковы, что !J1F f'(a).Пусть алгебраическая система -!3 и конгруэнтность 'Г/ определены, как в-1-sдля любых Ь , ... , Ь(2).ТогдаЕ L и формулы 'Р(У1, ... , Ys) сигнатуры О"о имеетместо эквивалентностьПоэтому Т*Если'Р Е Т*далибыбы= Th(K0),теория~'Р* Енами так как Ко~ К0 , то Т* ~ Th(Ko).Th(K1) была разрешима, то эквивалентностьTh(K1) и эффективность отображения 'Р f-+ 'Р*эффективнуюпроцедуруразрешимостиТ*. Но наследственная неразрешимость теорииТ* ~мостьTh(Ko) влекутTh(K,).Th(Ko)длятеориии включениенеразрешимость Т* и, следовательно, неразрешиЕсли теория Т( сигнатуры 0"1 содержится вTh(K1) и Kj - классKi ~ Kj.
Согласно замечаниювыше из Ко ~RED К, следует Ко ~RED Kj, тогда в силу доказанноговыше (заменяя К, на Kj) теория Т1* = Th(Ki) неразрешима. Итак,Th(K1) наследственно неразрешима.Овсех систем 9Л таких, что 9ЛF Т(,тоДоказанная теорема является весьма мощным редукционным методом доказательства неразрешимости. Последующие примеры демонстрируют возможности этого метода применительно к различным классам теорий.Теорию Те сигнатуры (П 2 ), определенную аксиомой Vx СП(х, х)/\Л'</у (П(х, у) --+ П(у, х))), назовем теорией графов {без петель). Модели теории Те назовем графами. Если <Вто элементыG=(G, Р)называются вершинами графа, а парыF Теграф,-Е Р(g,, g2)-ребрами.Предложение8.6.2.Для любых натуральных чисел псуществует конечный граф <Вп,k= (G, Q),>3и k >Ов котором относительноэлементарно определима любая модель 9Л мощности п и конечнойпредикатной сигнатуры О" такой, что все предикатные символы в О"не более чем k-местные.Доказательство.Пусть S;::::, {О, 1, ...
,п - 1}, К;::::,kU Sii=Iмножество всех непустых кортежей над S длины, не превосходящей k;kU P(Si)R;::::,над- множество всех не более чем k-местных предикатовi=ISположительной местности;искомого графа <Вn,k·G ;::::, S U К U R -множество вершинЕсли хlxl8.Гл.336= i,=(j1,ь,то положимопределено, еслиiРазрешимые и неразрешимые теории... ,ji) Е Si с к (1 ~ i ~ k) - кортеж длиныh(x) ~ j1, t(x) ~ (j2, ... ,ji) (значение t(x) не= 1).ПустьQo~{(i,j) li/j, O~i,j<n},Q1~{ (х, h(x)), (h(x),х) Jх Е К}U { (х, t(x)), (t(x), х) Jx ЕК,Jxl > 1},Q2 ~ {(Р,х), (х,Р) 1РЕ P(Si),x ЕР, 1 ~ i ~ k};Q~Qo U Q1 U Q2 - множество ребер графа Q5n,k·Из определения видно, что Q5n,k р= Та.Отметим ряд свойств графа Q5n,k, легко вытекающих из определения.1. Если х, х' Е К и lxl = lx'I, то (х, х') (/.
Q.2. Если РЕ R, 9,9 1 Е G и (Р,9), (Р,9 1 ) Е Q, то 9,9 1 Е К и 191 = lg'I.3. Если 90,91,92 Е G и (9i,9j) Е Q для всех О~ i < j < 3, то90,91,92 (/. R.Действительно, если, например,90 Е R, то по свойству 2 справед91,92 Е К и J91J = J92J, а это противоречит свойству 1 в силу(91,92) Е Q.4.
Если х Е К, 9 Е G \ R = S U К и (х, 9) Е Q, то либо 9 = h(x)(9 Е S), либо 9 = t(x), либо х = t(9) (9 Е К).ливоЛемма8.6.3. Если 90, 91, 92, 93 Е G и (9i, 9j) Е Q для всех О~ i << j < 4, то 90,91,92,93 Е S.До к аз ат ель ст в о. Предположим, что вершины 9о,91, 92, 93 Е G(9i, 9j) Е Q для всех О ~ i < j < 4. В силу свойства 3справедливо 9i (/. R, i < 4. Предположим, что 90 Е К. Не уменьшаяобщности, можно считать, что J90J ~ l9il при 9i Е К, О < i < 4. Посвойству 4 имеем либо 9i = h(90), либо 9i = t(90) (случай 90 = t(9i)невозможен по предположению J90J ~ l9il), i = 1, 2, 3, т.
е. 91, 92, 93 ЕЕ {h(90), t(90)}. Отсюда 9i = 9j для некоторых О< i < j < 4, но этопротиворечит предположению (9i, 9j) Е Q. Лемма доказана.Отаковы, чтоСледствие 8.6.4. Формула Ql(xo) ~ 3х13х23хз (Л П(хi, Xj))O~i<j<4истинна в Q5n,k в точности на элементах множестваЗаметим, что формула !.В(хо, х1) ~ ~п(хо, х1) определяет наношение равенства.Для1~ l < kрассмотрим формулуlf1(x1, ...
,x1;yo,Y1, ... ,y1-1) ~ Л Ql(xi)Лi=lОS.Sот§ 8.6. Неразрешимые теории/\:3zo ... :3z1-1(лщyi,Zi)/\ л П(zi,Zi+t)AЛП(zi,Xi+l)).i<lЛемма337i<l-1i<l8.6.5. Для любых Р Е Р(8 1 ), i 1, ... , i1 Е 8, 1 ~ l < k, справедлива следующая эквивалентность:F f1(i1,.,.,i1;P,8 1- 1, ... ,81) {:> х~(!Sn,k(i1, ... ,i1) ЕР.Доказательство. Предположим, что i1, .. ,,i1 Е 8, РЕ Р(8 1 )и (!Sn,k F f1(i1, ... , i1; Р, 8 1- 1, ...
, 8 1). Пусть вершины go, ... , g1-1 Е Gтаковы, чтоl-1l-1l-11(!Sn,k F П(Р,gо) /\ л П(8 -i,gi) /\ л П(gi-1,gi) /\ л П(gj,ij+1).i=lj=li=lТак как (Р,go) Е Q, то go ЕР; так как (go, i1) Е Q, go Е К, i1 Е 8, тоgi Е 8 1- 1 и (g1, go) Е Q, то g1 = t(go); из (g1, i2) ЕЕ Q следует, что i2 = h(g1) = h(t(go)). Далее аналогично доказывается,что для любого О< j < l - 1 справедливо gн1 = t(gj) и iн1 = h(gj)Итак, go ЕР, g1 = t(go), ... , g1-1 = t(g1-2); i1 = h(go), i2 = h(g1 ), ... , i1 == h(g1-1 ). Отсюда, как нетрудно видеть, следует, что go = (i1, i2, ...
, i1)их= (i1, ... , i1) = go ЕР.Обратно, если х = (i1, ... , i1) Е Р, то, полагая go ~ :к, g1 == t(go), ... , g1-1 = t(m-2), получаемi1= h(go);(!Sn,kFтак какll-1л Ql(ij) /\ П(Р,gо) /\ л П(8 1 -i,gi)I\j=li=ll-1/\ л П(gi-1,gi)l-f/\ л П(gj,ij+1),i=lj=lF f1(i1, ... 'i1; Р, 3 1- 1, ... '8 1). Лемма доказана.Пусть CJ = (П~0 ,П~· ), li ~ k, i ~ s, - некотораят. е. (!Sn,kD••• ,сигнатура, !JЛ=(8, Ро, ... , Ps) - модель сигнатуры- 1} ).
Тогда легкоQl(xo), 'Б(хо, х1 ),проверить, используя леммуCJО ~i~графепредикатная{О, 1, ... , n-что формулы~!1, (хо, ... , х1,-1; Zi, Yi,-1, Yl,-2, ... , У1),s, относительно(!Sn,k, если вPo, ... ,P8 ,8 1, ... ,8k-l Е R.в=8.6.5,!i(Xo, ... , Х/,-1, Zo, ... , Zs, У1, ... , Yk-1)~(8элементарнокачествеопределяютпараметроввзятьмодель!JЛпредикатыDГл.338Разрешимые и неразрешимые теории8.Равномерный характер относительной элементарной определимости, указанный в доказательстве предложения8.6.2,позволяет получить в виде следствияПредложениести ~48.6.6.Любой класс К конечных моделей мощноконечной предикатной сигнатуры относительно элементарно определим в классе Gfin конечных графов (даже в классе{~п.kln~4,k~O}).ОВ качестве следствия предложения8.6.6установим важную длядальнейших приложений теорему.Теорема8.6.
7.Класс Gfin всех конечных графов имеет наследственно неразрешимую теорию (даже в языке без равенства).~иДоказательство. По предложению 7.5.13 класс К4 ;::::': {П~ 1 п ~4} имеет наследственно неразрешимую теорию. Тогда теорема 8.6.1предложение 8.6.9, примененные к классу К4 , дают заключениетеоремы.ОТеорема8.6.7будет использована далее для доказательства неразрешимости ряда интересных алгебраических теорий.Отметим также одно несложное, но принципиальное следствие теоремы8.6.7.Теорема8.6.8.Если сигнатура CJ содержит по крайней мереодин предикатный символ местности ~функциональный символ местности ~сигнатурыCJ2,2 илипо крайней мере одинто исчисление предикатовнеразрешимо.До к аз ат ель ст в о. Неразрешимость исчисления предикатов сигнатуры (П 2 ) следует из наследственной неразрешимости теории конечных графов (теоремаПустьР Е CJ-8.6.
7).k-местныйпредикатныйсимвол,k > 2.Тогдакласс Kz всех моделей сигнатуры (П 2 ) относительно элементарно определим в классе Ка всех моделей сигнатуры CJ формуламиQl(y);::::':у~ у,!В(у1, Yz) ;::::': YI ~ YZ,<t(y,, Yz) ~ P(YI' YZ, YZ, ... 'yz).ПустьклассKzfЕ CJ -k-местный функциональный символ,k ~ 2. Тогдаотносительно элементарно определим в классе Ка всех моделей сигнатуры CJ формуламиQl(x, у) ;::::': ~х ~ у,§ 8. б.
Неразрешимые теории339~(х, У1, У2) ;:=с У1 ~ У2,<t(x, Yl, У2) ;:=с f(YI, У2, У2, ... , У2) ~ х.=Действительно, пусть !JЛнемодель из класса К2,-чтоМ' ;:=с Мопределим модель !JЛ' сигнатуры с,, полагаяU {*}элемент(М, Р)предположим,*! 9Л'( a1,a2, ... ,ak ) ~ {принадлежит*,~а1,М.Наимножествеесли(а1,а2)ЕП9Л,в противном случае.g9Л' (а1, а2, ... , а1) ;:=с * для любого функционального символа g ЕЕ с,\{!}, Q9Л' ;:=с 0 для любого предикатного символа Q из с,. Легкопроверить, что формулы Ql(x,y), ~(х,у1,у2) и <t(x,y1,Y2) определяютмодель !JЛ в модели !JЛ' при подстановке вместо х параметраПредложение8.6.9.КлассEq2*·Dвсех конечных моделей теории Т1двух эквuвалентностей, т.
е. теории сигнатуры (ТJб, rJI) определенной аксиомой, утверждающей, что Т/О и Т/l являются отношениями эквивалентности, имеет наследственно неразрешимую теорию(в языке без равенства).Докажем это, установив, что класстельно элементарно определим в=Пусть !JЛ!J1= (N, Т/0, Т/1)(М, Р) ЕЕEq2Gfin(из теоремыотноси8.6. 7)EQ2.Gfin; определим по !JЛ алгебраическую системутак:N=MUP;rygt ={(х,х) 1 х Е N} U {(х, (х,у))U{((x,y),x)U{ ((х, у),ry'f = {(х, х)1(х,11х ЕМ, (х,у) Е P}Uх ЕМ, (х,у) Еz)) 1 хP}UЕМ, (х, у), (х,х Е N} U { ((х, у), (у, х))z)1ЕР};(х, у) ЕР}.ПолагаемQl(y) = ТJо(у,у); ~(У1,У2) = ТJо(У1,У2);<t(yi, У2)=~ТJо(У1, У2) Л3z13z2( ТJО(У1, z1)Л ТJо(У2, z2) Л Т/1 (z1,Тогда, как нетрудно проверить, формулы Ql, ~.<tотносительно элементарно определяют !JЛ в !J1 и, следовательно, Gfin вПредложение8.6.10.КлассLEqz2) ).Eq2 .Dвсех конечных моделей теории Т2 отношения линейного порядка и эквивалентности (сигнатуры (~,ТJ)) имеет наследственно неразрешимую теорию.340Гл.8.Разрешимые и неразрешимые теорииДокажем это, установив, что Е<12 относительно элементарно определим вLEq.Пусть 9Л = (М, Т/О, Т/1) Е Е<12; определим по 9Л алгебраическую систему !)1 = (N, ~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
