Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 76
Текст из файла (страница 76)
Непротиворечивость этой системы аксиом мы можем установить с помощью двуэлементной ннднвидной области. В качестве индивидов мы воаьмем 0 и 1. РавенстваО = 0 и 1 = 1 мы будем считать и с т и н н ы м и; 0 = 1 и 1 = 0 будем считать л о ж н ы м и. Штрих-функцию мы определим так, чтобы 0' имело значение 1, а 1' имело значение О. Основываясь на этих соглашениях и учитывая обычные определения функций истинности исчисления высказываний, мы получим определения и с т и ни о с ти и л о жн о с т и для формул, построенных с помощью связок исчисления высказываний иа равенств вида 0(0 = 0(д).
Теперь, с помощью метода исключения переменных, мы снова можем показать, что всякая выводимая указанными средствами формула, не содержащая переменных, является в смысле сформулированного здесь определения истинной. Отсюда, в частности, следует, что формула 0 ~ О, которая как отрицание истинного равенства 0 = 0 является ложной, не может быть выведена из укаванных аксиом и, следовательно, эта система аксиом является непротиворечивой.
Если мы теперь добавим к этой системе аксиом рекурсивные равенства 6 (0) = О, 6(п') =п, то система перестанет быть непротиворечивой. Именно, второе из этих равенств при подстановке 0' вместо п даст 6 (О") = 0', а из аксиомы а" = а мы путем подстановки получим 0" = О. Далее, используя аксиомы равенства, мы получим формулу 0" = 0 -д- 6 (О") = 6 (0), так что с помощью схемы ааключения получится равенство 6 (О") = 6 (0). Эта формула вместе с 6 (О") = 0* и 6(0) =0 с испольаованнем второй аксиомы равенства дает 0' = О, в то время как среди наших аксиом имеется формула 0'~ О. Создавшуюся здесь ситуацию можно объяснить и с содержа- тельной точки зрения.
Система, состоящая из двух равенств вида 1(0) = а, ((п') = 5 (п, ((п)), представляет собой некоторое налагаемое на функцию ( (п) условие, выполнимость которого вависит не только от структуры рекурсивных равенств, а еще и от характеристических свсйствиатрих- $ О НЕКОТОРЫЕ ПОЯСНЕНИЯ ПРИНЦИПИАЛЬНОГО ХАРАКТЕРА 389 4гл. Рп РЕКРРСИВНЫЕ ОПРЕДЕЛЕНИЯ функции: от того, что эта функция никогда не принимает 0 в качестве значения и что двум различным зыачеыиям аргумента всегда соответствуют два различных значения этой функции. Таким образом, допущение рекурсивных определений равносильно неявной характеривации иатрих-функции. Эта характериэация касается как раа тех двух свойств штрих-функции, в силу которых она дает нам отображение, соответствующее дедекнндовскому определению бесконечыости, и формализация которых приводит нас к аксиомам (Р,) и (Ра) а).
В свете этих соображений становится понятным, что введение рекурсивных определений согласуется не с любой непротиворечивой системой аксиом. Вместе с этим напрашивается предположеиие, что пеановскне аксиомы (Ра) н (Ра) могут быть выведены с помощью рекурсивыых определений. Такой вывод действительно оказывается возможыым, причем для этого нам потребуется взять за основу лишь аксиомы равенства и яумеоическую формулу 0' ФО. Вывод формулы (Р,) а' чь 0 получается введением рекурсивных равенств здпО =О, зяп и = 0'.
Действительно, вторая из этих формул в результате подстановки дает здп а' = 0'. Далее, с помощью аксиом равенства мы получаем формулу а' = 0 -~- здп а' = зяп О, квторая в сочетаыии с формулами здпа' =0' и едпО =0 дает с использованием второй аксиомы равенства формулу а' = 0 -» 0' = О. Получающаяся отсюда путем контрапозиции формула Ос~О-»а ~0 вместе с взятой в качестве аксиомы формулой 0' чь 0 а) См. с.
272 и далее. дает с помощью схемы заключения искомую формулу а' ~ О. Для вывода формулы (Р,) а' = Ь' — » а = Ь мы возьмем уже приводившиеся вьппе рекурсивные равенства 6 (О) = Е, 6 (к') = и. Второе из ыих при помощи подстановки дает формулы 6(а') =а, 6(Ь') =Ь. Из этих формул и из получающейся с помощью аксиом равенства формулы а' = Ъ'-» 6 (а') = 6 (Ь') мы с помощью второй аксиомы равенства получаем искомую формулу а = Ь -» а = Ь. Таким образом, в результате допущения рекурсивных определений аксиомы (Р,) и (Ра) становятся ненужными. Впрочем, если пользоваться схемой индукции, то формула (Р,) может быть выведена также с помощью рекурсивных равенств для 6 (и) вместо здп п.
В самом деле, ввиду того, что у нас имеется схема индукции и формула 0' ~ О, нам достаточно вывести формулу а' Ф 0 -» а' чь О. Но зта формула получается путем контрапозиции из формулы а" = 0-» а' = О, которая с помощью рекурсивных равенств для 6 (н) и аксиомы (Уа) получается из формулы а" = 0-» 6 (а") = 6 (0), выводимой с помощью аксиом равенства '). Попутно напомним, что (по замечанию, сделанному в гл. У')) из равенства 6 (и') = и с помощью аксиомы (Юа) может быть выведена формула (у,). Другая возможность, открывающаяся в результате допущения рекурсивных определений, заключается в том, что символ ( можно взять не в качестве основного знака, а ввести его посред- В См.
с. 238. 24 Л Гнаьберта Па Вернере (ГЛ. УП $1) НЕКОТОРЫЕ ПОЯСНЕНИЯ ПРИНЦИПИАЛЬНОГО ХАРАКТЕРА 371 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 370 ством определения. В самом деле, используя приведенное выше рекурсивное определение функции 6 (и), введем сначала функциональный знак а — ' Ь с помощью рекурсивных равенств а — '. О=а, а — 'и'=6(а — '. и). А затем явно определим формулу а ( Ь при помощи эквивалентности а< Ь Ь вЂ” 'а~О.
Используя эту эквивалентность, формулы ((г)~ (~а) (~а) можно будет перевести в формулы а — а=О, Ь вЂ” 'ачьО бс с — 'Ь~Π— э. с — ачьО, а' — ' а чьО. А этн последние можно будет вывести с использованием схемы индукции. Методика проведения соответствующих выводов математикам хорошо знакома, и логический формализм играет при этом только подчиненную роль. Поэтому будет достаточно, если ход этих выводов мы заметим лишь в целом. Для проведения этих выводов мы воспользуемся аамечанием, сделанным в гл. '1( относительно выводимости формулы (1 ) т). В самом деле, в нашем распоряженииимеется равенство б (и') = и. В соответствии с этим применение аксиом равенства сводится к применению аксиомы ((а) н второго рекурсивного равенства для б (и). Поэтому в дальнейшем мы часто будем говорить просто об аксиоме равенства, имея в виду аксиому (1,).
Дальнейшему мы предпошлем еще одно замечание относительно использования схемы индукции. Из схемы индукции в качестве проиаводной схемы можно получить следующее ее обобщение: 6 (О) 7( (З) ~ Ж (З') 7((у) где () — пронавольная не входящая в Я(0) свободная индивидная переменная. Выводимость этой схемы устанавливается следующим образом.
Если () представляет собой переменную а, то никакого доказательства не требуется. Пусть () — какая- нибудь отличная от а переменная, и предположим сначала, что а вообще не входит в Я (()). Тогда нз формулы Я (())-~- Я (()') мы подстановкой получим формулу Я (а) -м Я (а'), которая ') См. с, 238.
вместе с Я (0) по схеме индукции даст формулу Я (а) иэ которой мы подстановкой снова получим формулу Я (()). Если же Я (()) переменную а содержит, то мы подставим в формулах Я (О) и Я (()) -~ Я (()') вместо а какую-нибудь свободную переменную, не встречающуюся в Я (()). Иа получившихся в результате этого формул Я*(0) и Я "(()) -~- Яв (()') (в которые переменная а больше не входит) мы получим, как только что было показано, формулу Я* (Э), а нз нее снова подстановкой — формулу Я (()). Применение указанной обобщенной схемы индукции мы для краткости будем называть и н д у к ц и е й и о (). Например, формулу а' — ' Ь' = а — ' Ь мы можем получить индукцией по Ь из формул а' — '0'=а — 0 а' — ' Ь' = а — ' Ь-~- а' — ' Ь" = а — ' Ь', которые сами получаются с использованием рекурсивных равенств.
для а — ' Ъ и б (и), а также аксиомы равенства. Теперь, исходя иэ этого специального, полученного индукцеей по Ь равенства а' — ' Ь' = а — ' Ь, при помощи схемы индукции и аксиомы равенства можно будет вывести формулы а — '. а=О и а' — 'а=0'. В то же самое время, используя формулу 0' чь О, мы можем получить формулу а' — а Ф О. Тем самым мы получили первые две формулы из числа тех, которые нам надлежит вывести, и, значит, осталось вывести только формулу Ь ' а ~ 0 Ь с — ' Ь Ф 0 -+ с — ' а ~ О. Этот вывод мы проведем индукцией по Ь и с этой целью сокращенно обоаначим рассматриваемую формулу посредством Я (Ь).
Формула Я (0) получается при помощи средств исчисления высказываний иа формулы 0 — '. а = О, которая сама получается по схеме индукции. Нам остается вывести формулу Я (Ь) -~- Я (Ь'). Для этого рассмотрим два случая: Ь вЂ” ' а чь 0 и Ь вЂ” ' а = О.
С формальной точки эрвння это означает, что формулу Я (Ь) -~- Я (Ь') мы получим ы* 11 некОтОРые пОяснения пРинципивльнОГО хАРАктеРА 373 1гл. ЧП РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 372 средствами исчисления высказываний из двух формул: Ь вЂ” ' а чь 0- (Я (Ь) — Я (Ь')) Ь вЂ” ' а = 0-т- (Я (Ь) -+ Я (Ь')). Первая из этих формул получается средствами исчисления высказываний из формулы с — ' Ь' ~ Π— ~ с — Ь Ф О. А зта формула получается контрапозицией из формулы с — ' Ь = 0-~- с -' Ь' =- О, которая получается из равенств с †' Ь' = б(с †' Ь) и б (О) = О с использованием аксиомы равенства.
Для вывода второй формулы Ь вЂ” а = 0 -~ (Я (Ь) -э Я (Ь')) мы можем вообще не пользоваться посылкой Я (Ъ), а вывести ораву формулу Ь вЂ” ' а = 0 е- Я (Ь'). Действительно, зта формула, которая записывается в виде Ь вЂ” ' а = 0 -е- (Ь' — а ~ 0 8т с — ' Ь' ~ 0 -э с — а ~ 0), получается средствами исчисления выскааываний с помощью уже вншеденной формулы с — ' Ь' Ф 0 е- с — ' Ь ~ 0 и формулы Ь вЂ” ' а = 0 8т Ь' — ' а чь 0 е- (с — Ь ~ 0-+ с — ' а -,ь 0), .которую мы по правилу силлогизма получим из формул Ь = а -1- (с — ' Ь Ф 0 -е- с — ' а ~ 0) ;и Ь вЂ” ' а = 0 8т Ь' — ' а ~ 0-+. Ь = а. Первая из этих формул получается в результате подстановки в (в в). Таким образом, нам остается вывести только вторую формулу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
