ordering on cardinalities
When there is a onetoone function from a set $A$ to a set $B$, we say that $A$ is embeddable in $B$, and write $A\le B$. Thus $\le $ is a (class) binary relation^{} on the class $V$ of all sets. This relation is clearly reflexive^{} and transitive^{}. If $A\le B$ and $B\le A$, then, by SchröderBernstein theorem^{}, $A$ is bijective^{} to $B$, $A\sim B$. However, clearly $A\ne B$ in general. Therefore $\le $ fails to be a partial order^{}. However, since $A\sim B$ iff they have the same cardinality, $A=B$, and since cardinals are by definition sets, the class of all cardinals becomes a partially ordered set^{} with partial order $\le $. We record this result as a theorem:
Theorem 1.
In ZF, the relation $\mathrm{\le}$ is a partial order on the cardinals.
With the addition^{} of the axiom of choice^{}, one can show that $\le $ is a linear order on the cardinals. In fact, the statement “$\le $ is a linear order on the cardinals” is equivalent^{} to the axiom of choice.
Theorem 2.
In ZF, the following are equivalent:

1.
the axiom of choice

2.
$\le $ is a linear order on the cardinals
Proof.
Restating the second statement, we have that for any two sets $A,B$, 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 wellordering principle (WOP).
 Zorn implies Statement 2:

Suppose there are no injections from $A$ to $B$. We need to find an injection from $B$ to $A$. We may assume that $B\ne \mathrm{\varnothing}$, for otherwise $\mathrm{\varnothing}$ is an injection from $B$ to $A$. Let $P$ be the collection^{} of all partial injective functions from $B$ to $A$. $P$, as a collection of relations between $B$ and $A$, is a set. $P\ne \mathrm{\varnothing}$, since any function from a singleton subset of $B$ into $A$ is in $P$. Order $P$ by set inclusion, so $P$ becomes a poset. Suppose $F$ is a chain of partial functions^{} in $P$, let us look at $f:=\bigcup F$. Suppose $(a,b),(a,c)\in f$. Then $(a,b)\in p$ and $(a,c)\in q$ for some $p,q\in F$. Since $F$ is a chain, one is a subset of the other, so say, $p\subseteq q$. Then $(a,b)\in q$, and since $q$ is a partial function, $b=c$. This shows that $f$ is a partial function. Next, suppose $(a,c),(b,c)\in f$. By the same argument used to show that $f$ is a function, we see that $a=b$, so that $f$ is injective. Therefore $f\in P$. Thus, by Zorn’s lemma, $P$ has a maximal element^{} $g$. We want to show that $g$ is defined on all of $B$. Now, $g$ can not be surjective, or else $g$ is a bijection from $\mathrm{dom}(g)$ onto $A$. Then ${g}^{1}:A\to B$ is an injection, contrary to the assumption^{}. Therefore, we may pick an element $a\in A\mathrm{ran}(g)$. Now, if $\mathrm{dom}(g)\ne B$, we may pick an element $b\in B\mathrm{dom}(g)$. Then the partial function ${g}^{*}:\mathrm{dom}(g)\cup \{b\}\to A$ given by
$${g}^{*}(x)=\{\begin{array}{cc}g(x)\hspace{1em}\text{if}x\in \mathrm{dom}(g),\hfill & \\ a\hspace{1em}\text{if}x=b.\hfill & \end{array}$$ Since ${g}^{*}$ is injective by construction, ${g}^{*}\in P$. Since ${g}^{*}$ properly extends $g$, we have reached a contradiction^{}, as $g$ is maximal in $P$. Therefore the domain of $g$ is all of $B$, and is our desired injective function from $B$ to $A$.
 Statement 2 implies WOP:

Let $A$ be a set and let $h(A)$ be its Hartogs number. Since $h(A)$ is not embeddable in $A$, by statement 2, $A$ is embeddable in $h(A)$. Let $f$ be the injection from $A$ to $h(A)$ is injective. Since $h(A)$ is an ordinal^{}, it is wellordered. Therefore, as $f(A)$ is wellordered, and because $A\sim f(A)$, $A$ itself is wellorderable via the wellordering on $f(A)$.
Since Zorn’s lemma and the wellordering principles are both equivalent to AC in ZF, the theorem is proved. ∎
Title  ordering on cardinalities 

Canonical name  OrderingOnCardinalities 
Date of creation  20130322 18:50:23 
Last modified on  20130322 18:50:23 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  4 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03E10 
Classification  msc 03E25 