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 A and B be given. Consider the collection of all partial injections f from A into B. That f is partial means that there is a C\subseteq A such that f:C\to B. Order this collection by extension: f\le f' iff f\subseteq f'. This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if f is maximal, then A is the domain of f, or B 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 \mathcal C is a set. We argue that one of the members of \mathcal C injects into all others. The proof is essentially the same as before: Let A\in \mathcal C, and consider the family of all sequences (f_B\mid B\in\mathcal C) such that for some A'\subset A and all B, we have that f_B:A'\to B is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element \vec f=(f_B\mid B\in \mathcal C); call A' the common domain of all the f_B. If A'=A, we are done. Else (and this is where the additional use of choice comes in), for some B, the range of f_B is B: Otherwise, we can pick a'\in A\setminus A' and a sequence (b_B\mid B\in\mathcal C) such that, for all B, b_B\in B\setminus f_B[A']. But then, setting f'_B=f_B\cup\{(a',b_B)\}, we see that (f'_B\mid B\in\mathcal C) contradicts the maximality of \vec f. The result follows: Letting B be such that f_B is onto, we see that B injects into A', and A' injects into all sets in \mathcal C.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: