Appendix D — The Well-Ordering Property

One of the basic assumptions we make about the number system \(\N\) that underwrites our ability to use mathematical induction is what’s known as the Well-Ordered Axiom.

Axiom 4.1 (The Well-Ordering Axiom) Let \(S\) be any nonempty subset of \(\N\). Then \(S\) has a least element.

We treat this as an axiom, which means we assume it without proof. While not true as written for \(\Z\), we can adapt it to integers with an additional assumption.

Theorem 4.2 Let \(S\) be any nonempty subset of \(\Z\) that is bounded below by an element of \(\Z\). Then \(S\) has a least element.

Proof. Suppose \(n\in\Z\) is a lower bound on \(S\). Then define \[T=\{1-n+s\st s\in S\}\]

Then if \(t\in T\), \(t=1-n+s\) for some \(s\in S\), \[t=1-n+s\geq 1-n+n=1.\]

Thus all elements of \(T\) are positive integers, so \(T\subseteq\N\). So by Axiom 4.1, \(T\) has a least element \(m\); that is \(m\in T\) and \(m\leq t\) for all \(t\in T\). Thus \(m=1-n+k\) for some \(k\in S\), so \(m+n-1=k\in S\). And if \(s\in S,\) then \(1-n+s\in T,\) so \(m\leq1-n+s,\) and therefore \(k=m+n-1\leq s.\) Thus \(k\) is the least element of \(S.\)

Exercise 4.3 Would Theorem 4.2 be true if we replaced \(\Z\) with \(\Q\)? or \(\R\)? Give a proof or counterexample for each.