Гильберт, Аккерман - Основы теоретической логики (947372), страница 21
Текст из файла (страница 21)
Аналогично дая аксиомы Р (у) — «(Ех) Р (х) имеем преобразования; (у)(Р(у) — "(Ех) Р(х)), (Р(!) — «(Ех) Р(х)) й(Р(2) «(Ех) Р(х)), (Р(1) — «Р(1) 'хс Р(2)) й(Р(2) — «Р(!)" ,Р (2)), (А — «А '„' В) й ( — «А ',' В), ко горце также приводят к всегда-истинной форьху се. Нам остается еще только показать, что применение правил «),,'), Т), 3) не нарупшет этого свойства.
Если мы имеем дзе формулы, вторая из которых получается из первой вследствие применения правил а!) или иЗ), то после преобразования обе формулы будут связаны правилом подстановки исчисления выгказываций или же вторая формула будет конъюнк- цией формул, каждая нз которых получается из пер- вой в результате применения правила подстановки исчисления высказываний. Правила и2) и о) превра- щакпся в простые повторения. Схема заключения сохраняет свою форму, если в формулах не встреча- ются снободные предметные переменные.
Если же схеаа заключения содержит еще свободные предметные пере. менные, то она может потерять свою форму после гого, как мы поставим впереди формул знаки общно- сти. Например, нз г( (х) И 1х) й (х, и !.х! получаем новую схему: (х) 6 (х) [х)(И (х! И (х)1 (х) ИП(х) После исключения знаков общности получаем: хг (1) й х( (2) (и(ц-и(ц) а(и (г)-и(г)1 м (!) й и (г! Но зта схема также соотпетствует правилам исчис- ления нысказываний. Аналогично обстоит дело в слу- чае нескольких свободных предметных переменных. Остается, наконец, правило .!). Выражение л- 6 (х) переходит (если 21 не содержит свободных перемен- ных) с помощью нашего преобразования в (х) (1Д вЂ” «6 (х)), (хс †« 6 (!)) й Л вЂ « 6 (2)) и т. д.
сй (х) 6(х) превращается в !Д -« 6 (!) й 6 (2). Но, по правилам исчисления высказываний, обе формулы эквивалентны. Так же обстоит дело в слу- чае, когда сй содержит еще свободные переменные. То же верно для правила Т), поскольку оно касается присоединения знака сущесгнонаиия. Таким образом, мы действительно доказалн, что всякая формула, выводимая из аксиом, с помощью нашего преобразования перехостит во вссгда-истицное сложное высказывание. Между тем формула (Ех) Р (х) (х) Р (х) 77алквта скатали аксивк !27 Утис иетслснис крсдсскатвв этого свойства не навеет, так как преобразование ее дает последовательно.' Е(1) 'кс Е(2) — > Е(1) ВГ(2), Л кл'  — а А т В, а это не всегда истинная формула исчисления высказываний.
Итак, мы показали, что наша система аксиом не полна в более строгом смысле слова. Возникает вопрос, име~т ли здесь место полнота в другом смысле, также упомянутом на стр. 16, т. е. нельзя ли из этой системы аксиом вывести асс тождественные — в смысле нашего определеняя в начале $5 этой главы — формулы исчисления прегикатсв. Полнота в этолв смысло действительно имеет место. Локазательство ее было дано К.
Гсдслсм; в последующем мы придерживаемся его изложения'. Согласно соображениям в конце 1 8, каждой формуле исчисления прсднкатов можно привести в соответствие некоторую формулу в нормальней форме Сколема, которая выводима или не выводилва одновременно с данной. Поэтому мы можем ограничи~ься установлением того, что все тождественные формулы в нормальной форме Сколема выводимы. Пусть (Ех,)...
(Ех )(у,)... (ус)6(х„..., х; у„..., у,) есть подобного рода формула. Прежде всего мы замечаем, что «-группы (хсн хси..., х„), образованные из неограниченного ряда предметных переменных х„х„х,..., можно перенумеровать, упорядочииая их обычным способом по возрастающей сумме индексов (1,+1,+...+ 1',), а при той же сумме индексов — лексикографически.
Таким обрааом, ряд начинается с групп (х„х„..., х,); (х„х„..., х,); (х„х„, ..., х„х,)ь.. Обозначим л-ую с насев, к., иве уапвгаащааеи есс лаваше еев ыавкьеп наеж1аеееаевао1 ° , мь, месь. ньуввк, ве, зт (воза). из этих й-групп через (х„„х,в, ., ., хщ).
Будем понимать, далее, под 6, формулус й(х„„х»„..., хтб хщ-исав, х< -в11+е,...,х.с) При этом мы замечаем, чсо предметные переменные, стоящие в этой формуле после точки с запятой, отличавотся от тех, которые стоят перед этим знаком, а также от всех переменных, встречающихся в формулах 6„(р С л). Напротив, все переменные х„„,..., х„, уже встречаются в формулах 6 (р < л). Буделв понимать, далее, под б„ дизъюнкцию 6, ", 6,',' 'ч' 6„, под л)„— формулу, получающувося из б„в результате присоединения впереди б„ всех знаков общности, соответствующих свободным переменным. Каждой формуле б„мы призодньв теперь в соответствие некоторую формулу исчисления высказываннй.
А именно, мы заменяем элементарные составные части этой формулы (которыми, понимо переменных высказываний, служат предикатные переменные с иредметнымн переменными в качестве аргументов) переменными высказываниями, причем вместо одинаковых элементов ставим одинаковые переменные высказывания, а вместо различных в различные жс переменные высказывакил. Отнесенную таким образом к б„ формулу исчисления высказываний назовем 6„. Очевидно, формула 6„ такова, что б„ можно получить из фт применяя правило подстановки я1). Мы навеем теперь следующую альтернативу: 1.
Существует такое л, что 6, является тождественной формулой исчисления высказьований. 2. Ни для какого и 6„не является тождественной формулой исчисления высказываний. Мы докажем: (А) В случае 1. формула (Ех,)... (Ех ) (у,)... (у,) Ж (х„..., х,; у„..., ув) выводима из слстемы аксиом исчисления предикагов. (В) В случае 2. указанная формула не является тождественной, так как можно указать предикаты, определенные в области натуральных чисел, ко- Уолоо игшгснлиг лргдихитоо торно, будучи подставлены в фориулу вместо пе- ременных предикатов, превращают ее э ложяое вы- сказывание. Из этих предлоуКений, КОтоРые еще должны быть доказаны, получаем в качестве следствий: Каждая тождсспюепная формула исчисления пре.
дикатов является в то же время и выводимой фор- мулой, т. е. наша система аксиом, состоящая из основных формул а) — 1) и правил к1) — аЗ), р), Т), З), обладает свойстволг полноты. Если некоторая формула являепся вгегда-истин- ной в области натуральных чисел (или в какой.лиди другой счетной бесконечной области индивидуумов), т.с.
если при любой замене предикатнвгх переменных индивидуальными теорепшко.чшловыми предикатами и свободных предмегпных нере.асиных определенными числами она всегда переходит в истинное высказывание, то эта формула всегда-испгинна для любой области индивидуумов, гп. е. является тождесгнеенной. Последнее — важное — предлоткение, которое полу- чае~ся здесь в качестве побочного результата, может быть получено само по себе проще; оио впервые было доказано Левенгеймом ', Приведем теперь доказательства утверждений (А) и (В).
Прежде всего покажем истинность (А). Итак, пусть для какого-нибудь ч 6„являтся тсждестаенной формулой. Так как $„ получается из 6„ в резуль- тате подстановки по правилу а1) и, далее, сй„ полу- чается из 6„ по правилу у), то достаточно показать. что для каждого и: %„-ь (Ех,) ... (Ехс) (у,)... ... (у,) й(х„, .., х,; у„..., у,) является выводимой формулой исчисления предикатов, г гвненаеин, ь., Снег мезнське11ед гнь Пе!аихаажо1, Ма1Ь.
Аии. НО. тб (1915). Сушосгионное улриигенне нетода доказательстна мы находим и риэоге Слолеми, уномянутоа н коанс З згоа глазы. Лолюгно сшлгеми олсиом Мы покажем это с помощью индукции по п. Жо имеет форлгу: (х,) (х,)... (хг) 21 (х„..., х,; х„..., х,). Используя нссколько раз аксиому 1) и правило Ч, мы можем вывесгн формулу: (у,) "(И)21(„",=,.;у„",И)- (Ех,)... (Ех„) (у,)... (у,) й (х„..., х,.; у„..., у,). Отсюда с помощью лодстановки полу;им; (у,)... (у,) й(х„..., х,; у„, уй — ь (Ех,)... (Ех„) (у,) ...
(у,) й(х„..., х,; у„..., у,) и затем по правилу т2) и формуле (22): сй,— ь(Ех,)... (Ех ) (у,)... (у,) й (х„..., хгб у„..., у,). Пусть, далее, удое доказана формула: г)1и, — ь(Ех,)... (Ех,) ('у,)... ... (у,) й(х„..., х,; у„..., у,). ~и имеет форму: (х,)(х,) ... (х,г) 6,; т. е, (х,)... (хо,)($„, 1У 6„) илн, точнее: (х,) (х,)... (хи,) (6„, ,'21 (Хип ..., Х„„; Хг„в 1ЬГ, ..., Х„)). Д(ы уже прежде отметили, что переменные Х,„и ЬЬГ... Х,г В Юи., НЕ ВХОДЯТ; ПОЭТОМУ, ИСПОЛЬ- зуя формулу (2б), получии выводимую формулу: ях„- (х„) (х,) ... (х,„..п )(6„, 1у (у,)...(у,) й(х„„..., х„„; у„..., у,)). Формула (х) (р (х) " ,О (х)) — ь (х) Р (х) ',' (Еу) О (у) выводима. Она получается из формулы (34), если >токиота сиссиеми аксиом Узкое исчисоеиие а едикатов >ЗО >з1 в ней Г заменить на 7 и принять во внимание, что знак †» представляет собой лишь сокращение.
Используя несколько раз зту последнюю формулу, получаем далее: 6„--»(х,)(х,)... (хы,>ч) 6„, 'чс (Ех,)... ... (Ехс)!у,)... (у,) К (х„..., х; у„..., у,), т. е. 'Ви — > З,, '/ (Ех,)... (Ехо) (у,)... ... (у,) Н (х„..., х,; у„..., у,). Затем в силу х>„, — » (Ех,)... (Еха) (у,)... ... (ус) 6(х„..., хы у„..., у,) легко получим з>„- (Ех,)...(ЕхП(У,),,.(УВтч(х„..., ха; У„...,У,). Таким образом, индукция является полной. Теперь докажем (В). Допустим, что никакое 6„не является тождес>венной формулой исчисления высказываний, Для удобства последующих рассмотрений целесообрззно формулам исчисления высказываний 6„ придать некоторую специальную форму.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
