§ 6. Доказательства независимости

1. Невыводимость аксиомы индукции из формул системы (А).

В приведенных выше утверждениях всегда речь идет о формулах, не содержащих формульных переменных. С точки зрения выводимости таких формул системы (А) и (В), как мы показали, являются равносильными. Но эта равносильность немедленно перестает иметь место, как только мы допустим к рассмотрению формулы, в которых содержатся формульные переменные. В самом деле, уже аксиома индукции не выводима средствами системы (А).

Для того чтобы доказать это, мы расширим систему (А), присоединив к ней предикатный символ а также аксиомы

и

Расширенную таким образом систему мы обозначим символом Если предположить, что в системе (А) выводима аксиома индукции, то в системе (А должна оказаться выводимой формула

так как она получается из формул

по схеме индукции, а тем самым и с помощью аксиомы индукции, И тем не менее мы покажем, что формула не может быть выведена средствами системы

Это может быть проделано с помощью уже применявшегося однажды метода видоизменения понятия верифицируемости посредством обобщения понятий нумеричности, истинности, ложности и модификации процедуры редукции.

Для расширения запаса цифр мы прежде всего введем символ со и все фигуры, которые получаются из со путем присоединения правого нижнего индекса в виде одной или нескольких звездочек,

например, Для любого числа символом мы будем обозначать фигуру, получающуюся из со в результате присоединения звездочек; будет обозначать . В качестве цифр второго рода мы возьмем теперь фигуры , а также те фигуры которые получаются из них в результате однократного или многократного навешивания символа штриха. Нумерическими мы назовем такие формулы, которые либо являются равенствами или неравенствами, составленными из цифр, либо являются формулами вида с какой-либо цифрой а, либо оказываются построенными из формул этого рода с помощью связок исчисления высказываний. К прежним пунктам определения истинности и ложности мы добавим следующие новые. Любая формула вида

истинна. Формулы вида

ложны. Формула

истинна, если число совпадает с и ложна в противном случае.

всегда истинна,

всегда ложна. Для произвольных нумерических формул истинностные значения получаются на основе этих, а также прежних пунктов определения.

В качестве следствия из этого определения истинностных значений отметим, что для всякой цифры второго рода и для произвольного числа всегда можно указать такую цифру второго рода , для которой будет истинным равенство

Действительно, такой цифрой является

Теперь, чтобы процедуру построения редукции формулы без формульных переменных привести в соответствие с только что сформулированным определением истинностных значений

нумерических формул, в обычной процедуре редукции нужно будет произвести лишь следующую модификацию:

1. В четвертом преобразовании из числа тех, которым мы подвергаем выражение [при устранении квантора существования в какой-либо из самых внутренних составных частей вида ], каждый входящий в член где меньше, чем максимальное число навешенных на х штрихов, мы заменим посредством в соответствии с этим заменим посредством Если в результате этого несколько членов конъюнкции или дизъюнкции окажутся совпадающими, то возникшие при этом повторения мы удалим.

2. При рассмотрении членов

в которых не содержит в качестве конъюнктивного члена никакого равенства

после вынесения из-под квантора существования членов, не содержащих х, для оставшегося выражения

мы должны будем различать следующие случаи:

а) В конъюнкцию входят одни только неравенства; в этом случае мы поступим прежним образом.

б) В конъюнкцию в качестве члена входят как так и в этом случае выражение мы заменим формулой

в) Выражение имеет вид

в этом случае мы заменим его равенством

г) имеет один из следующих двух видов:

где представляет собой конъюнкцию неравенств

Тогда мы прежде всего заменим

конъюнкцией

а

соответственно конъюнкцией

и после этого заменим так же, как и раньше, причем в последнем из упомянутых случаев, когда имеется конъюнктивный член члены

могут быть опущены.

Для этой процедуры редукции снова можно будет доказать обе прежние леммы и с их помощью доказать теорему об однозначности и теорему о частичной редукции. Кроме того, мы можем дословно перенести наше прежнее определение понятия верифицируемости, причем под цифрами теперь надо будет понимать цифры первого и второго рода.

С помощью элементарных рассуждений о числах теперь легко будет убедиться, что в соответствии с этим определением все аксиомы системы за исключением являются верифицируемыми. Для аксиомы также можно будет, аналогично предыдущему, показать, что всякая формула без формульных переменных, получающаяся из нее в результате подстановки, является верифицируемой. При этом возникнет некоторое расхождение с прежним рассуждением (как, впрочем, уже и в доказательствах теорем о редукции), поскольку из истинности нумерического равенства теперь нельзя будет сделать вывод о совпадении а с а вместо этого нужно будет пользоваться теоремой о том, что если суть цифры, для которых истинно, произвольная цифра, то формулы

соответственно имеют те же самые истинностные значения, что и формулы

Опираясь на эти утверждения об аксиомах, с помощью теоремы о частичной редукции можно будет показать, что всякая формула,

выводимая из системы (А и не содержащая формульных переменных, является верифицируемой

По отсюда дедует, что формула не может быть выведена из системы так как она не верифицируема. Действительно, если мы заменим в ней переменную а цифрой , то она перейдет в ложную формулу

Тем самым невыводимость аксиомы индукции из системы (А) установлена.

В качестве следствия мы можем получить отсюда и независимость аксиомы индукции от остальных аксиом системы (В); действительно все эти аксиомы, как мы знаем, выводимы из системы (А).