Полная упорядоченность множества натуральных чисел.
ТЕОРЕМА 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 и предоставляется читателю.
