На любое натуральное число можно смотреть с двух точек зрения. Например, 3-три (количество), 3-третий (порядок). В курсе алгебры изучают порядковую теорию натуральных чисел. На множестве ℕ вводится отношение '(штрих) - “непосредственно следовать за”. Например, а' - элемент, непосредственно следующий за а.
Определение 54. Непустое множество ℕ с определённым на нём отношением ' (“непосредственно следующий за”) называется натуральным рядом чисел, а его элементы - натуральными числами, если выполняются следующие аксиомы, называемые аксиомами Пеано:
Р1: существует натуральное число, обозначаемое 1, которое непосредственно не следует ни за одним натуральным числом, то есть а'≠1, ℕ.
Р2: для любого натурального числа существует единственное натуральное число, непосредственно следующее за ним, то есть если а = b, то а' = b'.
Р3: любое натуральное число непосредственно следует не более чем за одним натуральным числом, то есть если а' =b ', то а =b.
Р4: пусть М⊆ℕ. Если 1М и из аМ всегда следует, что а'М, то М=ℕ – аксиома индукции.
Лемма 4. аℕ а' ≠ а.
Доказательство. Пусть М – множество всех натуральных чисел а, для которых а' ≠ а => М ℕ. Покажем, что 1 М. По аксиоме (Р1): 1'≠1=> 1М. Пусть аМ =>а' ≠ а => (по (Р3)) (а')' ≠ а’’ => а'М. Таким образом, по аксиоме (Р4) М =ℕ => а' ≠ а, ℕ.
Лемма доказана.
Теорема 6 (теорема Евклида).Множество всех натуральных чисел бесконечно.
Теорема 7 (основная форма метода математической индукции).
Пусть утверждение Т истинно при n=1 и из истинности утверждения Т при n=k следует истинность утверждения Т при n=k+1. Тогда утверждение Т истинно для любого nℕ.
Доказательство. Пусть М - множество всех натуральных чисел, для которых утверждение Т истинно. Покажем, что М=ℕ. По заданному М: Мℕ. Так как Т истинно при n=1, то 1М. По условию теоремы Т истинно при n=k. Тогда по условию Т истинно при n=k+1=k' =>k'М. По Р4: М=ℕ => Т - истинно ℕ.
Теорема доказана.
Теорема 8 (Обобщение первой формы метода математической индукции).
Пусть утверждение Т истинно при n=n0 и из истинности утверждения Т при n=k следует истинность утверждения Т при n=k+1. Тогда утверждение Т истинно для любого nℕ .
Теорема 9 (вторая форма метода математической индукции).
Пусть утверждение Т истинно при n=1 и из истинности утверждения Т для любого натурального числа, меньшего k, следует истинность утверждения Т для k. Тогда утверждение Т истинно для любого nℕ.
Теорема 10 (обобщение второй формы метода математической индукции).
Пусть утверждение Т истинно при и из истинности утверждения Т для любого натурального числа, меньшего k и большего либо равного , следует истинность утверждения Т для k. Тогда утверждение Т истинно для любого nℕ .
Замечание 11. Доказательство утверждений методом математической индукции состоит из трёх этапов:
1. Базис индукции. Проверим, что утверждение верно при n= 1 ()
2. Индукционное предположение. Предположим, что утверждение верно при n=k (для основной формы).
3. Индукционное доказательство. Докажем, что утверждение верно при n=k+1.