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.
Let \(A\subseteq \mathbb{R}\) and \(m\in A\text{.}\) Then \(m\) is called a maximum (or greatest element) of \(A\) if for all \(a\in A\text{,}\) we have \(a\leq m\text{.}\) Similarly, \(m\) is called minimum (or least element) of \(A\) if for all \(a\in A\text{,}\) we have \(m\leq a\text{.}\)
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.
If the maximum of a set \(A\) exists, then it is denoted by \(\tcboxmath{\max(A)}\text{.}\) Similarly, if the minimum of a set \(A\) exists, then it is denoted by \(\tcboxmath{\min(A)}\text{.}\)
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)\coloneqq\) “\(n\) is not an element of \(S\)” and then use complete induction to prove the result.
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.
If \(A\) is a nonempty subset of the integers and there exists \(l\in \mathbb{Z}\) such that \(l\leq a\) for all \(a\in A\text{,}\) then \(A\) contains a least element.
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\text{,}\) then \(A\) contains a greatest element.
The element \(l\) 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\text{.}\) We will study lower and upper bounds in more detail in Section 5.1.
