§ 7. Изображение принципа наименьшего числа при помощи выражающей его формулы; равносильность этой формулы аксиоме индукции на основе прочих аксиом системы (В)

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

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

Кроме исчисления предикатов, мы используем для этого вывода аксиомы

выводимые формулы

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

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

Нам нужно вывести формулы

и

Первая из них получается из формулы , т. е. из формулы

которая может быть получена из

Для того чтобы получить вторую формулу, мы сначала с помощью

выведем формулу

которая сокращенно может быть записана в виде

Далее, из аксиомы мы получим

а отсюда, в сочетании с предыдущей формулой, —

Теперь, формула

по правилам исчисления высказываний переводима в

далее, формула т. е.

переводима в

и потому, используя формулу

мы получим

Но из основной формулы (b) подстановкой получается формула

В результате мы приходим к формуле

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

После этого можно применить схему индукции и получить формулу

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

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

Таким образом, будет достаточно вывести формулу

т. е.

Но эта формула может быть получена с использованием формулы и основной формулы Тем самым мы завершили вывод формулы

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

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

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

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