Cardinals

(Standard post on cardinals, as a prerequisite for forthcoming theory model post.)

An ordinal measures a total ordering. However, it does not do a fantastic job at measuring size. For example, there is a bijection between the elements of ${\omega}$ and ${\omega+1}$ :

$\displaystyle \begin{array}{rccccccc} \omega+1 = & \{ & \omega & 0 & 1 & 2 & \dots & \} \\ \omega = & \{ & 0 & 1 & 2 & 3 & \dots & \}. \end{array}$

In fact, as you likely already know, there is even a bijection between ${\omega}$ and ${\omega^2}$ :

$\displaystyle \begin{array}{l|cccccc} + & 0 & 1 & 2 & 3 & 4 & \dots \\ \hline 0 & 0 & 1 & 3 & 6 & 10 & \dots \\ \omega & 2 & 4 & 7 & 11 & \dots & \\ \omega \cdot 2 & 5 & 8 & 12 & \dots & & \\ \omega \cdot 3 & 9 & 13 & \dots & & & \\ \omega \cdot 4 & 14 & \dots & & & & \end{array}$

So ordinals do not do a good job of keeping track of size. For this, we turn to the notion of a cardinal number.

1. Equinumerous Sets and Cardinals

Definition 1 Two sets ${A}$ and ${B}$ are equinumerous, written ${A \approx B}$ , if there is a bijection between them.

Definition 2 A cardinal is an ordinal ${\kappa}$ such that for no ${\alpha < \kappa}$ do we have ${\alpha \approx \kappa}$ .

Example 3 (Examples of Cardinals) Every finite number is a cardinal. Moreover, ${\omega}$ is a cardinal. However, ${\omega+1}$ , ${\omega^2}$ , ${\omega^{2015}}$ are not, because they are countable.

Example 4 ( ${\omega^\omega}$ is Countable) Even ${\omega^\omega}$ is not a cardinal, since it is a countable union

$\displaystyle \omega^\omega = \bigcup_n \omega^n$

and each ${\omega^n}$ is countable.

Ques 5 Why must an infinite cardinal be a limit ordinal?

Remark 6 There is something fishy about the definition of a cardinal: it relies on an external function ${f}$ . That is, to verify ${\kappa}$ is a cardinal I can’t just look at ${\kappa}$ itself; I need to examine the entire universe ${V}$ to make sure there does not exist a bijection ${f : \kappa \rightarrow \alpha}$ for ${\alpha < \kappa}$ . For now this is no issue, but later in model theory this will lead to some highly counterintuitive behavior.

2. Cardinalities

Now that we have defined a cardinal, we can discuss the size of a set by linking it to a cardinal.

Definition 7 The cardinality of a set ${X}$ is the least ordinal ${\kappa}$ such that ${X \approx \kappa}$ . We denote it by ${\left\lvert X \right\rvert}$ .

Ques 8 Why must ${\left\lvert X \right\rvert}$ be a cardinal?

Remark 9 One needs the Well-Ordering Theorem (equivalently, Choice) in order to establish that such an ordinal ${\kappa}$ actually exists.

Since cardinals are ordinals, it makes sense to ask whether ${\kappa_1 \le \kappa_2}$ , and so on. Our usual intuition works well here.

Proposition 10 (Restatement of Cardinality Properties) Let ${X}$ and ${Y}$ be sets.

${X \approx Y}$ if and only ${\left\lvert X \right\rvert = \left\lvert Y \right\rvert}$ , if and only if there is a bijection between ${X}$ and ${Y}$ .

${\left\lvert X \right\rvert \le \left\lvert Y \right\rvert}$ if and only if there is an injective map ${X \hookrightarrow Y}$ .

Ques 11 Prove this.

3. Aleph Numbers

Prototypical example for this section: ${\aleph_0}$ is ${\omega}$ , and ${\aleph_1}$ is the first uncountable

First, let us check that cardinals can get arbitrarily large:

Proposition 12 We have ${\left\lvert X \right\rvert < \left\lvert \mathcal P(X) \right\rvert}$ for every set ${X}$ .

