Principle of Finite Induction

Theorem

Let $\left({S, \circ, \preceq}\right)$ be a naturally ordered semigroup.

Let $T \subseteq S$ such that $0 \in T$ and $n \in T \implies n \circ 1 \in T$.

Then $T = S$.

Generalisation

Let $p \in S$.

Let $T \subseteq S: x \in T \implies p \preceq x \land \left({x \in T \implies x \circ 1 \in T}\right)$.

Then $S \setminus S_p \subseteq T$ where $\setminus$ denotes set difference and $S_p$ denotes the set of all elements of $S$ preceding $p$.

As a proof technique

This theorem is often used as a proof technique where one defines a subset $T$ of $S$. The following steps are completed in order to show that this theorem can be used:

Basis for the Induction

The step that shows that the $p \in T$ is called the basis for the induction (also sometimes informally called the base case).

Induction Hypothesis

The assumption made that $n \in T$ is the induction hypothesis (also sometimes called the inductive hypothesis).

Induction Step

The step which shows that $n \in T \implies n \circ 1 \in T$ is called the induction step (also sometimes called the inductive step).

Proof

Aiming for a contradiction, suppose that $T \subset S$, i.e. $T$ is a subset of $S$ satisfying $T \ne S$.

Let $T\,' = S \setminus T$. Then $T\,'$ is non-empty by Set Difference with Proper Subset.

As $S$ is well-ordered, and $T\,' \subseteq S$, it follows that $T\,'$ has a smallest element $x$.

Now $p \in T \implies 0 \notin T\,'$, so $0 \prec x$.

By Precedes Next, $1 \preceq x$.

By the definition of a naturally ordered semigroup, $\exists y \in S: y \circ 1 = x$.

Again by Precedes Next, $y \prec x$.

Now $y \notin T\,'$ because $x$ is the smallest element of $T\,'$ and $y \prec x$. So $y \in T$.

But from the definition of $T$, $y \in T \implies y \circ 1 = x \in T$.

But then $x \in T\,' \implies x \notin T$, by the definition of $T\,'$. This contradicts the previous line.

So $T = S$.

$\blacksquare$

Proof of Generalisation

Let $T\,'$ be the union of $T$ and the set $S_p$ of all elements of $S$ preceding $p$.

Then the set $T\,'$ satisfies the conditions of the main theorem.

The same argument applies, and thus $T\,' = S$.

By Set Difference with Union is Set Difference, $S \setminus S_p = T \setminus S_p$.

By Set Difference Subset, $T \setminus S_p \subseteq T$, completing the proof.

$\blacksquare$

Natural Numbers

The principle is usually used in the following form:

$S \subseteq \N: 0 \in S \land \left({n \in S \implies n+1 \in S}\right) \implies S = \N$

and its generalisation:

$S \subseteq \N: k \in S \land \left({n \in S \implies n+1 \in S}\right) \implies S \supseteq \N \setminus \N_k$

In particular, the following is perhaps the most frequently used form of the principle:

$S \subseteq \N: 1 \in S \land \left({n \in S \implies n+1 \in S}\right) \implies S \supseteq \N^*$

As the Natural Numbers are a Naturally Ordered Semigroup, this follows directly from the above.

In this format it can be referred to as the Principle of Mathematical Induction, but that latter term is used for something slightly less abstract.

$\blacksquare$

Minimal Infinite Successor Set

Paul R. Halmos: Naive Set Theory (1960) uses $\omega$ for $\N$, where $\omega$ is defined as the minimal infinite successor set.

$S \subseteq \omega: \varnothing \in S \land \left({n \in S \implies n^+ \in S}\right) \implies S = \omega$

where $n^+$ is the successor of $n$.

The definition is demonstrated to be equivalent to the definition using $\N$ from Natural Numbers are Elements of the Minimal Infinite Successor Set, where it is shown that:

$\omega = \N$

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 12$: The Peano Axioms
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 16$: Theorem $16.5$, Corollary $16.5.1$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 20$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$: Theorem $\text{A}.6$