§ 7. Изображение принципа наименьшего числа при помощи выражающей его формулы; равносильность этой формулы аксиоме индукции на основе прочих аксиом системы (В)
Для характеристики системы аксиом (В) мы приведем еще один вывод, а именно вывод из этой системы следующей формулы:
которая выражает принцип наименьшего числа, т. е. предложение, говорящее о том, что для любого высказывания, выполняющегося для какого-нибудь числа, всегда имеется наименьшее число, для которого это высказывание имеет место.
Кроме исчисления предикатов, мы используем для этого вывода аксиомы
выводимые формулы
и схему индукции, которая, как мы знаем, равносильна аксиоме индукции. Схему индукции мы будем применять к формуле
Посылку и заключение этой формулы мы для краткости обозначим символами
соответственно. Тогда рассматриваемое применение схемы индукции будет иметь вид
Нам нужно вывести формулы
и
Первая из них получается из формулы
, т. е. из формулы
которая может быть получена из
Для того чтобы получить вторую формулу, мы сначала с помощью
выведем формулу
которая сокращенно может быть записана в виде
Далее, из аксиомы
мы получим
а отсюда, в сочетании с предыдущей формулой, —
Теперь, формула
по правилам исчисления высказываний переводима в
далее, формула
т. е.
переводима в
и потому, используя формулу
мы получим
Но из основной формулы (b) подстановкой получается формула
В результате мы приходим к формуле
а из нее средствами исчисления высказываний получается формула
После этого можно применить схему индукции и получить формулу
От этой формулы мы легко можем перейти к искомой. Действительно, искомая формула имеет вид
а из полученной нами формулы, если вместо а подставить а, получается формула
Таким образом, будет достаточно вывести формулу
т. е.
Но эта формула может быть получена с использованием формулы
и основной формулы
Тем самым мы завершили вывод формулы
Заметим, что верно также и обратное, т. е. из этой формулы в сочетании с формулами
может быть выведена аксиома индукции. Для этого надо в формулу, выражающую принцип наименьшего числа, вместо именной формы
подставить
а затем к импликации, стоящей в области действия квантора всеобщности
применить правило контрапозиции. Тогда с использованием перечисленных формул и формулы
которая выводится с помощью второй аксиомы равенства, мы получим формулу
из которой с помощью простых преобразований и получается аксиома индукции.