1.3 Well Ordering Principle | 1.3 Well Ordering Principle | Unit 1: Proofs | Mathematics for Computer Science | Electrical Engineering and Computer Science

Well Ordering Principle - Examples

A set of numbers is well ordered when each of its nonempty subsets has a minimum element. The Well Ordering Principle says that the set of nonnegative integers is well ordered, but so are lots of other sets. For example, the set \(r\mathbb{N}\) of numbers of the form \(rn\), where \(r\) is a positive real number and \(n \in \mathbb{N}\).

Indicate which of the following sets of numbers are well ordered.

The integers \( \geq -\sqrt{2} \)

The integers \( >\sqrt{2} \)

The rational numbers \( \geq \sqrt{2} \)

The set of rationals of the form \( \frac{1}{n} \) where \( n \) is a positive integer.

The set of rationals of the form \( \frac{1}{n} \) where \( n \) is a positive integer \( \leq 10^{100} \) (a googol)

The set \( G \) of rationals of the form \( \frac{m}{n} \) where \( m,n \) are positive integers and \( n\leq 10^{100} \)

The set, \( \mathbb{F} \), of fractions of the form \( \frac{n}{n+1} \)
\( \frac{0}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \dots \)

The set, \( W ::= \mathbb{N} \cup \mathbb{F} \) consisting of the nonnegative integers along with all the fractions of the form \( \frac{n}{n+1} \).

The set, \( R \), of real numbers with the property that every element of \( R \) has only finitely many elements of \( R \) below it. All the sets \( r\mathbb{N} \) for real \( r>0 \) have this property.

These sets have a minimum element, -1, and are well ordered by Corollary 2.4.3 in the course text.
Same as above.
These have no minimum element and so are not well ordered. They have no minimum element because \( \sqrt{2} \) is irrational. So if \( r \) is rational number \( \geq \sqrt{2} \), then in fact \( r > \sqrt{2} \). This means that \( r \) is not a minimum element \(\geq \sqrt{2}\) because the open-ended real interval \((\sqrt{2},r)\) has positive length, and therefore contains a rational number, \(q\), which is less than \(r\) and greater than \(\sqrt{2}\).
No minimum element.
This is a finite set of size a googol, and so is well ordered. Its minimum element is \(\frac{1}{g}\).
\(G\) has minimum element \(\frac{1}{g}\) and is well ordered.
To see why \(G\) is well ordered, note that all the numbers in \(G\) can be expressed with a common denominator. Let \[ d ::= g! ::= 2\cdot 3\cdot 4 \cdots (g-1) \cdot g \] Then each number in \(G\) can be written in the form \(\frac{k}{d}\) for some unique nonnegative integer numerator \(k\). So to find the minimum element in any nonempty subset of \(G\), express all the elements with the common denominator \(d\) and choose the one with minimum numerator, which exists by the WOP.
Zero is the minimum element. The minimum element of a nonempty subset of these numbers is simply the one with the minimum numerator when expressed in the form \( \frac{n}{n+1} \).
To show it is well ordered, we must show that every nonempty subset of \(W\) has a minimum element. But if a subset includes a fraction from \(S\), then, because all the elements in \(S\) are less than 1, the minimum element in the subset is the same as the minimum element among those in \(S\), which exists since \(S\) is well ordered. Otherwise, the subset consists solely of nonnegative integers and has a minimum element by the WOP.
To show that \( R \) is well ordered, let \( \mathbb{F} \) be a nonempty subset of \( R \), and suppose \( r \in \mathbb{F} \). We claim that \( \mathbb{F} \) has a minimum element. To see why, let \(S_{\leq r}\) be the set of elements in \( \mathbb{F} \) that are less than or equal to \( r \). A minimum number in \(S_{\leq r}\) is also a minimum number in \( \mathbb{F} \). But \(S_{\leq r}\) is finite by hypothesis, and therefore has a minimum element.