1. Натуральный ряд. Под натуральным рядом понимают последовательность чисел
0, 1, 2, 3, … .
В современной математике существование натурального ряда является одним из базовых постулатов. Постулируется существование множества N, удовлетворяющего определенным условиям – аксиомам натурального ряда.
Натуральный ряд – это множество Nвместе с отображением непосредственного следования s:N→N, s(x)=x’, удовлетворяющие следующим условиям (аксиомам).
1) Множество Nсодержит элемент, обозначаемый через 0, который не следует ни за каким элементом: 0∈Nи 0≠x’ каков бы ни был элемент x∈N.
2) Отображение непосредственного следования инъективно: если x’=y’, то x=y.
3) Аксиома индукции: единственное подмножество множества N, которое, во-первых, содержит 0 и, во-вторых, вместе с каждым элементом x содержит непосредственно следующий за ним элемент x’, – это само множество N.
Из первых двух условий следует, что последовательность
0, 0’, 0’’, 0’’’ …
не содержит повторяющихся элементов. В самом деле, если, например, 0’’=0’’’’, то, по аксиоме 2, 0’=0’’’ и 0=0’’, что противоречит аксиоме 1. Аксиома индукции говорит о том, что элементами этой последовательности исчерпывается все множество N. Таким образом, повторяя отображение s, можно, начав с 0, добраться до произвольного x∈Nза конечное число шагов. Используя привычные обозначения 0’=1, 0’’=2, 0’’’=3, …, получаем
N= {0, 1, 2, 3, …}.
2. Метод математической индукции. Многие математические доказательства основываются на аксиоме индукции, которую можно переформулировать следующим образом.
Принцип полной индукции. Пусть P – утверждение относительно натуральных чисел n такое, что
1) P верно для n=0;
2) из справедливости P для n=k следует справедливость P для n=k+1.
Тогда P верно для всех натуральных чисел.
Замечание. Чтобы показать, что эта формулировка следует из предыдущей, достаточно рассмотреть множество A={x∈N| P верно для x}.
Для доказательства в обратную сторону, множеству A⊂Nможно сопоставить свойство P «быть элементом множества A».
О доказательствах, основанных на аксиоме индукции, говорят, что они проведены методом математической индукции. Такие доказательства имеют следующую структуру:
•устанавливается справедливость P для n=0 (посылка индукции);
•предполагается, что P справедливо для некоторого произвольного, но фиксированного n=k (индуктивное предположение);
•доказывается, что из индуктивного предположения, следует, что P верно для n=k+1 (индуктивный шаг).
Примеры.Проведем два доказательства методом математической индукции.
1) Сумма первых натуральных чисел от 0 до n включительно равна 0,5n(n+1):
0+1+…+n = 0,5n(n+1).
Доказательство. Утверждение верно при n=0: имеем 0=0,5⋅0⋅(0+1) (посылка индукции).
Предположим, что доказываемое утверждение верно для n=k (индуктивное предположение), то есть
0+1+…+k = 0,5k(k+1). Покажем, что тогда оно верно и для n=k+1, то есть
0+1+…+k+(k+1) = 0,5(k+1)(k+2)
(индуктивный шаг). Сумма во втором равенстве отличается от суммы из первого равенства слагаемым k+1. Поэтому, в силу индуктивного предположения, получаем
0+1+…+k+(k+1) = 0,5k(k+1)+k+1 = 0,5(k+1)(k+2),
что и требовалось доказать.
В соответствии с принципом математической индукции, доказываемое утверждение верно для всех n.
2) Число подмножеств множества, содержащего n элементов, равно 2n.
Доказательство. Утверждение верно при n=0: пустое множество ∅ (единственное множество, содержащее 0 элементов) имеет ровно одно подмножество ∅.
Предположим теперь, что всякое множество с n=k элементами имеет 2k подмножеств, и покажем , что множество с n=k+1 элементами имеет 2k+1 подмножеств. Пусть A – произвольное множество с n=k+1 элементами. Так как k+1>0, то A не пусто и содержит хотя бы один элемент. Пусть a∈A. Разобьем совокупность всех подмножеств множества A на два класса. В класс U входят все подмножества, содержащие a, в класс V входят все подмножества, не содержащие a:
U={X⊂A | a∈X}; V={Y⊂A | a∉Y}. Положим A’=A\{a}. Множество A’ содержит k элементов, так что по индуктивному предположению, число его подмножеств равно 2k. Но подмножества множества A’ – это в точности подмножества множества A, не содержащие a. Следовательно, |V|=2k. Пара взаимно обратных отображений U→V, X→X\{a} и V→U, Y→Y∪{a} устанавливает между U и V взаимно однозначное соответствие, так что |U|=|V|=2k. Поэтому общее число подмножеств множества A составляет
|U|+|V|=2k +2k =2k+1,
что и требовалось доказать.
Иногда принцип полной индукции применяется в следующей форме.
Пусть P – утверждение относительно натуральных чисел n такое, что
1) P верно для n=n0;
2) из справедливости P(n) для n= n0, n0+1, …, n0+k следует справедливость P(n) для n= n0+k+1.
Тогда P верно для всех n≥ n0.
Принцип полной индукции в этой форме может быть сведен к предыдущей формулировке заменой утверждения P утверждением P’: утверждение P имеет место для всех t, таких, что n0≤t≤n.
Возможны и другие модификации принципа полной индукции.
Теорема.Всякое непустое подмножество натурального ряда содержит наименьший элемент.
Доказательство. Пусть A⊂N – непустое подмножество. Возможны два случая: 0∈A и 0∉A. В первом случае 0 является наименьшим элементом множества A. Рассмотрим второй случай. Предположим, что в A нет наименьшего элемента. Пусть A’ – это множество всех таких n, что ни одно число t из промежутка от 0 до n не содержится в A. Так как 0∉A, то 0∈A’. Далее, если k∈A’, то и k+1∈A’. В самом деле, в противном случае мы имели бы 0,1,…,k∉A, но k+1∈A – а это означает, что k+1 – наименьший элемент множества A в противоречие с предположением об отсутствии такового. По аксиоме индукции множество A’ совпадает с N. Но это находится в противоречии с предположением о том, что множество A не пусто.
