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

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

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

По теореме компактности Химеет модель 21. Так как v2l (с) -=1- v2l ( d) для d, с Е С, с -=1- d, то 21 имеетмощность?:х.DУпражнения1.Показать, что фильтрованное произведение частично упорядочен­ных множеств является частично упорядоченным множеством.2.Показать, что декартово произведение к, х К2 двух полей К1и К2 не может быть полем. (Указание.В к, х К2 имеютсяделители нуля.)3.Найти неизоморфные алгебраические системыторых:Е4.система= (r 1 ),ЕслиD121 и !.В, для ко­21 х 21 изоморфна !.В х 1.В.(Указание.. ПустьА= В= (.с), v2l(r) =(.с)\ {О}), v'1\r) =(.с)\ {О,~D2 -два фильтра на множествегомоморфизм системыD1 -prod 1.ВiнаI,1}.)то существуетD2-prod 1.Вi. (Указание.Рассмотреть отображение, сопоставляющее элементуDifэле­ментD2f.)5.

Пусть D -главный ультрафильтр на I и П D = {io}. ТогдаD-prod 21i изоморфна системе 21io·6. Пусть Г - такое множество предложений сигнатуры :Е, чтодля любой алгебраической системы 21 сигнатуры :Е существуетпредложение Ф Е Г, истинное на 21. Показать, что существуеттакое конечное множество { Ф1, ... , Фп} ~ Г, что предложение(Ф1 V (Ф2 V ... V Фп) ... ) - тождественно истинная формула.системаГлава4ИСЧИСЛЕНИЕ ПРЕДИКАТОВ§ 4.1.Аксиомы и правила выводаЗафиксируем некоторую произвольную сигнатуру Е. В этом пара­графе мы определим исчисление предикатов сигнатуры Е (сокращен­но ип 1\Формулами ипЕ будут формулы сигнатуры Е.

Секвенциями ипЕназываются последовательности видаФn,···,Фnf-Ф,где Ф1,... , Фn,Ф-формулы сигнатурымы получаем секвенцию видаf-~-Примем следующие соглашения. Пустьt,, ... , tn пись ( Фтермы сигнатуры Е и Ф)f/:.::'."t:nНапомним, что при п=ОФ.-xi, ... , Xn-переменные,формула сигнатурыбудет обозначать результат подстановки термов~-За­t,, ... , tnвместо всех свободных вхождений в Ф переменных х 1 ••• , Xn соответ­ственно, причем если в тексте встречается запись ( Ф)f/.::::'t:n,то пред­полагается, что при этой замене не увеличивается число связанныхвхождений переменных.

Это означает, что для всехi=1, ... , пни односвободное вхождение в Ф переменной Xi не входит в подформулу Фвида 'v'уФ1 или :3уФ, для у ЕFV(ti).Запись [Ф]t будет обозначать фор­мулу( Ф )t, и при ее появлении предполагается, что кроме условия назапись ( Ф )t еще выполняется условие у rf. FV (Ф). Когда в тексте ужевстречалась запись Ф(х,, ... , xn), вместо громоздкой записи ( Ф )f/:.:::'t:nчасто будем писать просто Ф(t,, ... , tn). Заметим, что по соглашениюв начале § 3.2 переменные х,, ...

, Хп попарно различны, в то время каксредиt,, ... , tnмогут быть равные термы.Определение. Аксиомами ИПЕ являются следующие секвенции:1) Ф f- Ф, Ф - формула сигнатуры ~;2) f- t ""' t, t - терм сигнатуры Е;3) t ""'q, (Ф)f f- (Ф)~, х - переменная, t, q - термы, Ф - формуласигнатуры Е, удовлетворяющая условию на запись ( Ф )f и ( Ф )~.§ 4.1.Аксиомы и правила вывода115Определение. Правила вывода ИПЕ таковы:Гl.23f--Ф; ГФ_f--.'Гf--Фll Г,Ф,Ф,Г1 f--X_. Г, Ф,Ф,Г1 f-- Х'Гf--Ф/\Ф..'Гf--ФГf--ФГf--Ф4·12. Г Ф f-- Ф;Г f-- Фv Ф'г f-- Ф vw;6Г, Фf--13 ·Х; Г, Ф.Г,Фf--Х; Гf--ВГf--ФV Ф.'Ф; Гf--Г f-- \lxФ'в члены Гсвободно;14 Г, (Ф)f f-- Ф_.Г, \lхФf--Ф'15 Гf--(Ф)f_ФГf--Ф-+Ф.f--Гf--Х7.где х не входитГf--ФГf--Ф5·f-- J .'Гf--ФlO Г f-- Ф; Г f-- ~Ф..Гf--J'Гf--Ф/\Ф..Г, ~Ф9Гf--Ф/\Ф'.ФГf--Ф-+Г f--::JxФ'где х не входитГ,Фf--ФФ.16 ·'Г,::JхФ f-- Ф'wивчлены Гсвободно;Как и в ИВ, в правилах вывода Ф, Ф,Х - формулы ИПЕ, а Г, Г1 последовательности таких формул.

