Mathematical Induction

Mathematical Induction

Mathematical Induction. Let $S \subseteq \mathbb{N}$ with the following properties:
(a) $n_0 \in S$ for some $n_0 \in \mathbb{N}$.
(b) $k \in S \Longrightarrow k+1 \in S$.
Then $S = \mathbb{N} \backslash \{1, ..., n_0 - 1\}$.

    $n_0 = 1$로 택하면 흔히 볼 수 있는 수학적 귀납법이 된다. 

Proof. Suppose that $T := (\mathbb{N} \backslash \{1, ..., n_0 - 1\}) \backslash S \neq \emptyset$. Then $T \subseteq \mathbb{N} \cup \{0\}$. Then there is the least element $l \in T$ by Well-Ordering Principle. Since $n_0 \in S$, $n_0 < l \Longrightarrow n_0 \leq l-1 < l$. Then $l-1 \in S \Longrightarrow l \in S \bigotimes$. Hence $T = \emptyset \Longleftrightarrow S = \mathbb{N} \backslash \{1, ..., n_0 - 1\}$. $\blacksquare$