Cardinals

1. Introduction

This page discusses cardinals and cardinal arithmetic, both with and without the Axiom of Choice. In general the subject is a very rich one with many results and still many difficult problems at the research level.

2. Cardinal arithmetic

Cardinal numbers are discussed at length in the beginning of Section 11.1 of The Mathematics of Logic. In particular two sets $X, Y$ have the same cardinality or are equipolent (written $X \approx Y$ ) if there is a bijection $f : X \to Y$ . This is an equivalence relation on sets. Informally you can think of the cardinality of a set as the equivalence class of the set by this equivalence relation, but this raises a problem: the cardinality of a set if defined this way is not itself a set but a class. To get round this problem one of two alternative definitions are usually provided.

In the absence of the Axiom of Choice, the following definition is usually preferred.

Definition.

$card (X)$ , the cardinality of $X$ , is the set $\{u: u \approx X \land \forall v (rank (v) < rank (u) \to \neg v \approx X)\}$ .

Thus the cardinality of a set is the set of sets equipolent to it of minimal rank. Since this is a subset of some $V_{α}$ it is a set.

If the Axiom of Choice holds then a simpler alternative is available.

Definition.

By the well-ordering principle every set $X$ is well-orderable, and hence in 1–1 correspondence with an ordinal. Thus there is a least ordinal $α \approx X$ . We define $card (X)$ to be this ordinal.

This definition has the advantage that $card (X)$ is a canonically chosen set with the same cardinality as $X$ . Note that the two definitions, as just given, are not compatible. In practice, the definition (any definition) of $card (X)$ is simply a convenience rather than essential, since results about a cardinal are usually proved by first taking a set that has that cardinality. Here we will implicitly assume AC holds and take the second definition of cardinal, but indicate which of the theorems we prove do not need choice.

Definition.

An ordinal $α$ is initial if there is no bijection $f : α \to β$ for $β < α$ .

For example, $ω$ is initial but $ω + 1$ is not. (This is a consequence of the next proposition below.)

Given a set $X$ , the least ordinal in 1–1 correspondence with it is an initial ordinal, since if not there would be a smaller ordinal in 1–1 correspondence with $X$ , because 1–1 correspondences compose. Thus cardinals are initial ordinals. Conversely, all initial ordinals are their own cardinals.

Proposition.

An infinite initial ordinal is a limit ordinal.

Proof.

If $α = β + 1$ is infinite there is a bijection $β \to α$ defined by $f (0) = β$ , $f (n +1) = n$ for $n \in ω$ and $f (γ) = γ$ for all other $γ$ .

The theorems and proofs in Sections 11.1 and 11.3 should be studied carefully. All of the proofs there are valid in $ZF$ or $ZFC$ , and where Zorn's lemma was used it is known that some form of the Axiom of Choice is required for the result in question. In particular the definitions of cardinal arithmetic and the order relation on cardinals is important. We define

Definition.

For sets $A, B$ , $card (A) ⩽ card (B)$ if there is an injection $f : A \to B$ . We define $card (A) ⩽^{*} card (B)$ if $A = \emptyset$ or there is a surjection $g : B \to A$ .

However, the Zorn's lemma proof in the book that cardinal arithmetic has $κ^{2} = κ$ for all infinite $κ$ is slightly long-winded. For those that know about ordinals (including everyone reading these web pages) there is a different proof.

First we define bijections $f_{α} : α \times α \to F (α)$ recursively on ordinals $α$ . Define $F (0) = 0$ , $F (α + 1) = F (α) + α + α + 1$ , and $F (λ) = ⋃_{α < λ} F (α)$ for limits $λ$ . Define $f_{0} : 0 \times 0 \to 0$ to be the empty function, and $f_{α + 1} (β, γ) = f_{α} (β, γ)$ if $β, γ < α$ , $f_{α + 1} (α, γ) = F (α) + γ$ if $γ < α$ , and $f_{α + 1} (β, α) = F (α) + α + β$ if $β ⩽ α$ ; finally $f_{λ} (β, γ) = f_{α} (β, γ)$ for any $α$ with $β, γ < α < λ$ . You can check that these define bijections $f_{α} : α \times α \to F (α)$ as claimed and $f_{α}$ extends $f_{β}$ for $α > β$ .

