1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Ес­ли8Е s1 и~9ЕЕ s1 иs2 (~8(Лs,, ~(Лs2)) будет предложение(С4).ПустьЕ8 1 /\ 8288Еs2),то интерполирующим для(предложение~0).и предположим, что существует ин­s1,терполирующее предложение Х для((Лs1)/\82,~(Лs2)). Тогда из Лs1((Лs1)t>81/\ 81, ~(Лs2)) или дляt>82 получаем, что Хи Лs,будет интерполирующим предложением для (Лs1, ~(Лs2)), что невоз­можно.Если81 /\ 82Еs2иХинтерполирующее предложение-для (Лs1,~((Лs2)/\81)) или для (Лs1,~((Лs2)/\82)), то в силу~(Лs2/\ 81) t>~(Лs2) и ~(Лs2/\ 82) t>терполирующим предложением для (Лворечия с условием показывают, что(С5).

Пустьдля ((Лs,81 V 82 Еs,) /\ 81, ~(л s2)),и Х1, Х2((Л~(Лs2) формула Х будет ин­s,, ~ (Л s2)).Полученные проти­s U {81} Е S и s U {82} Е S.-интерполирующие предложенияs,) /\ 82, ~(л s2))соответственно. Тогда§ 5.4.Механизм совместности171Х1 V Х2 будет интерполирующим предложением для (ЛЕсли01 V 02 Е s2 и(Л s,, '((Л s2) !\ 01 )),Х1, Х2(Лs1,-s1, ·(Л s2)).интерполирующие предложения для·((Л s2)соответственно, то Х1s,, ·(Л s2))!\ 02))!\ Х2будет интерполирующим предложением для (Л(Сб). Пусть \:/х0 Еs2,с Е С и Хинтерполирующее предложе­-ние для (Л s,, ·((Л s2) !\ (0);:). Так как ·((Л s2) !\ (0);:) 1> ·(Л s2), тоХ является интерполирующим предложением для (Л s 1, • (Л s2)), чтоневозможно.

В случае \:/х0 Еначалаs1 аналогично получаем, что в качествеs1 U {(0);:}, а в качестве конца - s2.можно взятьs U {(0);:}(С7). Пусть со Е С не содержится в элементахs. Если :3х0 Е s1- интерполирующее предложение для ((Л s1) !\ (0)~, ·(Л s2)), тоиз аксиомы 12 и правила 3 ИПf 0 получаем, что :3уХ, будет интер­и Хполирующим предложением для (Лs1,·(Лs2)), где Х1 не содержитконстанту со, (Х1 )¼о = Х и у - переменная, не входящая в элементыs U {Х}.

В случае, когда :3х0 Е s2 и Х - интерполирующее предло­жение для (Л s1, ·((Л s2) !\ (0)~)), предложение \:/уХ1 будет интерпо­лирующим для (Л s,, ·(Л s2)). В самом деле, Л s1 1> \:/уХ, следует изЛs1 1> Х, так как со не входит в Л s1. Из Х 1> ·((Л s2) !\ (0)~) получаемs2) V Vy·(e)~. Если \:/уХ, 1> ·(Л s2) не имеет места, то су­ществует модель 1.2( множества {\:/уХ1, Л s2}. Из предыдущего получаем,что в 1.2( истинно Vy·(e)~.

Это противоречит 1.2( F Л s2 и :3х0 Е s2.\:/уХ 1 1> ·(Л(С9). Пусть с' Е С не входит в элементытерполирующим предложением для ((Лs.Если Х является ин­... , сп), ·(Л s2)),s1, ·(Л s2)). Пусть{со ;:;:с; f(c,, ... ,Cn),(0)1(c,, ... ,cп)} ~ s. Если (0)f(с,, ... ,сп) Е s1 и Х интерполирующее предложение для ((Л s1) !\ (0)~, ·(Л s2)), то ин­s,)!\с';:;::; !(с,,то Х будет интерполирующим предложением для (Лтерполирующим для ((Лs,), ·(Лs2)) будет предложение Х в случаесо ;:;:с;f(c1, ·:·, сп) Е s1 и предложение ·со ;:;:с; f(c1, ... , сп) V Х в случаеСО;:;::; f(c1, ... , сп) Е s2. Если (0)f(с,, ... ,сп) Е s2 и Х - интерполирующеепредложение для (Л s1, ·((Л s2) !\ (0);:0 )), то интерполирующим для(Л s,, '(Л s2)) будет предложение Х в случае со ;:;::; f(c1, ...

, сп) Е s2 ипредложение со ;:;:с;f (с,, ... , сп)!\ ХИтак, мы показали, чтов случае со ;:;:с; !(с,,... , сп)S - механизм совместности. Если{ Ф, 'Ф} принадлежало бы S. Поимело места, то множество5.4.3множество{ Ф,Еs,.бы а) нетеореме·Ф} имело бы модель, что в силу следствияпротиворечило бы условию Ф4.5.81> Ф.Для того чтобы доказать б), нужно в определенииSзаменить слова<<предложение,> на <<предложение без равенства» и потребовать, чтобыне имело места ни 1> ·(Лs1),ни 1> ·(Лs2).Тогда при проверке (С!)случаи {0, ·е} ~ s 1 и {0, ·е} ~ s 2 невозможны.

Остальная проверкаусловий(Cl)-(C7)та же, что и в а). Следовательно,S -механизмГл.1725.Теория моделейсовместности без равенства. Затем применяем теоремутеоремы5.4.4вместоО5.4.3.Если в Ф или в Ф входит равенство, то в теореме5.4.7 б)потребо­вать, чтобы равенство входило в Х только тогда, когда оно входит вФ и Ф, нельзя (см. упражнениеприменим теорему5.4. 71).В оставшейся части параграфа мыдля характеризации предложений, сохраняю­щих свою истинность при переходе к гомоморфным образам.Определение. Если21 -алгебраическая система сигнатуры Е, тоотношение Е на множестве А назовем конгруэнтностью наоно является эквивалентностью на А и для любых а1,21,если...

, ап, Ь1, ...... ,ЬпЕА,следует (Ь1,rER, fEF, µ(r)=µ(f)=n из (a1, ... ,an)E112t(r)... ,Ьп) Е v2l(r) и из (а1,Ь1) Е Е, ... ,(ап,Ьп) ЕЕ следует(112t(f)(a1, ... ,an),112t(f)(Ь1, ... ,Ьn)) ЕЕ. Если Е - конгруэнтность насистеме 21 сигнатуры Е, то определим новую систему 21/ Е сигнатурыЕ, которую назовем факторсuстемой системы 21 по Е. Носительсистемы 21/ Е состоит из классов эквивалентности аЕ = {Ь 1 (Ь, а) ЕЕ}.Интерпретация v2l/ Е определяется так:(aiE, ... , апЕ) Е1/Ql/ Е (f)(a1E,1/Ql/ Е (r){==>(а1, ...

, ап) Е 112t(r) (r Е R),... , апЕ) = 11Ql(f)(a1, ... , ап)Е (! Е F).Проверку корректности этого определения, а также доказательствоследующего простого предложения мы оставляем читателю в качествеупражнения.Предложение5.4.8.а). Пусть Ф-предложение сигнатуры Е,а Ф' получается из Ф заменой подформулti ;:::: t2 на E(ti, t2), где Е 21 - система сигнатурыЕ, Е Е R' и v2l - конгруэнтность на 21 ~ Е, тосимвол отношения, не входящий вЕ' ;;:;>б). Если Е-R.Есликонгруэнтность на системе21,то отображение,сопоставляющее элементу а Е А элемент аЕ, будет гомоморфиз­мом21на21/ Е.ОФормулу Ф назовем положительной, если она не содержит импли­кации и все вхождения в Ф символов отношений и равенства являютсяположительными.

Будем говорить, что предложение Ф сигнатуры Есохраняется при гомоморфuзмах относительно предложения Ф сиг­натуры Е, если из истинности Фистинность Ф-./\Ф на системе21сигнатуры Е следуетФ на любом ее rомоморфном образе.Механизм совместности§ 5.4.Теорема5.4.9.Пусть Фи 1]! -173предложения сигнатуры Е и пред­ложение 1]! -. ·ф недоказуемо. Для того чтобы Ф сохранялось пригомоморфизмах относительно предложения 1]!, необходимо и доста­точно, чтобы Ф было эквивалентно относительно 1]! некоторомуположительному предложению Х (т. е.

1]! [> (Ф-. Х)До к аз ат ель ст в о.Необходимость. Так как Ф/\(Х-. Ф)).и1]! содержатконечное число символов, то можно считать сигнатуру Еконечной. Предположим сначала, чтоF= lo.= (R, F, µ)Обозначим через е конъ­юнкцию предложений\fv1 ... \fvпCr(v1, ... , Vn) V r'(v1, ... , Vn)), r Е R, µ(r) = п,и предложения\fv1\fv2("E(v1,v2) V E'(v1,v2)),гдеr' (r Е R), Е и Е' - попарно различные символы, не принадле­R. Обозначим через Л предложение сигнатуры, содержащейлишь символы из R U { Е} и не содержащее импликации, истинностькоторого на системе 21 равносильна тому, что v'lJ.(E) - конгруэнтностьна 21 r Е.