Proof: There is an injective map ${X \hookrightarrow \mathcal P(X)}$ but there is no injective map ${\mathcal P(X) \hookrightarrow X}$ by Cantor’s diagonal argument. $\Box$

Thus we can define:

Definition 13 For a cardinal ${\kappa}$ , we define ${\kappa^+}$ to be the least cardinal above ${\kappa}$ , called the successor cardinal.

This ${\kappa^+}$ exists and has ${\kappa^+ \le \left\lvert \mathcal P(\kappa) \right\rvert}$ .

Next, we claim that:

Exercise 14 Show that if ${A}$ is a set of cardinals, then ${\cup A}$ is a cardinal.

Thus by transfinite induction we obtain that:

Definition 15 For any ${\alpha \in \mathrm{On}}$ , we define the aleph numbers as

$\displaystyle \begin{aligned} \aleph_0 &= \omega \\ \aleph_{\alpha+1} &= \left( \aleph_\alpha \right)^+ \\ \aleph_{\lambda} &= \bigcup_{\alpha < \lambda} \aleph_\alpha. \end{aligned}$

Thus we have the following sequence of cardinals:

$\displaystyle 0 < 1 < 2 < \dots < \aleph_0 < \aleph_1 < \dots < \aleph_\omega < \aleph_{\omega+1} < \dots$

By definition, ${\aleph_0}$ is the cardinality of the natural numbers, ${\aleph_1}$ is the first uncountable ordinal, \dots.

We claim the aleph numbers constitute all the cardinals:

Lemma 16 (Aleph Numbers Constitute All Infinite Cardinals) If ${\kappa}$ is a cardinal then either ${\kappa}$ is finite (i.e. ${\kappa \in \omega}$ ) or ${\kappa = \aleph_\alpha}$ for some ${\alpha \in \mathrm{On}}$ .

Proof: Assume ${\kappa}$ is infinite, and take ${\alpha}$ minimal with ${\aleph_\alpha \ge \kappa}$ . Suppose for contradiction that we have ${\aleph_\alpha > \kappa}$ . We may assume ${\alpha > 0}$ , since the case ${\alpha = 0}$ is trivial.

If ${\alpha = \overline{\alpha} + 1}$ is a successor, then

$\displaystyle \aleph_{\overline{\alpha}} < \kappa < \aleph_{\alpha} = (\aleph_{\overline{\alpha}})^+$

which contradicts the fact the definition of the successor cardinal. If ${\alpha = \lambda}$ is a limit ordinal, then ${\aleph_\lambda}$ is the supremum ${\bigcup_{\gamma < \lambda} \aleph_\gamma}$ . So there must be some ${\gamma < \lambda}$ has ${\aleph_\gamma > \kappa}$ , which contradicts the minimality of ${\alpha}$ . $\Box$

Definition 17 An infinite cardinal which is not a successor cardinal is called a limit cardinal. It is exactly those cardinals of the form ${\aleph_\lambda}$ , for ${\lambda}$ a limit ordinal, plus ${\aleph_0}$ .

4. Cardinal Arithmetic

Prototypical example for this section: ${\aleph_0 \cdot \aleph_0 = \aleph_0 + \aleph_0 = \aleph_0}$

Recall the way we set up ordinal arithmetic. Note that in particular, ${\omega + \omega > \omega}$ and ${\omega^2 > \omega}$ . Since cardinals count size, this property is undesirable, and we want to have

$\displaystyle \begin{aligned} \aleph_0 + \aleph_0 &= \aleph_0 \\ \aleph_0 \cdot \aleph_0 &= \aleph_0 \end{aligned}$

because ${\omega + \omega}$ and ${\omega \cdot \omega}$ are countable. In the case of cardinals, we simply “ignore order”.

The definition of cardinal arithmetic is as expected:

Definition 18 (Cardinal Arithmetic) Given cardinals ${\kappa}$ and ${\mu}$ , define

$\displaystyle \kappa + \mu \overset{\mathrm{def}}{=} \left\lvert \left( \left\{ 0 \right\} \times \kappa \right) \cup \left( \left\{ 1 \right\} \times \mu \right) \right\rvert$

and

$\displaystyle k \cdot \mu \overset{\mathrm{def}}{=} \left\lvert \mu \times \kappa \right\rvert .$

Ques 19 Check this agrees with what you learned in pre-school for finite cardinals.

This is a slight abuse of notation since we are using the same symbols as for ordinal arithmetic, even though the results are different ( ${\omega \cdot \omega = \omega^2}$ but ${\aleph_0 \cdot \aleph_0 = \aleph_0}$ ). In general, I’ll make it abundantly clear whether I am talking about cardinal arithmetic or ordinal arithmetic. To help combat this confusion, we use separate symbols for ordinals and cardinals. Specifically, ${\omega}$ will always refer to ${\{0,1,\dots\}}$ viewed as an ordinal; ${\aleph_0}$ will always refer to the same set viewed as a cardinal. More generally,

Definition 20 Let ${\omega_\alpha = \aleph_\alpha}$ viewed as an ordinal.

However, as we’ve seen already we have that ${\aleph_0 \cdot \aleph_0 = \aleph_0}$ . In fact, this holds even more generally:

Theorem 21 (Infinite Cardinals Squared) Let ${\kappa}$ be an infinite cardinal. Then ${\kappa \cdot \kappa = \kappa}$ .

Proof: Obviously ${\kappa \cdot \kappa \ge \kappa}$ , so we want to show ${\kappa \cdot \kappa \le \kappa}$ .

The idea is to repeat the same proof that we had for ${\aleph_0 \cdot \aleph_0 = \aleph_0}$ , so we re-iterate it here. We took the “square” of elements of ${\aleph_0}$ , and then re-ordered it according to the diagonal:

$\displaystyle \begin{array}{l|cccccc} & 0 & 1 & 2 & 3 & 4 & \dots \\ \hline 0 & 0 & 1 & 3 & 6 & 10 & \dots \\ 1 & 2 & 4 & 7 & 11 & \dots & \\ 2 & 5 & 8 & 12 & \dots & & \\ 3 & 9 & 13 & \dots & & & \\ 4 & 14 & \dots & & & & \end{array}$

Let’s copy this idea for a general ${\kappa}$ .

We proceed by transfinite induction on ${\kappa}$ . The base case is ${\kappa = \aleph_0}$ , done above. For the inductive step, first we put the “diagonal” ordering ${<_{\text{diag}}}$ on ${\kappa \times \kappa}$ as follows: for ${(\alpha_1, \beta_1)}$ and ${(\alpha_1, \beta_2)}$ in ${\kappa \times \kappa}$ we declare ${(\alpha_1, \beta_1) <_{\text{diag}} (\alpha_2, \beta_2)}$ if

${\max \left\{ \alpha_1, \beta_1 \right\} < \max \left\{ \alpha_2, \beta_2 \right\}}$ (they are on different diagonals), or
${\max \left\{ \alpha_1, \beta_1 \right\} = \max \left\{ \alpha_2, \beta_2 \right\}}$ and ${\alpha_1 < \alpha_2}$ (same diagonal).

Then ${<_{\text{diag}}}$ is a well-ordering of ${\kappa \times \kappa}$ , so we know it is in order-preserving bijection with some ordinal ${\gamma}$ . Our goal is to show that ${\left\lvert \gamma \right\rvert \le \kappa}$ . To do so, it suffices to prove that for any ${\overline{\gamma} \in \gamma}$ , we have ${\left\lvert \overline{\gamma} \right\rvert < \kappa}$ .

Suppose ${\overline{\gamma}}$ corresponds to the point ${(\alpha, \beta) \in \kappa}$ under this bijection. If ${\alpha}$ and ${\beta}$ are both finite, then certainly ${\overline{\gamma}}$ is finite too. Otherwise, let ${\overline{\kappa} = \max \{\alpha, \beta\} < \kappa}$ ; then the number of points below ${\overline{\gamma}}$ is at most

$\displaystyle \left\lvert \alpha \right\rvert \cdot \left\lvert \beta \right\rvert \le \overline{\kappa} \cdot \overline{\kappa} = \overline{\kappa}$

by the inductive hypothesis. So ${\left\lvert \overline{\gamma} \right\rvert \le \overline{\kappa} < \kappa}$ as desired. $\Box$

