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\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öder-Bernstein 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 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\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 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
Canonical name	OrderingOnCardinalities
Date of creation	2013-03-22 18:50:23
Last modified on	2013-03-22 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