Comparability of cardinals from Zorn’s lemma

One of the basic consequences of the axiom of choice is that any two sets are comparable, that is, there is an injection from one into the other. The standard argument for this uses that choice is equivalent to the well-ordering theorem: One can prove (without choice) that any two well-ordered sets are comparable, and the well-ordering theorem states that any set is well-orderable.

If for some (foolhardy) reason (say, one is teaching an analysis or algebra course) one is interested in the result, but wants to avoid discussing the theory or well-orders, it seems desirable to have a proof based directly on Zorn’s lemma.

A few weeks ago, Sam Coskey and I found ourselves discussing such a proof. It turns out the argument, though not as well-known as may be expected, dates back at least to Chaim Samuel Hönig, and his short note Proof of the well-ordering of cardinal numbers, Proc. Amer. Math. Soc., 5, (1954), 312. MR0060558 (15,690a). It goes as follows: Let the sets and be given. Consider the collection of all partial injections from into . That is partial means that there is a such that . Order this collection by extension: iff . This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if is maximal, then is the domain of , or is its range. In either case, this gives us an injection from one of the sets into the other.

A natural extension of the idea allows us to recover that the class of cardinals is not just linearly ordered, but in fact well-ordered, but an additional use of the axiom of choice is needed now (namely, in the form: The product of non-empty sets is non-empty). Suppose first that is a set. We argue that one of the members of injects into all others. The proof is essentially the same as before: Let , and consider the family of all sequences such that for some and all , we have that is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element ; call the common domain of all the . If , we are done. Else (and this is where the additional use of choice comes in), for some , the range of is : Otherwise, we can pick and a sequence such that, for all , . But then, setting , we see that contradicts the maximality of . The result follows: Letting be such that is onto, we see that injects into , and injects into all sets in .

Finally, consider a (proper) class . Again, fix . Let be the collection of subsets of equipotent to sets in . Since is a set, the previous analysis applies, and we can find a that injects into all members of that inject into . It follows that actually injects into all members of . Otherwise, there is a that does not inject into. But then itself injects into , and therefore into . But this means that injects into after all.

Advertisement