Category Archives: Mathematical Induction

Proof of Mathematical Induction

Well-Ordering Property of the Natural Numbers (axiom)
Every non-empty subset of natural numbers has a least element.
Principle of Mathematical Induction (theorem)
Let S be a subset of \( \mathbb{N} \). If S possess the following two properties:
(i) \( 1 \in S \)
(ii) \( \forall j \in \mathbb N, \left(j \in S \right) \rightarrow \left(j+1 \in S \right) \)

then \( S= \mathbb N \)

Proof: (Argue by contradiction by assuming \( S \neq \mathbb N \).)
If \( S \neq \mathbb N \) then \( \mathbb N \setminus S \) is nonempty by definition of complement.
\( \mathbb N \setminus S \) has a least element, k , by the Well-Ordering Principle of the Natural Numbers.
\( k \notin S \) by definition of the complement \( \mathbb N \setminus S \)
If \( 1 \in S \) then \( k>1 \) from the definition of \( \mathbb N \setminus S \).
\( k-1 \in S \).
By hypothesis (ii) if \( j=k-1 \in S \) then \( j+1= \left(k-1 \right) + 1 \in S \) which contradicts the assumption.

Consider a specific example
Assume \( S \neq \mathbb N \) and possess properties (i) and (ii)
Since hypothesis (i) demands that \( 1 \in S \) let \( S = \left \{1, 2, 3, 4, 5, 6 \right \} \)
\( \mathbb N \setminus S = \left \{7, 8, 9, 10, \dots , n, \dots \right \} \) by the definition of complement.
\( \mathbb N \setminus S \) has a least element \( k=7 \) by the Well-Ordering property of the natural numbers.
\( 7 \notin S \) by the definition of complement
\( 7 > 1 \) and since 7 is the least element of \( \mathbb N \setminus S \) then \( 7-1=6 \in S \), again, by the definition of the complement.
By hypothesis (ii) if \( 6 \in S \) then \( 6+1=7 \in S \) but this contradicts \( 7 \notin S \) which implies that the assumption \( S \neq \mathbb N \) is false.
Therefore, \( S= \mathbb N \)