x, y, z

Аксиома индукции и метод математической индукции

# 9 Апр 2015 18:21:31
Алексей
Как доказать эквивалентность аксиомы индукции и метода математической индукции?
# 9 Апр 2015 18:45:48
Evgeniy

Аксиома индукции утверждает, что любое подмножество натуральных чисел, которое содержит единицу $1$ и вместе с каждым своим числом $n$ содержит также «следующее» за ним $n'$, совпадает с множеством натуральных чисел. (на самом деле $n'=n+1$, но при аксиоматическом определении натуральных чисел сначала вводится понятие следующий, а уже на его основе определяется операция сложение $+$).

Формально аксиому индукции можно записать так:

$\forall M \subset \mathbb{N}\ \left( (1\in M \land (n\in M \Rightarrow n'\in M) \Rightarrow M=\mathbb{N}\right)$.

Пусть $M$ – множество натуральных чисел, для которых данная теорема $T$ верна, то есть $M=\{n\in {\Bbb N}: T(n)\}$. По условию индукции, теорема верна для $n=1$, то есть $1\in M$. По условию индукции, при условии, что теорема верна для $n$, теорема верна для следующего $n'$, следовательно, множество $M$ вместе с каждым числом $n$ содержит следующее $n'$, то есть $n\in M \Rightarrow n'\in M$. Из этого следует, что $M=\mathbb{N}$, то есть теорема верна для всех натуральных чисел.

Обратное легко доказать, если положить $T(n):=(n\in M)$, то есть теорема $T$ заключается в том, что $n\in M$.
# 9 Апр 2015 18:58:22
Алексей
Благодарю. А как доказать эквивалентности первого и второго принципа математической индукции?
1) Если какое-нибудь утверждении верно при n=1, и из верности для n следует верность для n+1, то это утверждении верно.
2) Любое непустое подмножество натуральных чисел содержит наименьшей элемент.
# 9 Апр 2015 19:15:39
Evgeniy

1) —> 2)

Уже показано, что 1) эквивалентно аксиоме индукции, поэтому будем использовать аксиому индукции.

Пусть $M = \{ b \in N: \forall a \in A\ (b \leqslant a)\}$ – множество всех нижних границ множества $A$.

Сначала покажем, что $M \ne {\Bbb N}$.

Допустим противное: $M = {\Bbb N}$. Тогда $\forall b \in {\Bbb N}\ \forall a \in A \ne \varnothing \ (b \leqslant a)$, что противоречит, например, неравенству $a < b = a + 1$.

Так как $\forall a \in A \subseteq {\Bbb N}\ (1 \leqslant a)$, то $1 \in M$.

Покажем, что $\exists {b_0} \in M\ ({b_0} + 1 \notin M)$. Допустим противное: $\forall b \in M\ (b + 1 \in M)$. Тогда по аксиоме индукции $M = {\Bbb N}$, что, как показано выше, невозможно.

Покажем, что это ${b_0} \in M$ есть искомое минимальное число множества $A$.

Из определения множества $M$ следует, что $\forall a \in A\ ({b_0} \leqslant a)$.

Остается показать, что ${b_0} \in A$.

Допустим противное: $\forall a \in A\ ({b_0} < a)$. Тогда $\forall a \in A\ ({b_0} + 1 \leqslant a)$, то есть ${b_0} + 1 \in M$, что противоречит ${b_0} + 1 \notin M$.

2) —> 1)

Пусть теорема $T$ верна при $n=1$, и если верна для $n$, то также верна для $n+1$, то есть $T(1)$ и $\forall n\in {\Bbb N}\ (T(n) \Rightarrow T(n+1))$.

Пусть $\overline{M}$ – множество натуральных чисел, для которых данная теорема $T$ не верна, то есть $\overline{M}=\{n\in {\Bbb N}: \lnot T(n)\}$.

Если теорема $T$ верна не для всех натуральных чисел, тогда $\overline{M} \ne \varnothing$. Поэтому в множестве $\overline{M}$ найдется наименьший элемент $n_0$. При этом $n_0\ne 1$, так как по условию теорема верна при $n=1$. Таким образом, $n_0>1$.

Так как $n_0$ наименьший элемент $\overline{M}$, то теорема верна для всех натуральных чисел $n<n_0$, в частности, теорема верна для $n_0-1<n_0$. (заметим, что разность $n_0-1$ определена, так как $n_0>1$). Но по условию, из того, что теорема $T$ верна для $n_0-1\ge 1$, следует, что она верна для $n_0$. Но $n_0 \in \overline{M}$.

Пришли к противоречию. Следовательно, $\overline{M} = \varnothing$, то есть теорема верна для всех натуральных чисел.
*Имя:
Заголовок:
[TeX-help] [ted]
  • formulas >

*Вычислите
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.