1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 27
Текст из файла (страница 27)
Так как формулы5Ю. Л. Еошов. Е. А. ПалютинГл.130сигнатурыЕ14.являютсяИсчисление предикатовсловаминекоторого счетного алфавита,томножество всех формул сигнатуры Е1 имеет счетную мощность. Пусть{ ФпIпЕмножество всех предложений сигнатуры Е1.w} -Строим последовательностьХо ~ Х1 ~...~ Хп ~п Е w,... ,конечных множеств предложений сигнатуры Е 1 следующим образом:1.Хо =Х.2. Если Хп U { Фп} противоречиво, то Хп+13.Если Хп= Хп U ГФп}.U { Фn} непротиворечиво и Фп не начинается с квантораXn+I = Хп U {Фn}-существования, то4.
Если Хп U { Фn} непротиворечиво и ФпU {Фn, (Ф')~k}, где Ck Е С=:JхФ', тоXn+I =константа с наименьшим-Хп Uk,невходящая в Фп и элементы Хп.ПоложимXw.а)= UXwПусть Ф и ФXw-Хп. Установим некоторые свойства множестваnEwпроизвольные предложения сигнатуры Е1:непротиворечиво;б) либо Ф Ев) если Ф1,г) ФАд) фWЕV wЕXw, либо ·ф Е Xw;... , Фп Е Xw и Ф1, ... , Фп f- Ф доказуема,Xw {==} (Ф Е Xw и W Е Xw);Xw {==} (Ф Е Xw или ф Е Xw);то Ф ЕXw;tj. Xw;W Е Xw {==} (Ф tj. Xw или Ф Е Xw);з) :JхФ Е Xw {==} ((Ф)~k Е; Xw для некоторой Ck Е С);и) \fхФ Е Xw {==} ((Ф)~k Е Xw для любой ck Е С);е) ·ф Е w {==} Фж) Ф-->к) еслиt -замкнутый терм сигнатуры Е,, то Ck ~tЕXwдлянекоторой константы Ck Е С.Для доказательства а) в силу предложенияустановить, что Хп, п Еиндукцией по п.4.4.1,г), достаточноw, непротиворечивы.
Рассуждение проводимПо условию Хо=Хнепротиворечиво. Пусть Хпнепротиворечиво. Если для Фn имеет место случай2,то Хп+I непротиворечиво по предложению4.4.1, д). В случае 3 множество Xn+l непротиворечиво по условию. Пусть Хп U {:JхФ'} непротиворечиво и деревоD - доказательство в ИП:Е' секвенции Ф1, ... Фk,:JхФ 1 ,(Ф')~k f-J, гдеck Е С не входит в формулы Ф1,... , Фk, :JхФ'. Пусть у - переменная, неD, и D' получается из D заменой всех вхожденийck на у.
Очевидно, что D' будет доказательством в ИП:Е' секвенцииФ 1 , ... , Фk, :JхФ', [Ф']~ f- J, что противоречит предложению 4.4.1, в), если Wi Е Хп, 1 ~ i < k.входящая в деревоСвойство б) вытекает непосредственно из построенияФ=Фп для некоторого п Еw.Xw,так какСвойство в) легко следует из свойств а)§ 4.4.Теорема о существовании модели131и б). Свойства г)-ж) имеют место в силу свойств а), б) и в). Докажемсвойство з). Пусть Фп= :3хФ.Если :3хФ ЕXw,то по свойству а) Хп UU { Фn} непротиворечиво, тогда ( Ф );\ Е Xn+l для некоторой константыCk Е С.
С другой стороны, так как (Ф);':k 1-- :3хФ - теорема исчисленияпредикатов, то из ( Ф );':k Е Xn+l и свойства в) получаем :3хФ Е Xw,Докажем свойство и). Если \iхФ Е(Ф );':k 1-- ( Ф );':kпо правилусвойству в) получаем (Ф);':k Еимеем ~vхФ Е:3х~Ф Еи Ck Е С, то из аксиомыXw14 получаем теорему \iхФ 1-- ( Ф );':k. Отсюда поXw.Если \iхФiИз эквивалентности ~vхФXw.По свойству з) получаем ('Ф);':k ЕXw,Е С. Тогда по свойству е) имеет место (Ф);':kiXw,то по свойству е)= :3х~ФXwXw.и в) получаемдля некоторой Ck ЕДокажем теперь последнее свойство к).
Секвенция1-- (х ~ t)f является аксиомой исчисления предикатов. По правилу15 получаем,1-- :3х(х ~ t) - теорема ИПЕ 1 • Теперь к) следует из в) и з).чтоВ дальнейшем элементы множества С будем обозначать через с,иdi, ei iЕw.dНа множестве С определим отношение"' так:Сrv~ С~dИз свойства в) и предложенияdЕ4.1.6, а)-в)Xw,следует, что"'есть эквивалентность на С. Если с Е С, то обозначим через с класс эквивалентности по отношению"',содержащий с.=Переходим к определению алгебраической системы Qt(А, v'Ж).Пусть А = {с I с Е С}. Сигнатура системы Qt равна Е 1 = (R, F U С, µ1).Определим интерпретацию v'Ж сигнатуры Е1 в Qt.
Пусть с, d1, ... , dn ЕЕ С. Тогда1) v2l(c) = с;2) (d1, ... , dn) Е v'Ж(r) ~ r(d1, ... , dn) Е Xw где r Е R, µ(r) = п;3) если f Е F, µ(!) = п, то v2t(f)(d1, ... , dn) = с ~ с~ f(d1, ..... ,dn)ЕXw,Корректность определения предикатов системы Qt посвойства в) и предложения4.1.6, д).2)Проверим, что если3) действительно является определением опЕ:,Рации на1-следует изfЕF,тоПусть с ~... ,еп) Е Xw и d1 = е1, ... ,dп = еп. ТогдаXw, откуда по свойству в) и предложению4.1.6, г) получаем f(d1, ... , dn) ~ f(e,, ... , еп) Е Xw, следовательно, посвойству в) и предложению 4.1.6,j)-r), 3меем с ~ d Е Xw, т. е.
с= с!.С другой стороны, для любых d1, ... , dn Е А по свойству к) имеемс~ f(d,, ... , dn) Е Xw для некоторого с Е С, т. е. v2l(J) определена налюбых а,, ... , ап Е А.Индукцией по длине замкнутого терма t сигнатуры Е 1 покажем,~f(d1, ...
,dп)d1~ е1 ЕЕXw,Xw, ... , dnс'~ !(е1,~ еп Ечтоt'Ж5*=с~ с~ t Е Xw.(4.4)Гл.132Если4.Исчисление предикатовконстанта из С, тоt -(4.4)следует из определения отношения ,.._, и из 1) определения v21 • Для термовt вида J(d1, ... , dn), гдеt - константа из I;), эквивалентность (4.4) следует из оп_ределения v_,2{(!). Пусть t = J(t1, ...
, tn),f Е F, µ(!) = п ~ 1 и tf = d1, ... , t~ = dn. По индукционному предположению d1 ~ t1 Е Xw, ... , dn ~ tn Е Xw, поэтому из предложения4.1.6, r), и свойства в) получаемd1, ... , dnЕ С иЕf(в частности, когдаF(4.5)По определениюv2{(!)имеем(4.6)Из(4.5), (4.6),предложения4.1.66),в) и свойства в) получаем(4.4).Индукцией по длине предложения Ф сигнатуры I;l покажем(4.7)Если ФQ(= t 1 ~ t2,FФто по~ (с~(4.4)t1ЕимеемXw, с~ t2Отсюда в силу предложенияЕXw4.1.6, б)-г),для некоторого с Е С).и свойств в), к) множестваXwR, иtf = di, ... ,t~ = dn. Используя определение v21 (r), (4.4), предложение4.1.6 и свойство в), получаем (4.7) для такого Ф.
Для остальных Фэквивалентность (4. 7) сразу получается из индукционного предполополучаем(4.7)для этого случая. Пусть Ф= r(t1, ... ,tn), rЕжения и соответствующих свойств в)-и).Так как Х<; Xw,то из(4.7)получаем, что Q( является моделью длямножества Х.ОСледствием доказанной теоремы являетсяТеорема4.4.3(теорема Гёделя о полноте). Если С-тождественно истинная секвенция исчисления предикатов, то С доказуемав исчислении предикатов.Доказательство.Пусть С равнаФ1,... ,Фп 1--ственной истинности С получаем, что множество {Ф1,имеет модели.
Из теоремыФ 1 , .•• , Фп,~w 1-- J -4.4.2Ф.Из тожде... , Фп, ~Ф}теорема исчисления предикатов. По правилуполучаем, что С доказуема.Доказательство теоремынеследует, что оно противоречиво, т. е.9О4.4.2дает нам следующий факт: конечноенепротиворечивое множество Х формул сигнатуры I; имеет конечнуюТеорема о существовании модели§ 4.4.или счетную модельмы~-133К сожалению, теорема компактности, которуюприменили для произвольного множества Х, ничего не говоритнам о мощности модели для Х. Однако сила метода доказательстватеоремы4.4.2позволяет обойтись без теоремы компактности и заоднополучить информацию о мощности полученной модели. Сначала введемодно понятие.Определение.
Множество предложений Х сигнатуры Е называетсяполным в Е, если Х непротиворечиво и для любого предложения Фсигнатуры Е либо Ф Е Х, либо ~Ф Е Х.ПредложениеЛюбое4.4.4.непротиворечивоемножествоХпредложений сигнатуры Е содержится в некотором полном в Емножестве предложений У.До к аз ат ель ст в о. Рассмотрим семейство Р всех непротиворечивых множеств предложений сигнатуры Е, содержащих Х. Отношениевключения ~ частично упорядочивает множество Р.
Очевидно, чтообъединение любой цепи измаксимума (Р,4.4.1, д)получаем, что УТеорема(Р,принадлежит Р.~)По принципуимеет максимальный элемент У. Из предложения~)4.4.5.-полное в Е множество.DЕсли бесконечное множество Х формул сигнатуры Е непротиворечиво, то Х имеет модель ~ мощности, непревосходящей мощность Х.До к аз ат ель ст в о. Пустьхотябыводну формулужество С' =С'(R U F){Сх I х Е FV(X)}= 0. Пусть Е(Х)входятбыnхотяводнувсе переменные, входящиеFV(X) -из Хсвободно.Рассмотримтакоемносимволов, что Сх =J Су для х =J у и- сигнатура, все символы которойформулу изХ.ПустьЕополучаетсяизЕ(Х) добавлением элементов множества С' в качестве символов новых констант. В силу следствия 2.5.7,IEol~IXI.Заменим во всехформулах из Х все свободные вхождения переменных х ЕFV(X)на константы сх Е С' соответственно.
Ясно, что полученное множество Х' предложений сигнатуры Е 0 имеет модель тогда и толькотогда, когда Х имеет модель. Множество Х' непротиворечиво 1). В самом деле, предположим, что дерево(Ф1)~,, ..., ...,х;, ... , (Фk)~i,,.. ,x; f- J,, Xnxi , ... , xnх1доказательство секвенцииD -где Ф1,... , ФkЕ Х И Сх 1 ,... ,Схn-все константы из С', входящие вна переменные У1,D'секвенции1)D. Заменив константы сх,, ...
, Cxn... , Уп, не входящие в D, получим доказательство(Ф 1 )x,, ... ,xn, ... , (Фk)x,, ... ,xnYI ,..·,YnYI ,..·,Ynf-'1:'_UПрименяяпредложениеПо причинам, которые выяснятся в конце данного параграфа, мы даемздесь доказательство, не опирающееся на теорему4.4.2.Гл.134Исчисление предикатов4.и), получим доказуемость Ф1,4.1.4,... , Фk f- J,что невозможно в силунепротиворечивости Х.Переходим к построению множеств предложений Хп,сигнатурп Е w,ип Е w.
При этом будут выполняться следующие условия:En,1) Хп ~ Xn+I, п Е w, Х' ~ Хо;2) Xn - полное в En множество предложений;3) сигнатура En+I получается из En добавлениемновых символовконстант;= IXI,4) IEnl ~ IXnln ЕW.В качестве Хо берем полное в Ео множество предложений, содержащееХ'.
Если Хп уже построено, томножества{ сФIФЕEn+I получается из En добавлениемXn} новых символов констант. Рассмотрим множество предложенийХ~сигнатурыв= :3хФ, ФЕ Xn}{w;, ... , Ф~, Ф1, ... , Фm}~ Хп,w, = :3z1Ф1, ... , Фm =секвенциядоказуема иствеIФEn+I · Множество Х~ непротиворечиво. В самом деле, предположим, что для= :3zmФm,= Хп U {(Ф)~п..,m -минимальное такое число. Заменяя в доказательcq, 1 на переменнуюD, получим доказательство D' секвенцииDэтой секвенции константуИз предложения4.4.1в) получаем, что секвенциядоказуема, а это противоречит минимальностиберем теперь полное вПусть Xwп Е= UEn+lm.В качествеXn+Iмножество предложений, содержащее Х~.Xn и С есть множество всех констант из всех En,nEww.у, не входящуюТак как каждое Хп непротиворечиво, то иОчевидно также, что Xw -Xwнепротиворечиво,полное в Ew множество, где Ew= UEnnEwполучается из Е добавлением элементов С в качестве символов констант.
Следовательно,теоремы4.4.2,Xw,имеет свойства а) и б) из доказательствагде вместо сигнатуры Е1 рассматривается сигнатураEw.Из свойств а) и б) следуют свойства в)-ж). Свойство з) следует изпостроения множеств Х~, п Еw. Наконец, свойства и), к) следуют§ 4.5.Исчисление предикатов гильбертовского типаиз свойства з) так же, как в теореме1354.4.2. Далее нужно в точности4.4.2, начиная с определенияповторить конец доказательства теоремыотношения...,на множестве С.Осталось только заметить, что мощность модели Q( не превосходитмощности множества С, которое в свою очередь является объединениемсчетного числа множеств,имеющих мощность,непревосходящуюмощность Х, и, следовательно, имеет мощность, не превосходящуюwх Х.мощностьТеорема4.4.5По следствию2.5.6, а)вместе с теоремойимеем4.1.5lw х XI = IXI.Dдает также новое доказательство теоремы компактности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
