8.4: The Natural Numbers are Well-Ordered

Induction is a very powerful tool, but it is sometimes hard to apply (and there are many different versions to keep track of, as we saw in the preceding section). In this section, we demonstrate a closely related technique that is often less cumbersome to use.

Definition \(8.4.1\).

Let \(S \subset \mathbb{R}\) and \(a \in \mathbb{R}\). We say \(a\) is the smallest element of \(S\) iff:

• \(a \in S\), and
• \(\forall s \in S\), \(a \leq s\).

Example \(8.4.2\).

• The smallest element of \(\{2,4,6,8\}\) is 2.
• The smallest element of \(\{12,9,18,5,13\}\) is 5.

It is important to realize that not every set of numbers has a smallest element:

Exercise \(8.4.3\).

Show that the given set does not have a smallest element.

1. \(\mathbb{Z} [Hint: If \(n \in \mathbb{Z}\), then \(n − 1 < n\).]
2. \(\mathbb{R}^{+}=\{x \in \mathbb{R} \mid x>0\}\) [Hint: If \(x \in \mathbb{R}^{+}\), then \(x / 2 \in \mathbb{R}^{+}\).]
3. \(\varnothing\) [Hint: A set with no elements cannot have a smallest element.]

This problem does not arise for subsets of \(\mathbb{N}\):

Theorem \(8.4.4\) (\(\mathbb{N}\) is Well-Ordered).

Every nonempty subset of \(\mathbb{N}\) has a smallest element.

This rather obvious observation is as powerful as all of the many variations of the Principle of Mathematical Induction. Namely, if \(P(n)\) can be proved for all \(n \in \mathbb{N}^{+}\) by using any one of the many forms of Mathematical Induction, then it can also be proved by applying Theorem \(8.4.4\) to the set \[S=\left\{n \in \mathbb{N}^{+} \mid \neg P(n)\right\} .\]

More precisely, suppose \(P(n)\) is not true for all \(n \in \mathbb{N}^{+}\). Then the fact that \(\mathbb{N}\) is well-ordered tells us that there is a smallest \(n\), such that \(P(n)\) is not true. This means that:

1. \(P(n)\) is not true, but
2. \(P(k)\) is true for all \(k < n\) (such that \(k \in \mathbb{N}^{+}\)).

Obtaining a contradiction from these two assumptions will complete the proof that \(P(n)\) is true for all \(n \in \mathbb{N}^{+}\).

Example \(8.4.5\) (Alternate Proof of Example \(8.3.3\)).

Suppose it is not true that \(F_{n} < 2^{n}\) for all \(n \in \mathbb{N}^{+}\). (This will lead to a contradiction.) Then, since \(\mathbb{N}\) is well-ordered, there is a smallest \(n\), such that \(F_{n} \geq 2^{n}\). This means that

1. \(F_{n} \geq 2^{n}\), but
2. \(F_{k} < 2^{k}\) for all \(k < n\) (such that \(k \in \mathbb{N}^{+}\)).

Note that, since \[F_{1}=1<2=2^{1} \quad \text { and } \quad F_{2}=1<4=2^{2} ,\]

we see from (i) that \(n \notin\{1,2\}\), so \(n \geq 3\). Therefore \(n − 1 \in \mathbb{N}^{+}\) and \(n − 2 \in \mathbb{N}^{+}\). Then, since \(n − 1\) and \(n − 2\) are less than \(n\), we see from (ii) that \[(*) \quad F_{n-1}<2^{n-1} \text { and } F_{n-2}<2^{n-2} .\]

Now, we have \[\begin{aligned}
F_{n} &=F_{n-1}+F_{n-2} & & \text { (definition of Fibonacci sequence) } \\
&<2^{n-1}+2^{n-2} & &((*): \text { the minimality of } n) \\
&<2^{n-1}+2^{n-1} & &(n-2<n-1) \\
&=2^{n} & & .
\end{aligned}\]

This contradicts (i).

Exercise \(8.4.6\).

1. Prove \(F_{n+4} + F_{n} = 3F_{n+2}\) for all \(n \in \mathbb{N}^{+}\).
2. Prove \(2^{n} > n^{2}\) for every \(n \geq 5\).
3. Prove \(3^{n} > 2^{n} + 2n\), for every \(n \geq 2\).

Exercise \(8.4.7\).

1. Show that the Principle of Mathematical Induction (\(8.1.2\)) follows from the fact that \(\mathbb{N}\) is well-ordered.
2. Use induction to prove Theorem \(8.4.4\). [Hint: Define \(P(n)\) to be the assertion “If \(S \subset \mathbb{N}\) and \(S\) contains an element \(\leq n\), then \(S\) has a smallest element.”]