Math 115. Three Types of Induction

This handout discusses three types of induction, given below, and shows that they are equivalent. These types are:

Principle of Induction. Let P (n) be a statement (proposition) depending on a number n ∈ ℕ. Assume that (i). (basis statement) P (0) is true, and (ii). (inductive step) for all n ∈ ℕ, if P (n) is true, then P (n + 1) is also true. Then P (n) is true for all n ∈ ℕ.

Principle of Strong Induction. Let P (n) be a statement (proposition) depending on a number n ∈ ℕ. Assume that (i). (basis statement) P (0) is true, and (ii′). (inductive step) for all n ∈ ℕ, if P (k) is true for all k = 0, 1, …, n, then

P (n + 1) is also true. Then P (n) is true for all n ∈ ℕ.

Well-Ordering of ℕ. Every nonempty subset of ℕ has a smallest element.

A. Strong Induction implies Induction

Since n ≥ 0 , we have

P (k) is true for all k = 0, 1, …, n  implies  P (n) is true .

Therefore condition (ii) implies condition (ii′). This is because if (ii) is true and if P (k) is true for all k = 0, 1, …, n, then P (n) is true, and therefore by (ii) P (n + 1) is true. This verifies (ii′).

By a similar argument, the Principal of Strong Induction implies the Principle of Induction, because hypothesis (ii′) is weaker.

B. Induction implies Strong Induction

Let Q(n) be the statement “ P (k) is true for all k = 0, 1, …, n.” Then condition (i) for P implies condition (i) for Q. Also, assume that condition (ii′) holds for P . Then condition (ii) holds for Q(n) , because the truth of Q(n) implies that P (n + 1) is true (by (ii′)), and then Q(n + 1) is true because both Q(n) and P (n + 1) are true.

By induction, it then follows that Q(n) is true for all n, so P (n) is also true for all n.

C. Well-Ordering of ℕ implies Induction

We will prove this by contradiction. (This is called the “method of the minimal counterexample.”)

Let P be a proposition as in the statement of the Principle of Induction. Let S be the set of all n ∈ ℕ such that P (n) is false, and assume by way of contradiction that S is nonempty.

Then S has a smallest element by the well ordering property; call it m. We know by assumption (i) that m ≠ 0 . Then m − 1 ∈ ℕ, and since m is the smallest element of S, we have m − 1 ∉ S. Therefore P (m − 1) is true; therefore P (m) is also true by assumption (ii). This implies that m ∉ S, which gives a contradiction.

Thus, if P (n) is a proposition depending on n ∈ ℕ, and if P satisfies assumptions (i) and (ii) of the Principle of Induction, then P (n) is true for all n ∈ ℕ.

D. Strong Induction implies Well-Ordering of ℕ Suppose that the Principle of Strong Induction is true. In order to prove that ℕ is well ordered, we prove the following statement P (n)

by strong induction on n: If S is a subset of ℕ and n ∈ S, then S has a smallest element.

The basis step is true, because if 0 ∈ S then 0 is the smallest element of S, because there are no smaller elements of ℕ.

For the inductive step, suppose that P (k) is true for all k = 0, 1, …, n. To show that P (n + 1) is true, let S be a subset of ℕ that contains n + 1 . If n + 1 is the smallest element of S, then we’re done. Otherwise, S has a smaller element k, and P (k) is true by the inductive assumption, so again S has a smallest element.

Therefore, by strong induction, P (n) is true for all n ∈ ℕ. This implies the well-ordering of ℕ, because if S is a nonempty subset of ℕ, then pick n ∈ S. Since n ∈ ℕ, P (n) is true, and therefore S has a smallest element.

Comments 1. Parts C and D make part A redundant.

2. Part D is not really relevant, since well-ordering of ℕ is an axiom, but induction is a theorem. However, it may be useful if one has an axiom system in which induction is an axiom instead of well-ordering on ℕ. It is also useful for understanding why induction may or may not be valid for sets other than ℕ.

3. We also have principles of induction with ℕ replaced by ℤ_{>0} . Moreover, for any n_{0} ∈ ℤ, we can do induction on the set of all integers n ≥ n_{0} , merely by letting P (k) be the proposition that whatever is true for k + n_{0} .

4. In the statement of Strong Induction, (i) and (ii′) can be combined into the following statement:

(ii′′). (inductive step) for all n ∈ ℕ, if P (k) is true for all k ∈ ℕ with k < n,

then P (n) is also true.

Indeed, when n = 0 the hypothesis is vacuously true, which gives (i), and when n > 1 the condition is equivalent to (ii′) for n − 1 .