Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 24
Текст из файла (страница 24)
Если п од мать этот г) См. с. 75 — 79. ч е от,„о малявка, рассмотрен«) Заметим, что этот формализм, в отличие от р ного выше на с. 79 — 80, включает в себя аксному равенства (Лз). з) См, с. 77, 1!4 исслглонлиик Арифметики пш! помощи *-символа !гл и е-СИМВОЛ И ФОРМАЛИЗАИИЯ ПРИИИИПА ИИДУКИИИ 1!5 е з! вопрос детально, то оказывается, что перспектив в этом направ.: ленни не имеется.
Во-первых, при добавлении схемы индукции возникают труд- ' ности с выполнением одной из операций, подготавливающих процедуру устранения е-символов. Именно, после возвратного переноса подстановок в исходные формулы нельзя будет произвести полное исключение свободных переменных, так как в результате этой операции схемы индукции теряют свой вид. Напомним, что в результате операции возвратного переноса подстановок, а также необходимых для этой операции мероприятий ') схема индукции 6 (О) 6 (а) — 6 (а') 6 (а) переходит в схему вида Я (О) 6 (а) -+ 6 (а') 6 (!) где 1 — какой-либо терм, а а — свободная переменная («в ыделе н н а я» переменная модифицированной схемы). Прн замене выделенной переменной каким-либо постоянным термом схема индукции в любом случае теряет свой вид.
Поэтому исключение свободных переменных с сохранением структуры доказательства может быть произведено только в отношении формульных, но никак не индивидных переменных. Само по себе это обстоятельство могло бы и не быть существенной помехой для процедуры устранения критических формул. Но если мы попытаемся произвести устранение прежним способом, то обнаружим„что на пути к этому имеется два серьезных препятствия. Первое из них связано с применением дедукционной теоремы.
В нашей процедуре устранения мы использовали тот факт, что если из некоторых формул Я„..., Я„получающихся в результате подстановки либо из собственных аксиом, либо из а-формулы, при добавлении формулы ч) можно средствами исчисления высказываний вывести некоторую формулу ц, то из формул Эх, ..., Азг с помощью средств исчисления высказываний можно будет вывести формулу ф-ьГке). Если мы теперь попытаемся распространить эту теорему на тот случай, когда в дедуктивный аппарат формализма наряду х) См. т.
1, с, 328. е) См, с. 40 — 47. с исчислением высказываний включается н схема индукции, то пам придется наложить на формулу г1! ограничение, потребовав, чтобы она ие содержала выделенных переменных каких-либо схем индукции. Действительно, последовательность формул, получающихся из какой-либо схемы Я (О) 6(а)-ь Я (гг') 6 (1) н результате импликативного добавления посылки гр, только тогда можно по общему рецепту, используя выводимость формулы (г41 -ь 6 (а)) -+ (р-ь 6 (гз')) из формулы ф-ь(Я(а)- 6(а')), дополнить до перехода, производимого при помощи схемы индукции, когда Р4) не содержит переменной п, ибо только при этом условии последовательность формул 4) -+ 6 (О) (Ч) -ь 6 (П)) -ь (г4) -~ (Я (а')) '41 -ч- 6 (1) имеет вид схемы индукции '). При применении дедукционной теоремы в процессе устранения критических формул посылка В (7) любой исключаемой на некотором шаге пропедуры критической формулы становится одной нз добавляемых исходных формул').
Глвершенно не ясно, как в этом случае добиться того, чтобы ни одна нз посылок критических формул — в том виде, как онн будут выглядеть после выполнения операции возвратного переноса подстановок, — не содержала выделенной переменной какой-либо из схем индукции. Вторая помеха заключается в том„ что в результате производимых замен к-термов какая-либо из схем индукции может поте- ') Простые примеры показыаают, что способ рассуждений, отвечающий схеме й (а) — й (0) ЯЗ (а) — (й (а) -ь й (а')) й (е) -~ й (1) нельзя считать имеющим общую применимость. Например, а качестве й (с) можно акать формулу с=о, а качесгне 23(с) — формулу с~О, а а качест.
ее г — терм 0'. ") См. с, 40 — 47. Я (0) 6(п)-ьа(а') 'Л (1) А (а) -ь е„А (х) чь а' в сочетании с аксиомой а ~ 0 -ь 6 (а) ' = а. а ~ 0 — 6 (а') = а, Формула ») См. т. 1, с. 325. 113 исслндовднин Анифмвтики пни помощи .символд »гл. и рять свой вид. Если, например, схема индукции имеет вид 6(е, 0) 6 (е, д) - 6 (е, о') 6 (», 1) где е — некоторый а-терм, не содержащий выделенной переменной и этой схемы, и если е заменить термом й(д), в котором д фигурирует в качестве составной части, то получающаяся при этом последовательность формул 6 (д (д), 0) 6 (й (о), д) -ь 6 (й (д), д') 6(й(п), 1) теряет вид схемы индукции.
В самом деле, ко всякой схеме ин- дукции предъявляется требование, чтобы она содержала выделенную пе-, ременную д только там, где эта переменная указана в качестве ' аргумента'). Мы можем теперь попытаться избежать этих трудностей, связанных с видом схемы индукции, взяв в целях распространения первой е-теоремы и нп-теоремы на арифметический формализм ' вместо схемы индукции аксиому индукции или какую-нибудь другую формализацию принципа полной индукции. Аксиома индукции, если мы при помощи е-символа устраним из нее квантор всеобщности, как это полагается делать по нашей процедуре исключения кванторов, приводит к формуле, совершенно неудобной в обращении.
Но поскольку арифметический формализм содержит аксиому равенства ()е), вместо этой формулы можно взять другую, более простую формулу как мы знаем, с использованием схемы индукции выводится из 4 З1 в-СИМВОЛ И ФОРМАЛИ9АЦИЯ ПРИНЦИПА ИНДУКЦИИ 117 рекурсивного определения 6(0)=0, 6(а')=а и формулы а=Ь- а'=Ь'. Ее можно рассматривать как разрешенную форму аксиомы а чь 0-+ =(х (х' = а).
В доказательстве обобщенной е-теоремы или соответственно нп-теоремы она не вызывает никаких осложнений, так как содержит единственную свободную индивидную переменную а и прн распределении значений для термов без переменных 6(д), получающемся с учетом содержательного истолкования рекурсивного определения функции 6, она является верифицируемой формулой.
Тот факт, что в результате добавления в качестве аксиом двух формул А (а) -~- е„А (х) ~ а' и а Ф 0-ь 6 (а)' = а схема индукции действительно оказывается производным правилом [или соответственно аксиома индукции — выводимой формулой»)1, устанавливается следующим образом. Нам нужно показать, что из двух формул Я (0) и»Л (а) -н- 'Л (а'), первая из которых не содержит переменной а, с помощью формул А (а) -+ н А (х) ,— ь а' и а ~ 0-+- 6 (а)' = а может быть выведена формула Л(а). Кроме четырех указанных формул, для вывода формулы 'Л(а) мы будем использовать только средства исчисления высказываний, а-формулу н аксиому равенства ()в), из которой, как мы уже знаем, выводятся формулы') а= 6-в-(А (Ь) — А (а)) и а=Ь- Ь=а. Не ограничивая общности, мы можем считать, что формула Л(а) не содержит переменной х, так как в противном случае мы смогли бы удалить эту переменную в исходных формулах путем ') Относительно вывода аксиомы индукции с помощью схемы индукции см.
т. 1, с. 327. в) См. т. 1, с. 212 н 214. 118 исслкдовднин дриомктики пои помощи символа 1гл и переименования, формулу. Мы начнем с а затем снова ввести ее в заключительную формулы а ~ 0 — б (а)' = а. Она может быть преобразована в формулу а=О 1/ б(а') =а, откуда мы в результате подстановки получим формулу (1) е„ ) Я (х) = 0 ~/ б (в„ ) Я (х))' = е ) Я (х) Пользуясь формулами Я (О) и а = Ь -+- (А (Ь) -» А (а)), мы получим формулу (2) е ) Я (х) = 0 — Я (а„) Я (х)). Из формулы А (а)-ье А (х)=~а', а отсюда, произведя контрапозицию и воспользовавшись формулой а = Ь -~- Ь = а, получим формулу (3) Ь'=и ) 6(х)-»6(Ь).
С другой стороны, из формулы 6(а)-ь 6(а') подстановкой полу- чается формула (4) Я (Ь) -ь Я (д'), а в результате использования (3») получается формула (5) Ь' = е„) Я (х) -ь. (Л (Ь') — 1- 6 (в „) Я (х))) . Формулы (3), (4) и (5), взятые совместно друг с другом, по пра- вилам исчисления высказываний дают формулу Ь'=е„)6(х)-»6(в )6(х)), произведя подстановку вместо переменной а, мы сначала полу- чим формулу А (б (е„ 1 Я (х))) -+. е А (х) ~ б (в„ ) Я (х))'.
Из этой формулы, которая, если терм б(е )6(х)) обозначить через Ь, сокращенно запишется в виде А(Ь)-+.е А(х) ФЬ', совершив подстановку вместо формульной переменной, мы полу- чим формулу ) Я (Ь) — » е „1 Я (х) ~ Ь', 4 ч1 е-СИМВОЛ И оопызЛИЗ»П1ия ппинципа индукции 11З т. е 6(е„) 6(х))' =е ) 6(х)-»6(е„) Л(х)). (б) Но из формул (1), (2) и (б) средствами исчисления высказываний получается формула Я (е ) Я (х)), а эта последняя при помощи е-формулы и с использованием средств исчисления высказываний') дает нам искомую формулу 6(а).
Таким образом, формула А (а) -ь а„А (х) оь а', взятая в сочетании с в-формулой и аксиомой а ~ О -» б (а) ' = а, действительно дает формализацию принципа полной индукции. Формуле А (а) -+. е,А (х) Ф а', ') См. с. ЗЗ. ') Формально связь между этими двумя принципами отчетливее всего может быть обрисована при помощи той формализации, которая для принципа наименьшего числа дается с помощью р-функции посредством формул ЭхА (х) — » А (р»А (х)) А (а) -+ р„А (х) ~ а (в ) и (р) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
