## mathematical induction

The principle of mathematical induction can be proved if the following axioms are assumed:

(A1) (The Well-Ordering Principle) Every non-empty subset of the natural numbers ℕ = {0, 1, 2, ...} has a least element.

(A2) Let m ∈ ℕ. If m > 0, then ∃n ∈ ℕ: m = n + 1.

Proof: Suppose

(1) P(0)

and

(2) For all n ∈ ℕ: P(n) ⇒ P(n + 1)

We wish to prove:

(3) P is true for all integer values of m.

Let S be the set of numbers for which P is false.

Using (1), we see that 0 ∉ S and is therefore not the minimal element of S.

Using (A2), if m > 0, then m = n + 1. If n ∈ S, then m, being bigger, cannot be the minimal element of S. But if n ∉ S, we have P(n) and, using (2), P(n + 1). It follows that m ∉ S and m cannot be the minimal element of S.

Thus, S has no minimal element, and by (A1) must be empty. P is therefore true for all integer values of m.

The axiom (A1) can be proved by the principle of mathematical induction. Indeed, given (A2), the two are equivalent.

Let S be a set of natural numbers. We want to prove that if S has no smallest element, then S is empty.

Proof: Consider a set S with no smallest element and let P(n) be the statement that n ∉ S.

(1) Since S has no smallest element, 0 ∉ S and so P(0) is true.

(2) Suppose that P(n) is true for some n. That is, n ∉ S. Since S has no smallest element, n + 1 ∉ S either and so we have P(n + 1).

By induction, we know that P(n) is true for all n, and therefore S = ∅.

Sources: wikipedia.org and Paul R Halmos, Naive Set Theory

cactuspear home