The Various Forms of Mathematical Induction

Simple Induction and Complete Induction

Let $\mathbf{N}$ denote the set of natural numbers, i.e., the positive integers $\left\{1,2,3,\dots \right\}$. The most basic understanding of $\mathbf{N}$ is tied up with the idea of counting. In relation to that understanding for each number $n\in \mathbf{N}$ there is a successor $s\left(n\right)$, which is the same thing as $n+1$ if one is allowed to speak about addition. $s$ is a function from $\mathbf{N}$ to $\mathbf{N}$ that is injective (or one-to-one): if $s\left(n_1\right)=s\left(n_2\right)$, then $n_1=n_2$. Moreover, every integer $n\in \mathbf{N}$ other than $1$ is the successor of a unique integer ($n-1$ if one is allowed to speak about subtraction). An integer $l$ is smaller than an integer $m$ if there is a finite sequence of integers $n_0,n_1,n_2,\dots n_k$ with $n_j=s\left(n_{j-1}\right)$, $1\le j\le k$, and $l=n_0$, $m=n_k$.

Definition 1.   A subset $S$ of $\mathbf{N}$ is an I1 subset of $N$ if

(a) $1\in S$.

(b_n) $s\left(n\right)\in S$ if $n\in S$.

Definition 2.   A subset $S$ of $\mathbf{N}$ is an I2 subset of $N$ if

(a) $1\in S$.

(c_n) $n\in S$ if $m\in S$ for each $m<n$.

Simple induction or “induction I” is the axiom about $\mathbf{N}$ that every I1 subset of $\mathbf{N}$ is all of $\mathbf{N}$. Complete induction or “induction II” is the axiom about $\mathbf{N}$ that every I2 subset of $\mathbf{N}$ is all of $\mathbf{N}$.

These two axioms are logically equivalent in the sense that if either of them is assumed (in the presence of other well known and less subtle properties of $\mathbf{N}$), then the other follows.

Without assuming either of these axioms the following is true:

Proposition 3.   Every I1 subset of $\mathbf{N}$ is also an I2 subset of $\mathbf{N}$.

Proof. If $S$ is an I1 set, then it is certainly the case that condition (a) is satisfied. The issue is why condition (c_n) must be satisfied. Let $n\in \mathbf{N}$ have the property that $m\in S$ for each $m<n$. If $n=1$, then by (a) $n\in S$. Otherwise, $n$ is the successor of a unique integer $n^{\prime }$, $n^{\prime }=n-1$, smaller than $n$. Since every integer smaller than $n$ is in $S$, $n^{\prime }$ is in $S$, and since $n=s\left(n^{\prime }\right)$ and $S$ is an I1 set, $n\in S$. Hence, $S$ satisfies condition (c_n).

Corollary 4.   If a statement can be proved using Induction I, then it can be proved using Induction II.

Proof. To say that a statement can be proved using Induction I means that the set $S$ of all values of $n\in \mathbf{N}$ for which the statement is true may be shown to be an I1 set. Likewise for Induction II and I2 sets. If a statement can be proved by induction I, then the set of integers for which it's true is an I1 set, and, therefore by the proposition, also an I2 set. Hence, the statement can be proved by induction II.

Now notice the contravariance:

Corollary 5.   If $N$ satisfies Induction II as an axiom, then $N$ satisifes Induction I as an axiom.

Proof. Re-stated this says that if every I2 set exhausts $\mathbf{N}$, then every I1 set exhausts $\mathbf{N}$. If $S$ is any I1 subset of $\mathbf{N}$, then, by the proposition, $S$ is an I2 subset of $\mathbf{N}$. Since $\mathbf{N}$ satisifes Induction II, $S$ must be all of $\mathbf{N}$. Hence, $\mathbf{N}$ satisfies Induction I.

So it was not hard to see that Induction II implies Induction I.

Understanding that Induction I implies Induction II is more subtle because, while the two are, in fact, equivalent, and, therefore, it is, in fact, true that every I2 subset of $\mathbf{N}$ is also an I1 subset of $\mathbf{N}$ (since, in fact, every I2 subset of $\mathbf{N}$ is all of $\mathbf{N}$), this fact cannot be proved in the rather straightforward way that it was shown that every I1 set is an I2 set.

