# ordering on cardinalities

When there is a one-to-one 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öder-Bernstein 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. 1.

the axiom of choice

2. 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 well-ordering 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 well-ordered. Therefore, as $f(A)$ is well-ordered, and because $A\sim f(A)$, $A$ itself is well-orderable via the well-ordering on $f(A)$.

Since Zorn’s lemma and the well-ordering principles are both equivalent to AC in ZF, the theorem is proved. ∎

Title ordering on cardinalities OrderingOnCardinalities 2013-03-22 18:50:23 2013-03-22 18:50:23 CWoo (3771) CWoo (3771) 4 CWoo (3771) Theorem msc 03E10 msc 03E25