3. Установление ряда других независимостей с помощью модификации процедуры редукции.

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

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

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

На последнем шаге процедуры редукции, при рассмотрении выражений речь идет о том, чтобы для каждого такого выражения найти не содержащее переменной х

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

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

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

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

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

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

Цифра а) является цифрой первого рода тогда и только тогда, когда а является цифрой первого рода.

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

Если для каких-либо цифр равенство а является истинным, то для любой цифры с формулы

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

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

Теперь, с учетом этих предварительных замечаний, упомянутые четыре доказательства независимости могут быть представлены в следующем сокращенном виде:

1. Независимость формулы

Цифрами второго рода являются фигуры

Для равенств между произвольными цифрами и для неравенств между цифрами одного и того же рода берется обычное определение истинности и ложности. Если — цифра первого рода, цифра второго рода, то неравенство считается истинным, а неравенство ложным.

Формулы (а) и (а) имеют вид

Редукцией рассматриваемой формулы

является формула

При замене а посредством со эта формула оказывается ложной, так как со истинно, ложно и ложно.

2. Независимость формулы

Цифрами второго рода являются фигуры и .

Равенство является истинным, а неравенство ложным, если числа либо совпадают, либо отличаются друг от друга на четное число; в противном случае указанное равенство считается ложным, а неравенство — истинным.

Если — цифра первого рода, цифра второго рода, то неравенство считается истинным, а равенства и неравенство ложными. Формулы и имеют вид

В процедуре редукции должна быть модифицирована операция 3. Рассматриваемая формула

при замене переменных и с цифрами и оказывается ложной.

3. Независимость формулы

Цифрами второго рода являются фигуры . Равенства

считаются истинными или ложными в зависимости от того, совпадает число с числом или же нет. Из неравенств

первое истинно, а второе ложно, если число меньше, чем и второе истинно, а первое ложно, если число больше, чем оба неравенства ложны, если число совпадает с Равенство

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

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

В определении операции редукции различие между цифрами первого и второго рода не проявляется. Рассматриваемая формула

при замене а цифрой превращается в ложную.

4. Независимость формулы

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

Равенство

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

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

Если — цифра первого рода, цифра второго рода, то равенства а также неравенства всегда ложны; если же а отлично от 0, то истинно. Формулы имеют вид

В процедуре редукции должны быть модифицированы операции 2 и 4.

Рассматриваемая формула

при замене переменных цифрами оказывается ложной.

Тем самым для системы (А), так же как и для системы (В), нами установлена независимость каждой из ее аксиом от всех остальных.