Principle of Finite Induction/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S \subseteq \Z$ be a subset of the integers.

Let $n_0 \in \Z$ be given.


Suppose that:

$(1): \quad n_0 \in S$
$(2): \quad \forall n \ge n_0: n \in S \implies n + 1 \in S$


Then:

$\forall n \ge n_0: n \in S$


That is:

$S = \set {n \in \Z: n \ge n_0}$


Proof

Let $\Z_{\ge n_0} := \set {n \in \Z: n \ge n_0}$.

Aiming for a contradiction, suppose $S \ne \Z_{\ge n_0}$.

Let $S' = \Z_{\ge n_0} \setminus S$.

Because $S \ne \Z_{\ge n_0}$ and $S \subseteq \Z_{\ge n_0}$, we have that $S' \ne \O$.

By definition, $\Z_{\ge n_0}$ is bounded below by $n_0$.

From Set of Integers Bounded Below by Integer has Smallest Element, $S'$ has a minimal element.

Let $k$ be this minimal element of $S'$.

By $(1)$ we have that:

$n_0 \in S$

and so:

$n_0 \notin S'$

Hence:

$k \ne n_0$

and so:

$k > n_0$

It follows that:

$k - 1 \le n_0$

Because $k$ is the minimal element of $S'$:

$k - 1 \notin S'$

and so:

$k - 1 \in S$

But by $(2)$:

$\paren {k - 1} + 1 = k \in S$

So we have:

$k \in S$

and:

$k \notin S$

Hence by Proof by Contradiction $S = \Z_{\ge n_0}$.

$\blacksquare$


Sources