При этом в правилах13-16фор­мулы Ф, Ф и последовательности Г должны удовлетворять указаннымусловиям, а также условиям на запись( Ф )f. Так же как и в ИВ,если в правилах вывода вместо Ф, Ф, Х и Г, Г1 берутся конкретныеформулы и конкретныепоследовательности формул,то получаютсячастные случаи (или применения) правил вывода. Если8 -частныйслучай правила вывода а::, то будем говорить, что секвенция, стоящаяв8под чертой, получается из секвенций, стоящих в8над чертой, припомощи правила а::. Следующее определение является почти дословнымповторением соответствующего определения ИВ.Определение. Линейным доказательством в ИПЕ называется ко­нечная последовательность Со, ...

, Cn секвенций ИПЕ, которая удовле­творяет следующему условию: каждая секвенция Ci, i ~ п, либо явля­ется аксиомой, либо получается из некоторых предыдущих при помощиодного из правил вывода1-16.Линейное доказательство Со,... , CnГл.1164.Исчисление предикатовназывается линейным доказательством своей последней секвенции Сп.Если существует линейное доказательство в ИПЕ секвенции С, тос называется доказуемой в ипЕ или теоремой ипЕ. Формула фИПЕ называется доказуемой В ИПЕ ИЛИ теоремой ИП~ если В ИПЕдоказуема секвенция1-Ф.ДеревоDназывается доказательствомв виде дерева или деревом доказательства секвенции С в ИП~ есливсе его начальные секвенции - аксиомы ИП~ переходы - примененияправил1-16,а заключительная секвенция равна С.Определения допустимого правила и квазивывода совпадают с со­ответствующими определениями из § 1.3 с заменой ИВ на ИПЕ.Предложение 4.1.1.

Секвенция С является теоремой ИПЕ тогдаи только тогда, когда существует ее доказательство в виде деревав ипr:.До к аз ат ел ь ст в о. Почти дословное повторение доказательствапредложения1.3.1.DФормула Ф ИПЕ называется тавтологией, если она получается изформулы Ф исчисления высказываний, доказуемой в ИВ, путем заменывсех ее пропозициональных переменных Р1,...

, Pnна некоторые фор­мулы ИПЕ Ф1, ... , Фn соответственно. Формулу Ф при этом назовемосновой тавтологии.Предложение4.1.2.Любая тавтология Ф сигнатурыI:доказу­ема В ИПЕ.До к аз ат ел ь ст в о. Пусть Ф получена из основы Ф заменой пере­менных Р1,... , PnПусть деревоции1-на формулы Ф 1, ... , Ф n соответственно.D1получено из дерева доказательстваФ заменой переменных Р1,... , PnDв ИВ секвен­соответственно на Ф 1, ...