Пусть Фо и Wo получаются соответственно из Ф и 1]! заменойжащиевсех подформул вида х ~ у на Е(х, у). Пусть ФЬ,соответственно из Фо,штрихованные. Если на системетоwbи Л' получаютсяи Л заменой всех предикатных символов наWo21истинно предложение е 1\ Л/\Л',v'21(r) ~ v'21(r') для r Е R и v'21(E) ~ v'21(E'), поэтому отображе­ние, сопоставляющее элементу аЕ элемент аЕ', будет гомоморфизмомr=(21 E)/v'21(E) на 211/v'21(E'), где 211(А, v'21 1 ) - система сигнатурыЕ, для которой v'21 1 (r) = v'21(r') (r Е R). Отсюда, используя следствие4.5.8,предложение5.4.8 а)и условие теоремы, получаем, что имеетместоWo 1\ Фо 1\ лПредположим, что t> ·1]! 0символыгде81r'наrдляrЕ[>·wь V ·е V ·л' V ФЬ.V ·е V ·Л' V ФЬ.

Заменив в доказательствеRи Е' на Е, получаемполучается из е заменойчто t>81, следовательно,r'наr·wo V ·л V Фодля-rЕRи Е' на Е. Ясно,тождественно истинноепредложение. Отсюда, используя тот факт, что Л истинно на системах21, у которых отношение v'21(E) является равенством, получаем, что1]! -.

