2. Доказательства независимости с помощью метода подстановок.

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

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

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

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

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

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

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

Если мы теперь вместо равенства всюду подставим выражение

то только что упоминавшаяся формула перейдет в

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

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

2. Независимость аксиомы от остальных аксиом системы (В) может быть установлена путем замены а выражением

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

Если бы аксиома была выводимой из остальных аксиом системы (В), то эта формула выводилась бы из системы (В) (даже из одних только аксиом равенства и аксиомы индукции), в то время как на самом деле она не верифицируема.

3. Заменив неравенство выражением

мы получим, что если бы аксиома была выводима из остальных аксиом систем (А) и (В), то формула

должна была бы выводиться из аксиом

аксиомы индукции и формулы

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

принимает значение «ложь». Тем самым аксиома оказывается независимой от всех остальных аксиом систем (А) и (В).

4. Независимость аксиомы от остальных аксиом системы (В) доказывается с помощью замены выражением

5. Независимость формулы от остальных аксиом системы (В) доказывается с помощью замены выражением

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

от остальных аксиом системы (А) доказывается с помощью замены выражением

Тем самым для системы (В) все необходимые доказательства независимости проведены. У системы (А) пока отсутствуют

доказательства независимости для формул

и