From this it follows that cardinal addition and multiplication is really boring:

Theorem 22 (Infinite Cardinal Arithmetic is Trivial) Given cardinals ${\kappa}$ and ${\mu}$ , one of which is infinite, we have

$\displaystyle \kappa \cdot \mu = \kappa + \mu = \max\left( \kappa, \mu \right).$

Proof: The point is that both of these are less than the square of the maximum. Writing out the details:

$\displaystyle \begin{aligned} \max \left( \kappa, \mu \right) &\le \kappa + \mu \\ &\le \kappa \cdot \mu \\ &\le \max \left( \kappa, \mu \right) \cdot \max \left( \kappa, \mu \right) \\ &= \max\left( \kappa, \mu \right). \end{aligned}$

$\Box$

5. Cardinal Exponentiation

Prototypical example for this section: ${2^\kappa = \left\lvert \mathcal P(\kappa) \right\rvert}$ .

Definition 23 Suppose ${\kappa}$ and ${\lambda}$ are cardinals. Then

$\displaystyle \kappa^\lambda \overset{\mathrm{def}}{=} \left\lvert \mathscr F(\lambda, \kappa) \right\rvert.$

Here ${\mathscr F(A,B)}$ is the set of functions from ${A}$ to ${B}$ .

As before, we are using the same notation for both cardinal and ordinal arithmetic. Sorry!

In particular, ${2^\kappa = \left\lvert \mathcal P(\kappa) \right\rvert > \kappa}$ , and so from now on we can use the notation ${2^\kappa}$ freely. (Note that this is totally different from ordinal arithmetic; there we had ${2^\omega = \bigcup_{n\in\omega} 2^n = \omega}$ . In cardinal arithmetic ${2^{\aleph_0} > \aleph_0}$ .)

I have unfortunately not told you what ${2^{\aleph_0}}$ equals. A natural conjecture is that ${2^{\aleph_0} = \aleph_1}$ ; this is called the Continuum Hypothesis. It turns out to that this is undecidable — it is not possible to prove or disprove this from the ${\mathsf{ZFC}}$ axioms.

6. Cofinality

Prototypical example for this section: ${\aleph_0}$ , ${\aleph_1}$ , \dots are all regular, but ${\aleph_\omega}$ has cofinality ${\omega}$ .

Definition 24 Let ${\lambda}$ be a limit ordinal, and ${\alpha}$ another ordinal. A map ${f : \alpha \rightarrow \lambda}$ of ordinals is called cofinal if for every ${\overline{\lambda} < \lambda}$ , there is some ${\overline{\alpha} \in \alpha}$ such that ${f(\overline{\alpha}) \ge \overline{\lambda}}$ . In other words, the map reaches arbitrarily high into ${\lambda}$ .

Example 25 (Example of a Cofinal Map) ${\empty}$

The map ${\omega \rightarrow \omega^\omega}$ by ${n \mapsto \omega^n}$ is cofinal.

For any ordinal ${\alpha}$ , the identity map ${\alpha \rightarrow \alpha}$ is cofinal.

Definition 26 Let ${\lambda}$ be a limit ordinal. The cofinality of ${\lambda}$ , denoted ${\text{cof }(\lambda)}$ , is the smallest ordinal ${\alpha}$ such that there is a cofinal map ${\alpha \rightarrow \lambda}$ .

Ques 27 Why must ${\alpha}$ be an infinite cardinal?

Usually, we are interested in taking the cofinality of a cardinal ${\kappa}$ .

Pictorially, you can imagine standing at the bottom of the universe and looking up the chain of ordinals to ${\kappa}$ . You have a machine gun and are firing bullets upwards, and you want to get arbitrarily high but less than ${\kappa}$ . The cofinality is then the number of bullets you need to do this.

We now observe that “most” of the time, the cofinality of a cardinal is itself. Such a cardinal is called regular.

Example 28 ( ${\aleph_0}$ is Regular) ${\text{cof }(\aleph_0) = \aleph_0}$ , because no finite subset of ${\omega}$ can reach arbitrarily high.

