3. Применение метода оценок к вопросу о замене формул схемами.

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

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

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

Таким же способом можно доказать и то, что формула II 3):

не может быть замещена схемой

если мы ограничимся формулами групп Таким образом, даже если мы добавим схему в качестве формального правила вывода, то формула II 3) будет не выводима из формул I, II 1), 2), III.

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

Прежде всего, в силу этих определяющих равенств значение каждой из формул I, II 1), 2), III тождественно равно а. Затем, если значепия выражений тождественно равны а, то тогда и обладает этим свойством; таким образом, применяя

схему заключения

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

Но то же самое справедливо и в отношении присоединяемой схемы :

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

1. принимает значение тогда в любом случае принимает значение а.

2. принимает значение а. Так как по нашему предположению принимают значение а, то

и следовательно,

3. принимает одно из значений Так как принимают значение а, то должно принимать либо то же самое значение, что и либо значение а. То же самое справедливо и в отношении Так как теперь

то также принимает либо то же самое значение, что и либо значение а, так что

Тем самым мы установили, что еслп схему взять в качестве дополнительного правила вывода, то все формулы, выводимые из формул I, II 1), 2), III, будут тождественно принимать значение а. Между тем в отношении формулы II 3) это утверждение места не имеет. Действительно, если мы подставим в нее вместо значения то получим

В связи с проведенным доказательством независимости сделаем следующие замечания:

1. Если к рассматриваемым нами формулам I, II 1), 2), III добавить формулы группы V, то с помощью наших правил вывода и схемы можно будет вывести формулу II 3).

2. Если мы вместо схемы введем модифицированную схему

то с ее помощью формула II 3) может быть выведена из одних только формул группы

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

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

а из нее с помощью формул группы I может быть выведена и формула II 3).

Таким образом, формулу II 3) в нашей неявной характеризации конъюнкции можно заменить схемой

В случае дизъюнкции ситуация является не такой сложной, как в случае конъюнкции. Более того, здесь формула

может быть заменена схемой

аналогичной схеме Действительно, с помощью этой схемы формула III 3) может быть выведена из формул группы Для этого достаточно следующим образом применить схему :

Здесь обе первые формулы выводимы из формул группы I, а формула III 3) получается из заключительной формулы с помощью перестановки посылок импликации, чего можно добиться с помощью формул группы