4.4: The Well-Ordering Principle

Last updated
Save as PDF

Page ID: 95439

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The penultimate theorem of this chapter is known as the Well-Ordering Principle. As you shall see, this seemingly obvious theorem requires a bit of work to prove. It is worth noting that in some axiomatic systems, the Well-Ordering Principle is sometimes taken as an axiom. However, in our case, the result follows from complete induction. Before stating the Well-Ordering Principle, we need an additional definition.

Definition 4.35. Let \(A\subseteq \mathbb{R}\) and \(m\in A\). Then \(m\) is called a maximum (or greatest element) of \(A\) if for all \(a\in A\), we have \(a\leq m\). Similarly, \(m\) is called minimum (or least element) of \(A\) if for all \(a\in A\), we have \(m\leq a\).

Not surprisingly, maximums and minimums are unique when they exist. It might be helpful to review Skeleton Proof 2.90 prior to attacking the next result.

Theorem 4.36. If \(A\subseteq \mathbb{R}\) such that the maximum (respectively, minimum) of \(A\) exists, then the maximum (respectively, minimum) of \(A\) is unique.

If the maximum of a set \(A\) exists, then it is denoted by \(\max(A)\). Similarly, if the minimum of a set \(A\) exists, then it is denoted by \(min(A)\).

Problem 4.37. Find the maximum and the minimum for each of the following sets when they exist.

\(\{5,11,17,42,103\}\)
\(\mathbb{N}\)
\(\mathbb{Z}\)
\((0,1]\)
\((0,1]\cap \mathbb{Q}\)
\((0,\infty)\)
\(\{42\}\)
\(\{\frac{1}{n}\mid n\in\mathbb{N}\}\)
\(\{\frac{1}{n}\mid n\in\mathbb{N}\}\cup\{0\}\)
\(\emptyset\)

To prove the Well-Ordering Principle, consider a proof by contradiction. Suppose \(S\) is a nonempty subset of \(\mathbb{N}\) that does not have a least element. Define the proposition \(P(n):=\)“\(n\) is not an element of \(S\)" and then use complete induction to prove the result.

Theorem 4.38. Every nonempty subset of the natural numbers has a least element.

It turns out that the Well-Ordering Principle (Theorem 4.38) and the Axiom of Induction (Axiom 4.1) are equivalent. In other words, one can prove the Well-Ordering Principle from the Axiom of Induction, as we have done, but one can also prove the Axiom of Induction if the Well-Ordering Principle is assumed.

The final two theorems of this section can be thought of as generalized versions of the Well-Ordering Principle.

Theorem 4.39. If \(A\) is a nonempty subset of the integers and there exists \(\ell\in \mathbb{Z}\) such that \(\ell\leq a\) for all \(a\in A\), then \(A\) contains a least element.

Theorem 4.40. If \(A\) is a nonempty subset of the integers and there exists \(u\in \mathbb{Z}\) such that \(a\leq u\) for all \(a\in A\), then \(A\) contains a greatest element.

The element \(\ell\) in Theorem 4.39 is referred to as a lower bound for \(A\) while the element \(u\) in Theorem 4.40 is called an upper bound for \(A\). We will study lower and upper bounds in more detail in Section 5.1.