Example 29 ( ${\aleph_1}$ is Regular) ${\text{cof }(\aleph_1) = \aleph_1}$ . Indeed, assume for contradiction that some countable set of ordinals ${A = \{ \alpha_0, \alpha_1, \dots \} \subseteq \omega_1}$ reaches arbitrarily high inside ${\omega_1}$ . Then ${\Lambda = \cup A}$ is a countable ordinal, because it is a countable union of countable ordinals. In other words ${\Lambda \in \omega_1}$ . But ${\Lambda}$ is an upper bound for ${A}$ , contradiction.

On the other hand, there are cardinals which are not regular; since these are the “rare” cases we call them singular.

Example 30 ( ${\aleph_\omega}$ is Not Regular) Notice that ${\aleph_0 < \aleph_1 < \aleph_2 < \dots}$ reaches arbitrarily high in ${\aleph_\omega}$ , despite only having ${\aleph_0}$ terms. It follows that ${\text{cof }(\aleph_\omega) = \aleph_0}$ .

We now confirm a suspicion you may have:

Theorem 31 (Successor Cardinals Are Regular) If ${\kappa = \overline{\kappa}^+}$ is a successor cardinal, then it is regular.

Proof: We copy the proof that ${\aleph_1}$ was regular.

Assume for contradiction that for some ${\mu \le \overline{\kappa}}$ , there are ${\mu}$ sets reaching arbitrarily high in ${\kappa}$ as a cardinal. Observe that each of these sets must have cardinality at most ${\overline{\kappa}}$ . We take the union of all ${\mu}$ sets, which gives an ordinal ${\Lambda}$ serving as an upper bound.

The number of elements in the union is at most

$\displaystyle \#\text{sets} \cdot \#\text{elms} \le \mu \cdot \overline{\kappa} = \overline{\kappa}$

and hence ${\left\lvert \Lambda \right\rvert \le \overline{\kappa} < \kappa}$ . $\Box$

7. Inaccessible Cardinals

So, what about limit cardinals? It seems to be that most of them are singular: if ${\aleph_\lambda \ne \aleph_0}$ is a limit ordinal, then the sequence ${\{\aleph_\alpha\}_{\alpha \in \lambda}}$ (of length ${\lambda}$ ) is certainly cofinal.

Example 32 (Beth Fixed Point) Consider the monstrous cardinal

$\displaystyle \kappa = \aleph_{\aleph_{\aleph_{\ddots}}}.$

This might look frighteningly huge, as ${\kappa = \aleph_\kappa}$ , but its cofinality is ${\omega}$ as it is the limit of the sequence

$\displaystyle \aleph_0, \aleph_{\aleph_0}, \aleph_{\aleph_{\aleph_0}}, \dots$

More generally, one can in fact prove that

$\displaystyle \text{cof }(\aleph_\lambda) = \text{cof }(\lambda).$

But it is actually conceivable that ${\lambda}$ is so large that ${\left\lvert \lambda \right\rvert = \left\lvert \aleph_\lambda \right\rvert}$ .

A regular limit cardinal other than ${\aleph_0}$ has a special name: it is weakly inaccessible. Such cardinals are so large that it is impossible to prove or disprove their existence in ${\mathsf{ZFC}}$ . It is the first of many so-called “large cardinals”.

An infinite cardinal ${\kappa}$ is a strong limit cardinal if

$\displaystyle \forall \overline{\kappa} < \kappa \quad 2^{\overline{\kappa}} < \kappa$

for any cardinal ${\overline{\kappa}}$ . For example, ${\aleph_0}$ is a strong limit cardinal.

Ques 33 Why must strong limit cardinals actually be limit cardinals? (This is offensively easy.)

A regular strong limit cardinal other than ${\aleph_0}$ is called strongly inaccessible.

8. Exercises

Problem 1 Compute ${\left\lvert V_\omega \right\rvert}$ .

Problem 2 Prove that for any limit ordinal ${\alpha}$ , ${\text{cof }(\alpha)}$ is a regular cardinal.

Sproblem 3 (Strongly Inaccessible Cardinals) Show that for any strongly inaccessible ${\kappa}$ , we have ${\left\lvert V_\kappa \right\rvert = \kappa}$ .