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 AB. Thus is a (class) binary relationMathworldPlanetmath on the class V of all sets. This relation is clearly reflexiveMathworldPlanetmathPlanetmath and transitiveMathworldPlanetmathPlanetmathPlanetmath. If AB and BA, then, by Schröder-Bernstein theoremMathworldPlanetmath, A is bijectiveMathworldPlanetmathPlanetmath to B, AB. However, clearly AB in general. Therefore fails to be a partial orderMathworldPlanetmath. However, since AB iff they have the same cardinality, |A|=|B|, and since cardinals are by definition sets, the class of all cardinals becomes a partially ordered setMathworldPlanetmath with partial order . We record this result as a theorem:

Theorem 1.

In ZF, the relation is a partial order on the cardinals.

With the additionPlanetmathPlanetmath of the axiom of choiceMathworldPlanetmath, one can show that is a linear order on the cardinals. In fact, the statement “ is a linear order on the cardinals” is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the axiom of choice.

Theorem 2.

In ZF, the following are equivalent:

  1. 1.

    the axiom of choice

  2. 2.

    is a linear order on the cardinals


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, for otherwise is an injection from B to A. Let P be the collectionMathworldPlanetmath of all partial injective functions from B to A. P, as a collection of relations between B and A, is a set. P, 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 functionsMathworldPlanetmath in P, let us look at f:=F. Suppose (a,b),(a,c)f. Then (a,b)p and (a,c)q for some p,qF. Since F is a chain, one is a subset of the other, so say, pq. Then (a,b)q, and since q is a partial function, b=c. This shows that f is a partial function. Next, suppose (a,c),(b,c)f. By the same argument used to show that f is a function, we see that a=b, so that f is injective. Therefore fP. Thus, by Zorn’s lemma, P has a maximal elementMathworldPlanetmath 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 dom(g) onto A. Then g-1:AB is an injection, contrary to the assumptionPlanetmathPlanetmath. Therefore, we may pick an element aA-ran(g). Now, if dom(g)B, we may pick an element bB-dom(g). Then the partial function g*:dom(g){b}A given by

g*(x)={g(x) if xdom(g),a if x=b.

Since g* is injective by construction, g*P. Since g* properly extends g, we have reached a contradictionMathworldPlanetmathPlanetmath, 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 ordinalMathworldPlanetmathPlanetmath, it is well-ordered. Therefore, as f(A) is well-ordered, and because Af(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