1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 65
Текст из файла (страница 65)
, УkФ 1 +kФ 2 ), а в каlфkФ - последовательность фl , .•. , фkФI , фl , •.. , фkФ2 .честве ф , ... ,Пусть теперь Ф= :3х а(х, х1, ... , Xn),1122Зафиксируем некоторое взаимно однозначное отображениед : { 1, .. , , 2k" } -+ Р ({ 1, ... , ka}),Рассмотрим формулыei = лajл!\~jа,jE{l, ... ,ka}jEб(i)j(/.б(i)Нетрудно проверить следующие свойства:для любых1)f, f 1, ... , f nЕl-prod AiD-prodQti 'p=a(Df,Df1, ... ,Dfп){=::}выполнено21 /D 'p=Ф 1 (S1/D, ... ,S2ka/D),= {i I Qti F ej(fi, J,i, ... 'fпi)}, 1 ~ j ~ 2ka;2) C>8i-+ ~ej, i,j Е {1, ...
,2k"}, i -=f. j;3) С>81 V ... V 82ka.где SjПолагаем kФ= 2k".Эz1 ... ЭzkФ( (Обозначим через Ф* (у,, ... , УkФ) формулу/\zin Zj~О!\ (z, U ... u Zkф) ~ 1 ) лl~i<j~kф=и пусть фi:3x8i, i Е { 1, ... , kФ }. Докажем свойство (8.9). ПустьF Ф(Df1, ...
,Dfn).Тогда найдется f Е l-prodAi, для коD-prodQti F a(Df,Df1, ... ,Dfn), По свойству 1)имеем 21 / D 'р= Ф'(l(! D, ... , 1,Ф/ D) дляD-prodQtiторого выполнено1;= {i 1 !2ti 'F= ej(fi, f1i, ... , fпi)},1 ~ j ~ kф.Тогдаlj с; lj = {i I QtiВ силу свойствl( U ... U ЦФ=F Фj(f1i, ... , fпi)},3) имеем Д n 11=1 ~ j ~ kф.2) и121, 1 ~ i < j ~ kФ, иl. Так как отображение D: 21 -+ 21 / D является гомо-Гл.330Разрешимые и неразрешимые теории8.морфизмом, то в 21 / D истинны Ц/ Dдляi,jЕn Ii/ D ~ Ц/ D,Ц/ Dn I1/D~ О{1, ... , kФ}, i -j. j, и I[ID U ...
U 1,Ф/D ~ 1. Таким образом,(8.10)Пусть теперь выполнено (8.10). Тогда найдутся такие Ц ~что I\(Цnl;)ED для i,jE{l, ... ,kф}, i-j.j,I \ Щ \ Ii) Е D и выполнено~ kФ,ED,21 /D р Ф'Щ/D, ... , Цф/D).(8.11)3) вытекает I1 U ... U IkФ = I. ПоэтомуI, 1 ~ i ~ kФ, что выполнены условия:4) Ц'/D = Ц/D для всех i Е {1, ... ,kФ};найдутся такие Ц' ~Из условия~I, 1 ~ iI(u ... uцф5) I(' U ...
U Ilф= I,6) Ц' ~ Ii для всех i Е {1, ... ,kФ};7) Ц' n I/ = 0 для всех i,j Е {1, ... , kФ}, i -1- j.В силу условий 5), 6), 7) и 2) найдется такой f Е l-prod Ai,всех j Е { 1, ... , kФ} выполненоI;' = {iПоэтому из условийчто для1~i F ej(fi,f1i, ... ,fni)}.и4), (8.11)1)получаемD-prod~i pa(Df,D/1, ... ,Dfn).Следовательно,D-prod~iСледствие8.5.2.p=Ф(D/1,о... ,Dfn).Если алгебраические системы ~1 • ••• , ~n сигнатуры Е имеют разрешимые теории, то декартово произведение~1 х...х ~n также имеет разрешимую теорию.До к аз ат ел ь ст в о.веркаусловия~1 х2{I, •. ,n} р Ф*(I1,разрешимости...Попредыдущемух ~n р Фсводитсяпредложениюкпроверкепро-условия...
,IkФ) для некоторых I,, ... ,IkФ ~ {1, ... ,п}. ИзTh(~i), ... , Th(~n) получаем, что I1, ... , IkФтеорийэффективно находятся по Ф. Так как 2{I, ... ,n} -конечная система, тосуществует алгоритм проверки истинности формул Ф* (I1,... , Ikф)этой системе.наОБулева алгебра ~ называется атомной, если для любого а Е А либоа= О, либо в~ найдется атом (см.Лемма8.5.3.123.ры, то~=Если ~ и123 -§ 2.3)Ь, для которого Ь ~ а.бесконечные атомные булевы алгеб§ 8.5.
Теории декартовых произведенийДо к аз ат ель ст в о. Воспользуемся следствиемДляiЕ{1, ...,п} в качествеFi(n)3315.1.2.возьмем все такиеПусть п ЕfЕw.P(Ql,123),которые удовлетворяют следующим условиям:l) f - изоморфное вложение конечной подалгебры Qlf ~ Q( в 123;2) если а Е At содержит k < 2п-i атомов в Ql, то f(a) содержитk атомов в 123;3) если а Е А1 содержит ~ 2п-i атомов в Ql, то f(a) содержит~ 2п-i атомов в 123.Так как отображение, состоящее из единственной пары нулей соответствующих алгебр, принадлежит всем множествамFi(n),то все этимножества непустые.Покажем, что выполнено условиеfЕFi(n), 1 ~ i <*)следствия5.1.2.Пусть а Е А,п.
Так как А1 конечно, то найдутся такие попарно... , ak Е At, что а, U ... U ak = 1 и для любогоAj и любого i Е {1, ... , k} выполняется Ь n ai = О или ai ~ Ь. Пустьа} = ai n а, а;= ai n а, i Е { 1, ... , k }. В силу свойств 1)-3) для каждогоразличные элементы а1,Ь Еi Е { 1, ... , k} найдутся такие Ь}, Ь~ Е В, что выполнены условия:4) Ь!i n Ь1,2 = О ' f (а.)= Ь 1,1 U Ь i2 '•.,5) для каждого j Е {1, 2}, если а{ содержит т < 2п-i-l атомов в Ql,то Ь{ содержит т атомов в 123;6) для каждого j Е { l, 2}, если а{ содержит ~ 2п-i- l атомов в Ql,то lJi содержит ~ 2п-i-l атомов в 123.Нетрудно понять, что для любого элемента е алгебры Ql( а,, ... , ak, а)найдутся такие s(e),r(e) ~ {l, ...
,k}, чтое=UСледовательно, а Еdomg,U а;.а} UiEs(e)и в силуiEr(e)4), f~g={(UaluUa;,UьJuUь;)•EsiEr~Евg,1гдеs.r~{1 ..... k}}-iErТак как пересечение различных элементов вида а{ (вида ь{) в Q1 (в 123)равно нулю, то из условий 1)-6) вытекает g Е Fн1 (п).Случай Ь Е В в условии *) рассматривается аналогично, если вместо f рассмотреть 1- 1•DСледствие8.5.4.Теория любой атомной булевой алгебры Q1 разрешима.До к аз ат ель ст в о. Так как для любой конечной алгебраическойсистемы конечной сигнатуры существует алгоритм проверки истинности в ней предложений этой сигнатуры, то теория любой конечной332Гл.8.Разрешимые и неразрешимые теориибулевой алгебры разрешима. Так как условие атомности булевой алгебры записывается одним предложением, а условие бесконечностизаписывается бесконечным множеством аксиомто теория бесконечных атомных булевых алгебр перечислима.
В силу предыдущей леммы теория бесконечных атомных булевых алгебрполна. Из этих фактов в силу предложения7.5.8получаем требуемоеутверждение.СледствиеО8.5.5.Еслиалгебраическая система и2t -разрешима, то для любого непустого2t 1 разрешима.ITh(2t)теория декартовой степениДо к аз ат ель ст в о. Пусть Ф - предложение сигнатуры 2t. Применяя предложение 8.5.1, найдем Ф* (У1, ... , УkФ) и Ф 1 , •.• , фkФ, длякоторых2( 1гдеFф{=:::::>21F Ф*(I1, ...
,Ikф),(8.12)Ij = {i Е J l 2t р Фi}. Так как Ij Е {.0,J}, то21F Ф*(J,, ... ,JkФ){=:::::>21F Ф*(с?, ... , сfФ),(8.13)где cf Е {О, 1}. Если Th(2t) разрешима, то существует алгоритм, находящий по Ф константы с;, i Е {1, ... ,kФ}- Из (8.12), (8.13), атомностибулевой алгебры 21 и предыдущего следствия получаем тогда разрешимость Th(2t 1 ).оВ заключение отметим, что разрешимы теории всех булевых алгебри любой булевой алгебры. Из последнего результата и предложения8.5.1вытекает обобщение следствия8.5.5:если2t -алгебраическаясистема с разрешимой теорией, то любая ее фильтрованная степень 2t Dимеет разрешимую теорию.§ 8.6.Неразрешимые теорииВ настоящем параграфе будет указан один общий метод доказательства неразрешимости элементарных теорийэлементарной определимости--метод относительнойи будут даны примеры примененийэтого метода.Элементарную теорию Т назовем наследственно неразрешимой,если любая ее подтеория То ~ Т является неразрешимой.§ 8.6.
Неразрешимые теории333Заметим, что если Т наследственно неразрешима и То ~ Т-подтеория, то и То наследственно неразрешима. В терминах классовмоделей это свойство может быть сформулировано так: если Ко ~ К1,где Ко и К1-классы моделей одной и той же сигнатуры, инаследственно неразрешима, то иПусть Ко-Th(K1)Th(Ko)наследственно неразрешима.класс алгебраических систем (чисто предикатной конечной) сигнатуры ио=(Р0п 0 ,••• ,F'/?),Ki -класс алгебраическихсистем сигнатуры и1. Будем говорить, что класс Ко относительноэлементарно определим в классе Ki, если существуют такие формулыQt(x; у), ~:в (х; у-1; 1l2), ~о (х; у 1 ; ...
; yno ), ... , ~k (х; у 1 ; ... ; Wk) сигнатуры и1(здесь и далее х = (х1, ... , хп), yi = (yf, ... , У:ТJ), что для любой алгебраической системы 9Л Е Ко найдутся алгебраическая системаи элементы а1, ... , ап ЕIJ1Е К1удовлетворяющие условиям:N,( 1) множество L = {Ь I Б Е Nm, IJ1 F Qt(a, Ь)} непусто;(2) формула ~:Б(а; у 1 ; у2 ) задает конгруэнтность 'Г/ на алгебраической системе ~ сигнатуры ио, основное множество которой есть L,а предикаты определены формулами ~i(a; у 1 ; ...
; yn;) (т. е. 11.1:(Pi) == {(ь1. ... 'ь) 1Бj Е L, j=1, ... 'ni'1)1F ~i ( а; ь1; ... ;ьп;)' i ~ k});(3) факторсистема ~/'Г/ изоморфна 9Л.Если формулы Qt, ~:в,~.... , ~kудовлетворяют сформулированнымвыше условиям, то будем говорить, что они относительно элементарно определяют 9Л вIJ1(класс Ко в классе К1).Если класс Ко относительно элементарно определим в классе К1,то обозначать это будем так: Ко ~RED К1.Отметим следующие простые свойства введенного понятия:1.
Если Кб~ Ко, К1 ~ к; и Ко ~RED К1, то Кб ~RED к;.2. Если Ко ~RED К1 и К1 ~RED К2, то Ко ~RED Kz.Основой метода доказательства неразрешимости - методательно элементарной определимости - является следующаяТеорема8.6.t.Если элементарная теорияTh(Ko)относикласса Конаследственно неразрешима и Ко ~RED К1, то и теорияTh(K1)класса К1 также наследственно неразрешима.До к аз ат ель ст в о. Пусть формулы Qt, ~:в,~элементарно определяют класс Ко в К1 ирешимаTh(Ko).... , ~kотносительнонаследственно нераз..Для любой формулы ср(у1,им формулу...
, Ys) сигнатуры ио эффективно постро-zp(x; у 1 ; ••• ; '[/) сигнатуры а1 по следующим правилам:если ср(у1, ... , Ys) есть Yi ~ Yj, то -zp(x; у 1 ; ... ; у8 )= ~:Б(х; yi; yj);334Гл.если1.р(у1, ... , Ys)= ~- (-x.-yli.~'l,Разрешимые и неразрешимые теории8.'естьPi (У1" ... , YiпJ,то"ip(x; 1J1; ... ;"JJ8)·-yln;)·, ••• ,'если1.p(y1, ... ,ys) есть <po(Yl,···,Ys)т1.p1(Yl,···,Ys) (тЕ {Л,V,-+}),... ;1?) = ("ij50(x; у\ ...
;1J8)т"ij5 1 (х; у 1 ; ... ; JJ8));если 1.p(y1, ... ,ys) есть ...,'Ф(Yl,···,Ys), то "ip(x;y 1; ... ;y8 ) =......о/1,(х·' -у\.' ••• .' -ys)·'то "ip(x; у\=если1.p(y1, ... ,ys) есть 3Ys+1'l/J(y1, ... ,ys,Ys+1) (\:/Уs+1'Ф(У1, .. .. · ·, Ys, Ys+I )), ТО "ip(x; у 1 ; ... ; У8 ) = 3yf+I ... 3y~+I (21.(х; ys+I) Л ф(х; у 1 ; ... ;... y8;ys+l)) (\:/yf+I ...
\:/y~+\(21.(x;ys+I)-+ ф(x;yl; ... ;y8;ys+I))).Пусть= f>(x1, ... , xn) -f>(x)следующая формула:31}21.(х; у) л Vy°vy 1vy2[ ( Л 21.(х; yi) -.. IJ3(x; у°; у°)) л·~2л(IJ3(x;y°;y 1 )-+ IJ3(x;y 1;1}°)) л (1J3(х;у°;у 1 )лЛIJ3(x;yl;y2))-+ IJ3(x;y°;y2))] Л л[vyl ... vyn'vzl ...i~k... vzni ( ( (\(21.(х; у1 ) Л 21.(х; z1 ) Л IJ3(x; у1 ; z1 )) ЛJ=IЛ(ti (х; yl; ... ; уп'))где \/у (3у) означает \:/у1... \:/ym-+ (ti (х; :zl; ... ;(3у1:zn;))] '... 3ym). Формула f> выражает( 1) и (2) изтребования на <<параметры)) х удовлетворять условиямопределения относительной элементарной определимости.Длялюбогопредложения<рсигнатурыаопусть<р*= \:/х1 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