Ф также тождественно истинно. Поэтому в качестве Х можновзять предложениеV ·е V ·Л' V ФЬ не·(wo 1\ Фо 1\ Л) также не доказуемо, так каксилу того, что Л истинно на системах 21, у кото-\fviV[ ~ V[. Пусть теперь ·1],ьдоказуемо. Предложениев противном случае вГл.174Теория моделей5.рых v 21 (E) является равенством, предложение Ф---+ ·ф также было бытождественно истинным, что противоречит условию о его недоказуемо­сти. Тогда по теореме5.4.

7, б)существует интерполирующее предложе­ние Хо, не содержащее равенства, для которого имеют место условияФа/\ Фа/\ Лt>Хо, Хоt>v ·e v ·Л' v ФЬ, Е+(Хо) ~ RU {Е}, а так­n Е-('ФЬ v ·е v ·л' v ФЬ) = 0. Сле­·ФЬже Е-(Хо) ~ Е-(Фо /\Фа/\ Л)довательно, Хо-положительное предложение сигнатуры Е1, котораякроме символов Е имеет лишь символ Е. Заменяя в выводе символыr' на r для r Е R и Е' на Е, получаем Хо t> ·Фо V ·01 V ·л V Фо.Так как t>01, то Хо t> ·Фо V ·л V Фо. Таким образом, мы полу­чили Фо, Лt>стемах ~.у которых отношение v 21 (E)Фt>(Ф---+ Х)/\(Фо---+Хо)/\(Хо---+Фо). Так как Л истинно на си­является равенством, то(Х---+ Ф) для положительного предложения Х, получен­ного из Хо заменой подформул вида Е(х, у) на х ~ у.Пусть теперь Е = (R, {!1, ...

, fm}, µ). Рассмотрим сигнатуру Е' =(R U {F1, ... , Fm}, 0, µ'), где F1, ... , Fm - попарно различные сим­волы, не принадлежащие R, µ'(r) = µ(r) (r Е R) и µ'(Fi) = µ(fi) + 1,i Е { 1, ... , m}. Пусть Фо - предложение, выражающее в системахсигнатуры Е', что отношения F 1 , ••• , Fm являются функциями 1). Пусть=-Ф1, Ф1предложения сигнатуры Е, находящиеся в приведенной н. ф.,эквивалентные соответственно предложениям Ф, Ф. Пусть Ф 2 , Ф 2 по­лучаются соответственно из Ф1, Ф1 заменой атомных подформул видау~fi(x1, ...

, хп), fi(x1, ... , хп)~ у наFi(x,, ... , Хп, у).Ясно, что еслиФ сохраняется при гомоморфизмах относительно Ф, то Ф 2 сохраняетсяпри гомоморфизмах относительно Ф 0 /\ Ф 2 . Так как Е' не содержитсимволов функций, то по только что доказанному существует положи­тельное предложение Х1 сигнатуры Е', для которого имеет местоИспользуя следствиегде Х-заменой4.5.8,получаем, что тогда справедливоположительное предложение сигнатуры Е, полученное из Х1Fi(x1, ... ,Хп+1) на Xn+l ~ J(x1, ... ,хп)-Достаточность условия теоремы получаетсяиз следующих двухфактов, которые проверяются непосредственно индукцией по длине Х.1)То есть Фо является конъюнкцией предложений'v'x1 ...

'v'xni 'v'y'v'z((Fi(X1, ... , Xn,,->(у:=:::z)Лу) Л'v'x1 ... 'v'xniЭyF;(x1, ... , Xn,,у),F(x1, ... , Xni, z))->i Е {!, ... , m}, n;= µ(!;).Счетная однородность и универсальность§ 5.5.1). Если h -гомоморфизм17521 на ~ и Х(х1, ... , хп) -формула, несодержащая отрицания и импликации, то2).Положительная формула Х эквивалентна формуле Х1, не содер-жащей отрицания и импликации.ОУпражнения1.Используяготеоремулинейногодоказать,5.4.6,21порядкабезчтодляпоследнеголюбогоэлементасчетно­существу­ет такое собственное элементарное расширение ~ (т. е.иА-/-В),чтоявляется21начальнымотрезком~21-<(т. е.~из(Ь, а) Е v'В ( ~) и а Е А следует Ь Е А).

Характеристики

Список файлов книги