# Second Principle of Finite Induction/Zero-Based

Jump to navigation
Jump to search

## Theorem

Let $S \subseteq \N$ be a subset of the natural numbers.

Suppose that:

- $(1): \quad 0 \in S$

- $(2): \quad \forall n \in \N: \paren {\forall k: 0 \le k \le n \implies k \in S} \implies n + 1 \in S$

Then:

- $S = \N$

## Proof

Define $T$ as:

- $T = \set {n \in \N : \forall k: 0 \le k \le n: k \in S}$

Since $n \le n$, it follows that $T \subseteq S$.

Therefore, it will suffice to show that:

- $\forall n \ge 0: n \in T$

Firstly, we have that $0 \in T$ if and only if the following condition holds:

- $\forall k: 0 \le k \le 0 \implies k \in S$

Since $0 \in S$, it thus follows that $0 \in T$.

Now suppose that $n \in T$; that is:

- $\forall k: 0 \le k \le n \implies k \in S$

By $(2)$, this implies:

- $n + 1 \in S$

Thus, we have:

- $\forall k: 0 \le k \le n + 1 \implies k \in S$

Therefore, $n + 1 \in T$.

Hence, by the Principle of Finite Induction:

- $\forall n \ge 0: n \in T$

That is:

- $T = \N$

and as $S \subseteq \N$ it follows that:

- $S = N$

$\blacksquare$