You are here
Homeordering on cardinalities
Primary tabs
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\leq B$. Thus $\leq$ is a (class) binary relation on the class $V$ of all sets. This relation is clearly reflexive and transitive. If $A\leq B$ and $B\leq A$, then, by SchröderBernstein theorem, $A$ is bijective to $B$, $A\sim B$. However, clearly $A\neq B$ in general. Therefore $\leq$ 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 $\leq$. We record this result as a theorem:
Theorem 1.
In ZF, the relation $\leq$ is a partial order on the cardinals.
With the addition of the axiom of choice, one can show that $\leq$ is a linear order on the cardinals. In fact, the statement “$\leq$ 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. $\leq$ 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\neq\varnothing$, for otherwise $\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\neq\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 $\operatorname{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\operatorname{ran}(g)$. Now, if $\operatorname{dom}(g)\neq B$, we may pick an element $b\in B\operatorname{dom}(g)$. Then the partial function $g^{*}:\operatorname{dom}(g)\cup\{b\}\to A$ given by
$g^{*}(x)=\left\{\begin{array}[]{ll}g(x)\quad\mbox{ if }x\in\operatorname{dom}(% g),\\ a\quad\mbox{ if }x=b.\end{array}\right.$ 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. ∎
Mathematics Subject Classification
03E10 no label found03E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections