23. Принцип математической индукции

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

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

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

Если бы существовало натуральное число х, для которого утверждение Т не имело бы силы, то множество всех таких чисел было бы непустым и в силу утверждения в нем имелось бы наименьшее число . Это число было бы натуральным числом, для которого утверждение Т не имело бы

силы, и из условия относительно утверждения Т (что оно справедливо для числа 1) следовало бы, что Утверждение Т было бы, следовательно, справедливо для натурального числа что, по смыслу условия, принятого для утверждения Т, влечет за собой его справедливость для числа что противоречит предположению. Утверждение Т должно быть, следовательно, справедливо для любого натурального числа. Мы доказали таким образом, что из утверждения вытекает принцип математической индукции.

Допустим теперь справедливость принципа математической индукции. Пусть есть некоторое произвольное непустое множество натуральных чисел. Допустим, что в множестве нет наименьшего числа. Очевидно, что в таком случае число 1 не принадлежит множеству

Обозначим через Т утверждение (в котором говорится о натуральном числе «Ни одно натуральное число, меньшее или равное не принадлежит множеству Утверждение Т очевидным образом справедливо для числа Если утверждение Т справедливо для натурального числа то оно имеет силу и для числа так как в противном случае число было бы, как легко видеть, наименьшим числом множества что противоречит предположению о том, что множество не имеет наименьшего числа.

Следовательно, на основании принципа индукции утверждение Т справедливо для любого натурального числа . Но в таком случае из утверждения Т вытекает, что множество является пустым, что противоречит предположению.

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

Тем самым мы доказали, что утверждение равносильно принципу математической индукции.