Let \(A\) and \(B\) be two sets. Using the well-ordering theorem, prove that either they have the same cardinality, or one has cardinality greater than the other. [Hint: If there is no surjection \(f: A \to B\), apply the preceding exercise.]
Solution
By the well-ordering theorem, choose well-orders on \(A\) and \(B\).
If \(B=\varnothing\), then either \(A=\varnothing\) and the two sets have the same cardinality, or \(A\ne\varnothing\), the empty map is an injection \(B\hookrightarrow A\), and there is no map \(A\to B\) at all, so \(A\) has greater cardinality than \(B\). Assume from now on that \(B\ne\varnothing\).
If there is no surjection \(A\to B\), then no section \(S_a\) of \(A\) maps onto \(B\) either: a surjection \(g:S_a\to B\) extends to a surjection \(A\to B\) by sending every point of \(A-S_a\) to a fixed element of \(B\). Hence E-MUN-10-10 applies with \(J=A\) and \(C=B\). Its recursively defined map \[ h(a)=\min(B-h(S_a)) \] is injective, because each new value is chosen outside the set of all earlier values. Thus there is an injection \(A\hookrightarrow B\). There cannot also be an injection \(B\hookrightarrow A\), for Schroeder–Bernstein would then give a bijection \(A\cong B\), hence in particular a surjection \(A\to B\), contrary to assumption. Therefore \(B\) has greater cardinality than \(A\).
If there is a surjection \(p:A\to B\), choose for each \(b\in B\) the least element of the nonempty fiber \(p^{-1}(b)\) in the chosen well-order of \(A\). This defines an injection \[ s:B\hookrightarrow A. \] If there is also an injection \(A\hookrightarrow B\), then Schroeder–Bernstein gives \(|A|=|B|\). If no such injection exists, then by definition \(A\) has greater cardinality than \(B\).
Thus exactly one of the following holds: \(A\) and \(B\) have the same cardinality, \(A\) has greater cardinality than \(B\), or \(B\) has greater cardinality than \(A\).