ordering on cardinalities
When there is a one-to-one function from a set to a set , we say that is embeddable in , and write . Thus is a (class) binary relation on the class of all sets. This relation is clearly reflexive and transitive. If and , then, by Schröder-Bernstein theorem, is bijective to , . However, clearly in general. Therefore fails to be a partial order. However, since iff they have the same cardinality, , and since cardinals are by definition sets, the class of all cardinals becomes a partially ordered set with partial order . We record this result as a theorem:
In ZF, the relation is a partial order on the cardinals.
In ZF, the following are equivalent:
the axiom of choice
is a linear order on the cardinals
Restating the second statement, we have that for any two sets , there is an injection from one to the other. The plan is to use Zorn’s lemma to prove the second statement, and use the second statement to prove the well-ordering principle (WOP).
- Zorn implies Statement 2:
Suppose there are no injections from to . We need to find an injection from to . We may assume that , for otherwise is an injection from to . Let be the collection of all partial injective functions from to . , as a collection of relations between and , is a set. , since any function from a singleton subset of into is in . Order by set inclusion, so becomes a poset. Suppose is a chain of partial functions in , let us look at . Suppose . Then and for some . Since is a chain, one is a subset of the other, so say, . Then , and since is a partial function, . This shows that is a partial function. Next, suppose . By the same argument used to show that is a function, we see that , so that is injective. Therefore . Thus, by Zorn’s lemma, has a maximal element . We want to show that is defined on all of . Now, can not be surjective, or else is a bijection from onto . Then is an injection, contrary to the assumption. Therefore, we may pick an element . Now, if , we may pick an element . Then the partial function given by
Since is injective by construction, . Since properly extends , we have reached a contradiction, as is maximal in . Therefore the domain of is all of , and is our desired injective function from to .
- Statement 2 implies WOP:
Since Zorn’s lemma and the well-ordering principles are both equivalent to AC in ZF, the theorem is proved. ∎