Proposition 6.   Every I2 subset of $\mathbf{N}$ contains an I1 subset of $\mathbf{N}$ as a subset of itself.

Proof. Let $S$ be an I2 subset of $\mathbf{N}$. Let $T$ be the set of all $n\in \mathbf{N}$ with the property that every integer $m\le n$ is in $S$. Then certainly $1\in T$, and $T$ is a subset of $S$. Proving the proposition reduces to showing that $T$ is an I1 subset of $\mathbf{N}$.

Suppose that $n\in T$. Then every $m\le n$ is in $S$ by the definition of $T$. So every $m<n+1$ is in $S$ since there are no elements $m\in \mathbf{N}$ with $m\nleqq n$ and $m<n+1$. Since $S$ is an I2 set, $n+1\in S$, and therefore, $T$ is an I1 set.

Corollary 7.   If $N$ satisfies Induction I as an axiom, then $N$ satisfies Induction II as an axiom.

Proof. Re-stated this says that if every I1 set exhausts $\mathbf{N}$, then every I2 set exhausts $\mathbf{N}$. If $S$ is any I2 subset of $\mathbf{N}$, then, by the last proposition, $S$ contains an I1 subset $T$ of $\mathbf{N}$. Since $\mathbf{N}$ satisfes Induction I, $T$ must be all of $\mathbf{N}$. Since $T$ is a subset of $S$, $S$ must also be all of $\mathbf{N}$. Hence, $\mathbf{N}$ satisfies Induction II.

Theorem 8.   Simple induction and complete induction are equivalent as axioms about the natural numbers (in the presence of other well known properties of $\mathbf{N}$).

Corollary 9.   If a statement can be proved using Induction II, then it can be proved using Induction I.

Proof. To say that a statement can be proved using Induction II means that the set $S$ of all values of $n\in \mathbf{N}$ for which the statement is true may be shown to be an I2 set. By the last proposition, $S$ contains an I1 set $T$ as a subset. It is sufficient to know that the set of all values of $n\in \mathbf{N}$ for which the statement is true contains an I1 set.

The Well Orderedness of $\mathbf{N}$

Definition 10.   $\mathbf{N}$ is well-ordered if every non-empty subset of $\mathbf{N}$ contains a smallest member.

Proposition 11.   Complete induction implies well-orderedness.

Proof. Let $S$ be a non-empty subset of $\mathbf{N}$, and suppose that $S$ does not contain a smallest element. Then clearly $1\notin S$. Let $T$ be the set of all integers $m\in \mathbf{N}$ such that $m<n$ for each $n\in S$. Then certainly $1\in T$. Suppose $n\in \mathbf{N}$ has the property that $m\in T$ for each $m<n$. This means that $m<k$ for each $k\in S$ whenever $m<n$. If it were true that $n\in S$, then $n$ would be the smallest element of $S$ since every integer smaller than $n$ is strictly smaller than every element of $S$ and, therefore, not in $S$. This would be a contradiction. Hence, $n\notin S$. Since $n\notin S$, it follows that $n\in T$. Hence, $T$ is an I2 subset of $\mathbf{N}$, and, therefore, $T$ exhausts all of $\mathbf{N}$. But since $S$ is not empty, there is at least one integer $n_0\in S$, and $n_0\notin T$, a contradiction. Hence, the assumption that $S$ contains no smallest element leads to a contradiction.

Proposition 12.   Well-orderedness implies simple induction.

Proof. Let $S$ be an I1 subset of $\mathbf{N}$. If $S$ does not exhaust $\mathbf{N}$, then its complement $T=\mathbf{N}-S$ is a non-empty subset of $\mathbf{N}$. By well-orderedness $T$ contains a least element $t$. Since $S$ is an I1 set, one has $t\ne 1$, i.e., $t>1$. Then $t-1$ is an element of $\mathbf{N}$ smaller than the least element of $T$, which is to say that $t-1\notin T$ or, equivalently, $t-1\in S$. Since $S$ is an I1 set, it follows that $t\in S$, which contradicts $t\in T$. The contradiction was made possible by assuming that the I1 set $S$ fails to exhaust $\mathbf{N}$.

Since the two forms of induction are equivalent as axioms about $\mathbf{N}$, combining these two propositions, one has:

Theorem 13.   Well-orderedness as an axiom about $\mathbf{N}$ is equivalent to simple induction and to complete induction.