Полная упорядоченность множества натуральных чисел.

ТЕОРЕМА 3.11. Система является вполне упорядоченным множеством.

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

Очевидно, формула верна при , т. е.

Предположим, что для любого а и некоторого натурального числа верна формула

Тогда ибо в противном случае было бы наименьшим элементом множества А; поэтому . Так как, по теореме 3.1, из следует , то .

Значит, для всякого натурального верна импликация Следовательно, доказано, что формула верна для любого натурального b.

По предположению, множество А не пусто, следовательно, существует элемент . Полагая в формуле имеем Отсюда, поскольку , получаем , т. е. получено противоречие.

ТЕОРЕМА 3.12. Пусть А — подмножество множества N всех натуральных чисел. Если для каждого натурального выполняется условие

Доказательство. Предположим, что . Тогда множество не пусто и (по теореме 3.11) имеет наименьший элемент; следовательно, существует натуральное число, удовлетворяющее условиям:

В силу условия (1) верна импликация

По правилу отделения из (3) и (4) следует , что в силу (2) невозможно.

ТЕОРЕМА 3.13. Пусть — любой одноместный предикат на множестве N натуральных чисел. Если для всякого натурального числа

то для любого натурального

Доказательство теоремы 3.13 легко следует из теоремы 3.12 и предоставляется читателю.