Proposition.

If $κ$ is an infinite initial ordinal then there is a bijection $κ \times κ \to κ$ .

Proof.

Suppose $κ$ is initial and for every smaller initial ordinal $μ$ there is a 1–1 correspondence $μ \times μ \to μ$ . Consider $f_{κ} : κ \times κ \to F (κ)$ . If $F (κ) ⩽ κ$ we are finished, by Schröder–Bernstein. So $κ < F (κ)$ . Also $F (μ) < κ$ for all initial $μ < κ$ since $F (μ)$ , $μ \times μ$ and $μ$ all have the same cardinality strictly less than $κ$ . Let $F_{κ} (α, β) = κ$ and let $δ = max (α, β) +1$ so $κ$ is in the range of $f_{δ}$ . Now $δ < κ$ as $κ$ is initial and hence is a limit ordinal. Therefore there is a bijection from $δ$ to $μ$ , some initial ordinal less than $κ$ , and this induces an impossible bijection from $F (δ) > κ$ to $F (μ) < κ$ .

The previous result does not need the axiom of choice, but the conclusion that $κ \times κ = κ$ for all infinite cardinals $κ$ does not follow from it without choice as (in the absence of choice) some sets are not well-orderable.

3. Alephs and Hartog's function

The axiom of choice is not required in this section either.

Definition.

Given any set $X$ , we define $ℵ (X) = \{α \in On: there is an injection α \to X\}$ .

Lemma.

For all sets $X$ , $ℵ (X)$ is a set, and hence an ordinal. There is no injection $ℵ (X) \to X$ and $ℵ (X)$ is the least ordinal with this property.

Proof.

Let

W = \{(y, <): y \subseteq X \land < is a well-order on X\}

So $W$ is a set by separation and power set axioms and there is for each $(y, <) \in W$ a unique ordinal $α_{y}$ order-isomorphic to $(y, <)$ . Define $f : (y, <) \mapsto α_{y}$ and by replacement the image of $f$ is a set, and note that this image is $ℵ (X)$ . There is no injection $ℵ (X) \to X$ for if there was we would have $ℵ (X) \in ℵ (X)$ .

Proposition.

For all $X$ , $ℵ (X)$ is initial.

Proof.

If not, $f : ℵ (X) \to β < α$ and $g : β \to y \subseteq x$ are bijections then their composition maps $ℵ (X) \to X$ injectively, so $ℵ (X) \in ℵ (X)$ .

Initial ordinals are sometimes called Alephs because of the following.

Definition.

$ℵ_{0} = ω$ , the first infinite initial ordinal; $ℵ_{α + 1} = ℵ (ℵ_{α})$ ; and $ℵ_{λ} = ⋃_{α < λ} ℵ_{α}$ for limit ordinals $λ$ .

Proposition.

Each $ℵ_{α}$ is initial; every initial ordinal is $ℵ_{α}$ for some $α$ .

Proof.

If $λ$ is a limit and $f : ℵ_{λ} \to β < ℵ_{λ}$ is a bijection then a restriction of $f$ is an injection $ℵ_{α + 1} \to β \subseteq ℵ_{α}$ , contradicting Schröder–Bernstein. Thus every $ℵ_{α}$ is initial as the result is obvious for the zero and sucessor cases. The converse is proved by taking an initial ordinal $α$ and considering the least ordinal $β$ such that $α < ℵ_{β}$ . This $β$ exists by the fact that $α_{β} ⩾ β$ for all $β$ , and must be a successor. For if $β$ is a limit, by definition of $α_{β}$ there would be $δ < β$ with $α < ℵ_{δ}$ . Thus $β = γ + 1$ and $ℵ_{γ} ⩽ α < ℵ_{γ + 1}$ so there is an injection $α \to ℵ_{γ}$ as $α \in ℵ (ℵ_{γ})$ , hence $α = ℵ_{γ}$ as $α$ is initial.

