На множестве имеется отношение линейного порядка. Скажем, что n<m, если найдется натуральное число k такое, что n+k=m. Отношение n≤ m тогда получается из отношения строгого неравенства простой логической операцией: n≤ m означает, что либо n=m, либо n<m. Например, 5≤ 5 -- верное высказывание. Отметим фундаментальные свойства неравенств.
· Если n>m, то n+k>m+k для любого k. То же свойство справедливо для нестрогого неравенства.
· Если , то для любого k∈ ℕ. Если , то для любого .
Натуральные числа, а также множество среди других числовых систем обладают свойством полной упорядоченности: любое непустое подмножество натуральных чисел M имеет наименьший элемент min M. Докажем это утверждение.
Пусть и M≠ ∅ . Обозначим через [0,n] множество целых неотрицательных чисел больше либо равных 0 и меньше либо равных n. В начале, индукцией по n установим, что если пересечение M∩ [0,n] не пусто, то существует min M. База индукции -- случай n=0. Тогда min M=0. Пусть утверждение доказано для n, проверим, что тогда оно справедливо и для n+1. Имеем M∩ [0,n+1]≠ ∅ . Eсли, кроме того, M∩ [0,n]=∅ , то min M=n+1, иначе M∩ [0,n]≠ ∅ и можно воспользоваться предположением индукции. Итак, принцип индукции позволяет утверждать, что если M∩ [0,n]≠ ∅ для какого либо n∈ ℕ_0, то существует min M. Но для непустого множества M это условие заведомо выполняется, достаточно выбрать m∈ M и тогда m∈ M∩ [0,m], откуда M∩ [0,m]≠ ∅ .
Принцип полной упорядоченности эквивалентен принципу индукции. Сформулируем и докажем принцип индукции в другой редакции:
Пусть мы имеем серию утверждений: . Известно, что утверждение справедливо, а также известно, что если справедливо для всех k<n, то и тоже истинно. Тогда все утверждения верны.
Для обоснования этого утверждения рассмотрим множество M всех натуральных чисел m таких, что не верно. Если M непусто, то существует m=min M. Число m не равно 1 в силу истинности . Кроме того, для любого k<m утверждение справедливо, ибо k∉ M. Но тогда и верно. Получаем противоречие с тем, что ложно в силу того, что m∈ M. Противоречие показывает, что M=∅ , тем самым нет ни одного натурального k такого, что ложно. Значит все утверждения истинны.