1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 29
Текст из файла (страница 29)
Тогда по теоремеФ1, ... , Фп----, А, то4.4.2 дляследует 12{F Ф['У]4.5.6для любых системмножество Х U ГФ} не имеет моденекоторых Ф1, ... , Фп Е Х секвенцияf- Ф доказуема и из теоремы 4.5.6 получаем достаточность. DУпражненияl.2.Доказать утверждения б) и г) предложенияДоказать, чтоG 1>4.5. l.Ф тогда и только тогда, когда существует такаяпоследовательность Фо, ... , Фп формул ИПf, что Фпкаждого i ~ n формула Фi удовлетворяет одному из=Ф и дляследующихусловий:l) фi доказуема в ипf,2) Фi принадлежит G,3) Фi получается из некоторых§ 4.6.Ф1 ,j < i,по правилуl.Чистое исчисление предикатовВ этом параграфе будет определено исчисление ИПЧ, которое называется чистым исчислен.ием предикатов, и будет доказана некоторая«универсальность» этого исчисления (теорема4.6.2).Гл.140Исчисление предикатов4.Рассмотрим сигнатуру Е*=(R*, F*, µ*)со следующими свойст-вами:l) F* = 0, R* = {r~ k, т Е w};2) µ*(r~) = k для любого m Е w и k Е w.1Формулами ИПЧ будут формулы сигнатуры Е*, не содержащиесимвола равенства.
Секвенции ИПЧ - это секвенции ипЕ: все формулы в которых являются формулами ИПЧ.Аксиомами ИПЧ будут только секвенции вида Ф1-- Ф; правила. Доказательство в ИПЧ определяется такконечно, под формулами, секвенциями и аксиомавывода те же, что у ИПже, как в ипЕ* -Е*ми теперь понимаются формулы, секвенции и аксиомы ИПЧ. Легкопроверить, что все результаты висключением предложения4.1.6,§ 4.
l -4.3,относящиеся к ИПпредложенияи теоремы4.3.2Е*, за4.1. 7,справедливы также для ИПЧ, так как в их доказательствах не используются аксиомы2), 3).Сейчас мы покажем, что результаты§4.4такжераспространяются на ИПЧ. На самом деле имеет местоТеорема 4.6.1. Исчисление ипЕ* является консервативным расширением исчисления ИПЧ.До к аз ат ел ь ст в о.Множество Х предложений ИПЧ называется совместным в ИПЧ, если для любых Ф1, ... , Фп Е Х секвенцияФ1, ... , Фп1--iне доказуема в ИПЧ. Покажем, что любое совместноев ИПЧ множество формул ИПЧ имеет модель. Доказательство этогоутверждения мало чем отличается от доказательства теоремыПостроение множестваXw -4.4.2.то же самое. (При этом под формулами и доказательствами, конечно, понимаются формулы и доказательства в ИПЧ).
Доказательства свойств а)-и) дляXwте же самые.Свойство к) в данном случае не требуется. Отношениена С не,....,определяется и носителем системы Qt является само множество С.Доказательство эквивалентностииз свойств а)-и) проводится еще проще, чем в теореме4.4.2,так какотпадает необходимость переходить к представителям классов эквивалентности по отношению,...., и нет атомарных формул видаЕсли теперьS= \J.11, ... , Фп 1--квенцией ИПЧ, то по теоремеФ-4.1.5теорема ИПсеквенцияЕ*Sтинна. Тогда по указанному выше {Ф 1, ... , Фn, ~Ф}в ИПЧ множество, следовательно, секвенциязуема в ИПЧ.
По правилу9получаем,t1~t2.являющаяся се-тождественно ис-не совместное\J.11, •.. , Фn, ~Ф 1-доказуемость S в ИПЧ.iдокаОЯсно, что из результатов § 4.4 и теоремы 4.6. l следует справедливость всех теорем, полученных из теорем § 4.4 заменой ИПЕ на ИПЧ.§ 4. 6.Чистое исчисление предикатов141Конец этого параграфа мы посвятим одному факту, который показывает, что вопросы о доказуемости в различных ИПЕ <•сводятся,> к вопросам о доказуемости в ИПЧ. Переходим к точным формулировкам.Зафиксируем предикатный символОпределение. Пусть ЕroЕ= (R, F, µ) -тура. Инъективное отображение а:R*,для которого щrо)= 2.конечная или счетная сигнаR U F ---t R*называется интерпретацией Е в Е*, если выполняются следующие условия:а)rotf.
a(R U F);б) еслив) еслиsfµ*(as) = µ(s);ЕR,тоЕF,то µ*(а.!)=µ(!)+1.Для интерпретации а сигнатуры Е в Е* определим отображение а.*множества формул сигнатуры Е, находящихся в приведенной нормальной форме, в множество формул ИПЧ по индукции. Если Фформула видах~ у, то а.*(Ф)= r0 (x,y);-атомнаяесли Ф- атомная формулавида s(x,, ... , хп), то а.*Ф = as(x,, ... , Хп); если Ф - атомная формулаf(x,, ... , Хп) или f(x,, ... , Хп) ~ у, то а*Ф = af(x,, ... , Хп, у);~w, Ф = Qx\JJ или Ф = Ф1тФ2, где Q Е {V,3}, т Е {/\, V,---t},то а*Ф равна ~а*Ф, Qxa*\JJ или а*Ф,та*Ф2 соответственно.Если а. интерпретация Е в Е*, Ф Е F(E) находится в приведенной н.ф. и Е(Ф) = ({so, ... ,sk},{fo, ...
,fm},µ 1 ), то через а.оФвида у~если Ф =обозначим конъюнкцию следующих предложений сигнатуры Е*, гдеп1= µ'(s 1 ),li = µ 1 (fi),x,y,z,x1, ... ,xn,Y1, ... ,yn ные переменные 1):попарно различ1) \ix1 ... \ixn; Vy, ... 'v'Yn; ((ro(x,, у,)/\ .... . . /\ ro (Xn;, Уп;) /\ as1 ( Х 1, .•. , Xn;)) ---t as1 (у,, ... , Уп;)), j~k;2) \ixo ... \ixz,\iyo ...
\iyz, ((ro(xo, Уо) /\ ...... /\ ro(xz" yz,) /\ afi(xo, ... , xzJ) ---t a.fi(Yo, ... , yzJ), i~ т;3) Vx, ... \ixz,3yafi(x,, ... ,xz"y), i ~ т;4) Vx, ... \ixz, \iy\iz((afi(x,, ... , xz,, у)/\/\afi(x,, ... ,xz,,z)) ---t ro(y,z)), i~ т;5) \ixro(x, х);6) \ix\iy(ro(x, у) ---t ro(Y, х));7) \ix\iy\iz((ro(x, у)/\ ro(y, z)) ---t ro(x, z)).Ясно, что из условия2)на сигнатуру Е* следует, что для любойконечной или счетной сигнатуры Е существует интерпретация Е в Е*.1) Предложение а 0 Ф зависит только от сигнатуры ~(Ф), а его истинность наалгебраической системе Qt равносильна тому, что v'д(ro) является эквивалентностью, предикаты vш (asj) и vш (af;) не <•различают» vш (rо)-эквивалентныеэлементы, а отношения v!}((af;) определяют на классах vш(rо)-эквивалентныхэлементов l;-местные операции.Гл.142Теорема= Ф,Ф'4.Исчисление предикатовПусть Ф4.6.2.формула исчисления-Ф' находится в приведенной н.
ф. и о:предикатов,интерпретация-сигнатуры Е( Ф') в Е*. Тогда Ф доказуема в исчислении предикатовтогда и только тогда, когда о:оФ'---.о:*Ф' доказуема в ИПЧ.Доказательство. В силу теорем4.1.5, 4.4.3и4.6.10достаточно проверить, что тождественная истинность Ф' равносильна тождественной истинности о: 0 Ф'---. о:*Ф'. Для любой системы Qt сигнатуры= ({so, ... , sk}, {!о, ... , fm}, µ) определим систему o:szt сигнатуры= ({ro, o:so, ... , o:sk, o:fo, ... , o:fm}, 0, о:µ)~ Е* следующим образом:Е(Ф')о:Еа) о:А= А;б) (а, Ь) Е v°' 21 (ro) ~ а= Ь;в) v°' 21 (o:s1 ) = v 21 (s 1 ), j ~ k;r) v°' 21 (o:fi)д)v°' 21 (o:fi)= v 21 (fi), i ~ т, µ(fi) > О;= {v 21 (fi)}, i ~ т, µ(fi) = О.Индукцией по длине формулы Ф сигнатуры Е( Ф'), находящейся в приведенной н.
ф., легко проверить, что для любой интерпретации 'У в Асвободных переменных Ф имеет местоВ частности, для любой т FV(Ф')---. А имеемQ(Очевидно, что вo:sztF ~Ф'['У]===;,o:sztF ~о:*Ф'["f].истинно о:оФ', поэтому изиз тождественной истинности о: 0 Ф'---.(4.8)(4.8) получаем, чтоо:*Ф' следует тождественнаяистинность Ф'.Пусть о: 0 Ф'---.о:*Ф' не тождественно истинна, тогда для некоторойсистемы Qt0 сигнатуры о:Е и интерпретации 'Уа в Ао свободных переменных Ф' имеемF о:оФ'предложенийиз определения о:оФ' получаем, что отношениеszto5)-7) ииsztoF ~о:*Ф'['Уо].Из истинности вsztov 210 ( r0 ) определяет на Ао эквивалентность. Класс эквивалентности поотношению v 210 (r0 ), содержащий а Е Ао, будем обозначать через а.Определим систему 'Во сигнатуры Е( Ф') следующим образом:а) Во={а I а Е Ао};б) (а1, ... ап) Е v'E 0 (sj) ~ (а1, ...
,ап) Е v 210 (o:sj), j ~ k;в) (a1, ... ,an+1) Е v'E 0 (1i) ~ (а1, ... ,ап+1) Е v 210 (o:fi), i ~ Щµ(fi) = n > О;r) а= v'E 0 (Ji) ~ а Е v210 (o:fi), i ~ т, µ(fi)Из истинности наszto= О.конъюнктивных членов 1) и 2) предложения о:оФ'следует корректность этих определений. Из истинности предложений§ 4.6.Чистое исчисление предикатов1433) и 4) следует, что v'13°(Ji), i ~ т, - операции на В0 .
Индукцией по длине формулы Ф(х1, ... , хп) сигнатуры Е( Ф'), находящейсяв приведенной н. ф., легко проверить, что для любых а1,. .. , ап Е АосправедливоОтсюда получаем, чтоФ'-F ~Ф'[::Уо]230где ::Уо(х)= ,о(х),х Е FV(Ф'), т. е.не тождественно истинная формула.Как будет показано вО§ 7.5, существуют эффективно заданные множества формул, для которых нет эффективной процедуры (алгоритма),позволяющей для любойформулы данногомножествазаконечноечисло шагов устанавливать, является ли она тождественно истиннойформулой или нет.
Однако теорема Гёделя о полноте дает нам возможность по любой эффективно заданной сигнатуре Е построить эффективный процесс (машину) мг., который перечисляет все тождественноистинные формулы сигнатуры Е, т. е. мг. в процессе работы выдаеттакие слова Ф 0 , .•• , Фп,... ,что {Фа,... , Фп, ... }есть множество всехтождественно истинных формул сигнатуры Е.
Этот процесс состоитв выписывании конечных последовательностей секвенций ИПЕ и выдает слово Ф тогда, когда выписанная последовательность есть линейноедоказательство секвенции f- Ф в ИПЕ. Так как для любого эффективнозаданного множества формул Х переход от формулы Ф Е Х к формулеФ'=Фв приведенной н. ф., а затем к формуле о: 0 Ф' ----+ о:*Ф' можносделать эффективным, то теорема4.6.2показывает, что для того, чтобыуметь перечислять все тождественно истинные формулы из любого эффективно заданного множества формул, достаточно построить машинуМ, перечисляющую теоремы ИПЧ.Упражнение1.ПустьJ -исчисление, полученное добавлением к ИПЧ символаравенства и следующих аксиом:а)f-х ~ х;б) х ~ у, (Р);, f--- (Р)~, где Р- атомная формулаПоказать, что в J доказуемы все теоремы ипЕ*.сигнатуры Е*.Глава5ТЕОРИЯ МОДЕЛЕЙЭлементарная эквивалентность§ 5.1.В§ 3.2было показано, что на изоморфных системах истинны одни ите же предложения.
Обратное неверно для бесконечных систем. В этомпараграфе мы покажем (теорема5.1.1 ),что истинность на 2( и !В однихи тех же предложений равносильна существованию <<достаточно большого~ запаса конечных частичных изоморфизмов 2( и !В. В частности,если на конечных системах 2( и !В истинны одни и те же предложения,то 2( изоморфна !В.Определение.
Две алгебраические системы 2( и !В сигнатуры :Еназываются элементарно эквивалентными (обозначаем 2(= !В),еслидля любого предложения Ф сигнатуры :Е имеет местоМножество предложений{ Ф 12t F2t илиментарной теорией системычерез2t = !Вравносильно равенствуОпределение. Пусть 2( и !В= (R, F, µ).называетсяа1,...
, апчастичнымTh(2t)= Тh(!В).алгебраические системы сигнатуизоморфизмом2(f:вХ --+ В, где Х ~ А,!В,еслидлялюбыхЕ Х выполняются следующие условия:1)если s ЕR UF -2)если s ЕF ---Инъективное отображениене константа, токонстанта, то(Напомним, что если пХпросто теорией 2( и обозначаетсяTh(2t).Ясно, что отношениеры :ЕФ} сигнатуры :Е называется эле=О, токонечное множество, тоf(ai, ... , ап) = ( ) =Л= 0.)Еслиназывается конечным частичным§ 5.1. Элементарная эквивалентность145изоморфизмом. Множество конечных частичных изоморфизмов Qt вобозначаем черезТеорематогоПусть Qt и5.1.1.чтобы системынеобходимоиi:!3P(Qt, i:13).Qt идостаточно,системы сигнатуры Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
