An Introduction to Proof via Inquiry-Based Learning

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.

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.

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

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.