, Ф n изаменой остальных пропозициональных переменных на произвольнуюформулу Фn+l сигнатуры I:. Очевидно,доказательства секвенции 1- Ф в ИПЕ.что деревоD1 является деревомDПредложение 4.1.3. Пусть Ф - формула ипЕ, Х}, •.. , Xn - пере­t 1 , ••• , tn - термы сигнатуры I: и выполняются условия наменные,запись (Ф )f/.:J:n. Тогда в ИПЕ доказуемы следующие секвенции:а) \/х ...

\/х ф 1- (Ф)х,, ... ,Хn;1nt,, ... ,tn...б) (Ф)х,, ,хnt,, ... ,tn1-:3х1... :3хnФ.До к аз ат ел ь ст в о. Пусть у1,... , Yn -попарно различные пере­менные, не входящие в формулу Ф, в термыX!,•••,Xn.t1, ... , tnи отличные отАксиомы и правила вывода§ 4.1.а). Для всех( \/х1< k <117п имеет место равенство...

,хk-1 )xkk+I ... \/х n (Ф)х1,Yl,···,Yk-lYk= \/х k+I ... \/х n (Ф)х1,... ,хkYI,···,Yk'и выполнены все условия на такую запись. Поэтому следующее деревобудет доказательством в ИПЕ:( ф)Xl,•··,XnYl,···,Yn\/хnf--(Ф)Xl,···,Xn-l(Ф)Xl,···,XnYl,···,Ynf--(Ф)Xl,•••,XnYl ,···,Yn-lYl ,···,Уп\/х - \/х (Ф)х, .... ,Хn-2 f-- (Ф)Xl,•••,Xnn I nYl,···,Yn-2Yl,···,Yn\/х1...

\/х n ф f--... ,хnYl,···,Yn(Ф)х,,Применяя теперь п раз правило 13, получаем доказуемость в ИПЕсеквенции\/х1 ... VxnФ f-- \/у1 ... Vуп(Ф);!:::::;:.Обозначим формулу (Ф)t!:::::::; через Ф. Тогда для Ф выполнено условиена запись (Ф)Y/:.::]nn. Для всех 1 < k < п имеем)Yk vv (w)Y'····,Yk(vYk+I · · · vУп (w)Yl,···,Yk-lt 1, ... ,tk-l tk = Yk+I · · · Упt1, ... ,tkи условия на такую запись. Снова применяя п раз правило14,получаемдоказуемость в ИПЕ секвенции\/у1 •••\/yn ф f-Так как (Ф)Yi::::J:дом в ипr::Lг1.-/vy1 ...=(Ф)t:::::1:, то следующее дерево будет квазивыво­vYn ,т,'!!1.-/(\Jl)f/,'.::]nn •-+,Хn.ti, ......,tn,(Ф)х,,1.-1vX) ...vXn ф1.-1lг1.-/vy1 ...1.-/,т,vУп '!!б).

Доказательство аналогично а). Сначала, применяя несколько разправило15,получаем теорему( Ф)х,, ... ,ХnYI,···,Ynf--:3х1... 3хпФ.Затем, применяя несколько раз правило 16, получаем теорему ИПЕ:(4.1)118Гл.4.Исчисление предикатовОпять, применяя несколько раз правилополучаем доказуемость15,В ИПЕ секвенции( ,т,)Уl,···,Уп'¼'=где IJ!(Ф)i!:::::;;:. Измость в ИПt1 , ...,tn1.::J::J,т,(4.2)Г ::JY! · · · ::JYn 'i' •(4.1) и (4.2) так же, как в а), следует доказуе­секвенции б).ОПредложение 4.1.4. В ИПЕ допустимы правила а)-д) из предло­1.3.3 и упражнения 2 к § 1.3, а также правиложенияИФ1, ... , Фk f- IJ!(Ф~ )x,, .. ,,Xn, ... , (Фk)x,, ..

