Second Principle of Finite Induction

Theorem

$S \subseteq \N: \N_1 \subseteq S \land \left({\N_k \subseteq S \implies \N_{k+1} \subseteq S}\right) \implies S = \N$

Basis for the Induction

The step that shows that the $\N_1 \subseteq S$ is called the basis for the induction (also sometimes informally called the base case).

Induction Hypothesis

The assumption made that $\N_k \subseteq S$ is the induction hypothesis (also sometimes called the inductive hypothesis).

Induction Step

The step which shows that $\N_k \subseteq S \implies \N_{k+1} \subseteq S$ is called the induction step (also sometimes called the inductive step).

Proof

Suppose the existence of:

$S \subseteq \N: \N_1 \subseteq S \land \left({\N_k \subseteq S \implies \N_{k+1} \subseteq S}\right)$

such that $S \ne \N$.

Now, consider the set $T = \N - S$. We know $T \ne \varnothing$ from our assumption $S \ne \N$.

By the Well-Ordering Principle, $T$ must contain a minimal (least) element: call it $a$.

We have that:

$\N_1 \subseteq S \implies 1 \in S \implies 1 \notin T \implies a \ne 1 \implies a > 1$

From the definition of $T$, we know that $a \notin S$, and as $a$ is the least element of $T$, it follows that:

$\forall k \in \N: 1 \le k < a: \N_k \subseteq S$

Now consider the set $\N_b: 0 < b = a-1 < a$.

As $b < a$ and $a$ is the least element of $T$, $b \notin T \implies b \in S \implies \N_b \subseteq S$.

But from the property of $S$ that $\N_k \subseteq S \implies \N_{k+1} \subseteq S$, we have:

$\N_b \subseteq S \implies \N_{b+1} \subseteq S \implies \N_a \subseteq S \implies a \in S$

So we have obtained a contradiction, and the assumption we made that $T \ne \varnothing$ is false, and therefore:

$\N - S = \varnothing \implies \N = S$

So we have $S \subseteq \N \land \N \subseteq S$, and so $S = \N$ as we wanted to prove.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 20 \alpha$