The Well-Ordering Principle - Induction

Mathematical Writing - Vivaldi Franco 2014

The Well-Ordering Principle
Induction

Franco Vivaldi1

(1)

School of Mathematical Sciences, Queen Mary, University of London, London, UK

Franco Vivaldi

Email: f.vivaldi@qmul.ac.uk

Induction is a fundamental method of proof, used in every corner of mathematics. It is applicable to statements of the form

$$\begin{aligned} \forall n\in \mathbb {N},\quad {\fancyscript{P}}(n) \end{aligned}$$

(8.1)

where $${\fancyscript{P}}$$ is a predicate over $$\mathbb {N}$$. This sentence says that all natural numbers have property $${\fancyscript{P}}$$.

Induction is first met in the proof of summation identities and inequalities:

1

$$\sum _{k=0}^n x^k=\frac{1-x^{n+1}}{1-x}$$

$$x\not =1$$

Sum of geometric progression

2

$$(x+y)^n=\sum _{k=0}^n{n\atopwithdelims ()k}x^ky^{n-k}$$

Binomial theorem

3

$$(1+x)^n\geqslant 1+nx$$

$$x>-1$$

Bernoulli inequality1

4

$$\prod _{k=1}^n x_k \leqslant \left( \frac{1}{n} \sum _{k=1}^nx_k \right) ^n$$

$$x_{k} >0$$

Arithmetico-geometric



mean (AGM) inequality

5

$$\left| \sum _{k=1}^n x_ky_k\right| ^2 \leqslant \sum _{k=1}^n|x_k|^2\sum _{k=1}^n|y_k|^2$$

Cauchy-Schwarz inequality2

(The variables are complex numbers in 1, 2, and real numbers in 3, 4, 5.)

The expression (8.1) unfolds into an infinite sequence of boolean expressions:

$$ {\fancyscript{P}}(1),\, {\fancyscript{P}}(2),\, {\fancyscript{P}}(3),\, \ldots $$

and to prove it we must show that all expressions in the sequence are true:

$$ {\textsc {{T}}},\, {\textsc {{T}}},\, {\textsc {{T}}},\,\ldots . $$

For instance, the Bernoulli inequality unfolds as follows:

$$ 1+x\geqslant 1+x,\quad (1+x)^2\geqslant 1+2x,\quad (1+x)^3\geqslant 1+3x,\quad \,\ldots $$

each inequality being valid for all real numbers $$x>-1$$.

A special form of mathematical argument is needed for this purpose, called mathematical induction. It takes several forms, and we will examine four:

·  ($$A$$) The well-ordering principle.

·  ($$B$$) The infinite descent method.

·  ($$C$$) The induction principle.

·  ($$D$$) The strong induction principle.

We will show that these principles are equivalent in the sense that any one of them implies all the others. The different forms of the principle are appropriate for different situations.

The term mathematical induction was coined by De Morgan around 1840. The attribute ’mathematical’ is used to differentiate this concept from the homonymous concept in philosophy, which has a different meaning.3 The induction principle—in any of the above forms—is one of the five Peano axioms 4 which characterise the set $$\mathbb {N}$$ of natural numbers.

8.1 The Well-Ordering Principle

The well-ordering (or least counter example) principle states that

·  ($$A$$) Every non-empty set of natural numbers contains a least element.

This principle is clearly false for subsets of $$\mathbb {Z},\mathbb {Q}$$ or $$\mathbb {R}$$, and, less trivially so, for subsets of $$\mathbb {Q}^+$$ or $$\mathbb {R}^+$$, or of any real or rational interval. A possible strategy for proving (8.1) is to combine well-ordering with contradiction. Such a proof will begin as follows:

PROOF. Suppose (8.1) is false. Let $$k$$ be the least natural number $$n$$ for which $${\fancyscript{P}}(n)$$ is false. ...

Then with this $$k$$ we try to deduce a contradiction, using the knowledge that $${\fancyscript{P}}(n)$$ is true for $$n=1,\ldots , k-1$$. The integer $$k$$ defined in the proof exists by virtue of the well-ordering principle: it is the least element of the set $$\{n\in \mathbb {N}\,:\,\lnot {\fancyscript{P}}(n)\}$$, which is a subset of $$\mathbb {N}$$. By assumption, this subset is non-empty.

Let us apply this strategy to some specific problems.

Proposition

If $$n \geqslant 7$$, then $$n! > 3^n$$.

PROOF. Suppose this statement is false, and let $$k$$ be the least integer $$n\geqslant 7$$ such that $$n! \leqslant 3^n$$. We know that $$k > 7$$, since

$$ 7! = 5040 > 2187 = 3^7. $$

Put $$j=k-1$$. Then $$j \geqslant 7$$, and hence $$j! > 3^j$$ by choice of $$k$$. So

$$ k! = (j+1)j! > (j+1)3^j > 3\cdot 3^j = 3^k $$

contradicting the choice of $$k$$. $$\square $$

The initial verification that $$k>7$$ creates enough room for the principle to work. We note that $$6!=720$$ and $$3^6=729$$, so the inequality $$n\geqslant 7$$ is the best possible one. Under these circumstances, we say that $$n\geqslant 7$$ is a strict bound. Our next statement is more substantial:

Theorem

Every integer greater than 1 is a product of one or more prime numbers.

PROOF. Suppose the statement is false, and let $$k$$ be the smallest integer greater than 1 which is not a product of primes. Then $$k$$ is not prime, so $$k = mn$$ for two smaller integers $$m, n \geqslant 2$$. Since $$m$$, $$n$$ are smaller than $$k$$ and greater than 1, they are products of prime numbers. So $$k=mn$$ is also a product of primes, which contradicts the choice of $$k$$. $$\square $$

This form of mathematical induction can be very effective. The assumption that $$k$$ is the smallest counterexample puts the maximum amount of information on the table; it gives us the feeling that we are examining a concrete object.