Under the Axiom of Choice, every set is well-ordered so is in one-to-one correspondence with an ordinal. Thus the Axiom of Choice implies every cardinal is an aleph.

Hartog's $ℵ$ function gives one way to make a larger cardinal from a smaller one. Another way is to use the power set function.

Proposition.

Let $X$ be a set. Then there is no bijection between $X$ and $P (X)$ .

Proof.

Suppose $f : X \to P (X)$ is a bijection and let $y = \{u \in x: u \notin f (u)\}$ . We get a contradiction by taking $u \in x$ such that $y = f (u)$ and trying to decide if $u \in f (u)$ or not.

Definition.

For a set $X$ , $ℶ (X)$ is the cardinality of $P (X)$ .

Thus we have two ways to make a cardinality just a bit bigger than $ω$ : either $ℵ (ω)$ or $ℶ (ω)$ . Assuming the Axiom of Choice we have $ℵ (ω) ⩽ ℶ (ω)$ . Cantor's Continuum Hypothesis (CH) is the statement that $ℵ (ω) = ℶ (ω)$ . Whether or not this is true remains a moot point, but it has been shown to be independent of the ZFC axioms (assuming ZFC to be consistent.

More generally, the Generalised Continuum Hypotheis (GCH) is the statement $ℶ (ℵ_{α}) = ℵ_{α + 1}$ for all $α$ . Again, this is consistent with the axioms of ZFC but not provable in them. It can be shown that GCH implies the axiom of choice, so assuming GCH makes no sense without also assuming AC.

4. Trichotomy

The Trichotomy theorem (Proposition 11.18 in The Mathematics of Logic) is equivalent to the Axiom of Choice. To see this, let $X$ be any set. Then it is not the case that $ℵ (X) ⩽ X$ , by the construction of Hartog's $ℵ$ function, so by Trichotomy $X ⩽ ℵ (X)$ . In other words there is an injection $X \to ℵ (X)$ and as $ℵ (X)$ is an ordinal a well ordering on $X$ may be defined via this injection and $\in$ on $ℵ (X)$ . Under a particular assumption on the arithmetic of certain cardinals, an interesting weakening of trichotomy can be obtained without Choice. In this section $κ, λ$ are just names for infinite cardinals: the fact we call them this is not intended to mean that they are necessarily ordinals. (Sometimes they will be ordinals, sometimes not.)

Proposition.

If $κ, λ$ are cardinals such that $κ + λ = κ λ$ then $κ ⩽ λ$ or $λ ⩽^{*} κ$ .

Proof.

Suppose $K, L$ are disjoint sets with cardinalities $κ, λ$ and $f : K \cup L \to K \times L$ is a bijection and $π : K \times L \to L$ is the projection map. If the composite of $K \to K \times L \to L$ is onto then we know that $λ ⩽^{*} κ$ . Otherwise there is $x \in L$ such that for each $y \in K$ the unique $z \in K \cup L$ such that $f (z) = (y, x)$ is in $L$ . This defines an injection $y \mapsto z$ taking $K$ into $L$ . Thus $κ ⩽ λ$ .

This result has the consequence that our theorem on cardinal arithmetic is in fact equivalent to the axiom of choice.

If $κ^{2} = κ$ for all infinite cardinals $κ$ then the Axiom of Choice holds.

Proof.

Let $X$ be an arbitrary set with cardinality $λ$ and let $κ = ℵ (X)$ . Then $κ + λ = (κ + λ)^{2} ⩾ κ λ ⩾ κ + λ$ so by Schröder–Berstein $κ + λ = κ λ$ . Thus by the previous either $κ ⩽ λ$ or $λ ⩽^{*} κ$ . But $κ ⩽ λ$ is impossible by the definition of $ℵ (X)$ and hence $λ ⩽^{*} κ$ so there is a surjection $f : κ \to X$ and hence an injection $g : X \to κ$ given by $g (x)$ is the least $β < κ$ with $f (β) = x$ . This allows us to define a well-ordering on $X$ as before.

On the other hand, the proposition $κ + κ = κ$ for all infinite cardinals $κ$ is known to be strictly weaker than the axiom of choice.