,,Xn f- (\J!)x1, .. ,,Xn ·)·t,, .. ,,tnt, ,.. ,,tnt, ,.. ,,tnДо к аз ат ель ст в о. Для правил а)-д) доказательство по суще­ству совпадает с доказательством допустимости соответствующих пра­вил из§1.3.и). Пусть секвенция Ф1, ... , Фk f- 1J! доказуема в ИПЕ. Применяянесколько раз правило 7, получаем доказуемость в ИПЕ секвенцииf-Ф1--+ (Ф2--+ ... (Фk--+Применяя несколько раз правилоИз предложения4.1.3, а),13,\J!) ... ).получаем доказуемость секвенциии допустимого правила в) получаем доказуе­мость В ИПЕ секвенции(4.3)Из (4.3) и аксиомы (Ф1)fi':.:::t:n f- (Ф1)fi':.:::t:n по правилам 8 и 12 получа­ем секвенцию( фl)x,,t1 ,..... ,,Xn,tn f-(Ф2--+ ( ...

(Фk --+\J!) .. .))x,,,Xn.t, ,......,tnАналогично применяя еще несколько раз правило8,получаем доказу­емость В ИПЕ секвенции( фl)x,, ... ,Xn, .. ,, (Фk)x,, .. ,,Xn f- (1J!)x1, ... ,Xn.t1 '" .. ,tnft , ... ,tnоft , ... ,tnЕсли С - секвенция ИПЕ, то объединение всех множеств FV(Ф),где Ф-формула из С, называется множеством свободных перемен­ных секвенции С и обозначается черезОпределение. Пусть С=раическая система сигнатурыFV(C)Г f- IJ! -I:и"/ -FV(C).секвенция ИПЕ, 2t -алгеб­интерпретация переменных изв множестве А. Секвенция С называется истинной в21при§ 4.1.

Аксиомы и правила вывода119Fинтерпретации "f (обозначаем 2tС["!]) тогда и только тогда, когдаФ["f] или 2t~Ф["t] для некоторой формулы Ф из Г.2tFFЕсли секвенция С не истинна в 2t при"/, то говорим что С ложна2t при т Из определения получаем, что секвенция f- J ложна в любойалгебраической системе 2t.вОпределение. Секвенция С исчисления ИПЕ называется тожде­ственно истинной, если 2tF С["!]для любой алгебраической системы2t сигнатуры I: и любой интерпретации т FV ( С)---> А.Ясно, что свойство секвенции С быть тождественно истинной независит от того, в каком исчислении ИПЕ она рассматривается (т. е. отсигнатуры I:).Основной целью для нас в этой главе будет доказательство следу­ющего замечательного результата К. Гёделя: класс доказуемых в ИПЕсеквенцийсовпадаетсклассомтождественноистинныхсеквенцийИПЕ. Это утверждение называется теоремой полноты исчисленияпредикатов.

Одна часть этого утверждения доказывается легко.Теорема 4.1.5. Все доказуемые в ИПЕ секвенции С являютсятождественно истинными. В частности, исчисление ИПЕ непроти­воречиво, т. е. Не все формулы ИПЕ доказуемы В ИПЕ.До к аз ат ель ст в о проведеминдукцией по высоте доказатель­ства секвенции С в виде дерева. Очевидно, что аксиомы ИПЕ яв­ляются тождественно истинными.вода1-16тателю в качестве упражнения.киправилПусть ФПроверку того, что правила вы­сохраняют тождественную истинность, мы оставляем чи­14инужно15формула,-(Ф)t', Х="/ 1(Х \{х})t -Заметим только, что для провер­сначала установитьследующийфакт.терм и выполняются условия на записьFV(Ф), У= FV((Ф)t'), т Х---> А,"/*: У---> А.

Тогда если= "/* 1(Х \{х}) и "t(x)= t 21 ["t*],тоЭтот факт легко устанавливается индукцией по длине Ф.DВторую часть теоремы полноты мы докажем в § 4.4. Для этого намнужно сначала получить достаточное количество доказуемых в ИПЕсеквенций. Следующее предложение показывает, что обычные свойстваравенства доказуемы в ИПЕ_ Если t,, ... , tn, t - термы сигнатурыI:, х,, ...

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

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