Let \(A\) be a nonempty finite simply ordered set.
Show that \(A\) has a largest element. [Hint: Proceed by induction on the cardinality of \(A\) .]
Show that \(A\) has the order type of a section of the positive integers.
Solution
- We induct on \(|A|\). If \(|A|=1\), the unique element is the largest element.
Assume every nonempty simply ordered set of cardinality \(n\) has a largest element, and let \(|A|=n+1\). Choose \(a\in A\). Then \(A-\{a\}\) has cardinality \(n\), so by induction it has a largest element \(m\). Since the order is simple, either \(a<m\) or \(m<a\). In the first case \(m\) is largest in all of \(A\); in the second case \(a\) is largest. Thus every nonempty finite simply ordered set has a largest element.
- We again induct on \(|A|\). A one-point ordered set is order-isomorphic to \(\{1\}\). Suppose the assertion holds for cardinality \(n\), and let \(|A|=n+1\). By part (a), \(A\) has a largest element \(M\). The subset \[ A'=A-\{M\} \] has cardinality \(n\), so by induction there is an order-preserving bijection \[ \phi:A'\longrightarrow\{1,\dots,n\}. \] Extend it by setting \[ \Phi(M)=n+1. \] Since every element of \(A'\) is less than \(M\), \(\Phi\) is an order-preserving bijection \[ A\longrightarrow\{1,\dots,n+1\}. \] Hence \(A\) has the order type of a section of the positive integers.