(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 and :

In fact, as you likely already know, there is even a bijection between and :

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 1Two sets and areequinumerous, written , if there is a bijection between them.

Definition 2Acardinalis an ordinal such that for no do we have .

Example 3 (Examples of Cardinals)Every finite number is a cardinal. Moreover, is a cardinal. However, , , are not, because they are countable.

Example 4 ( is Countable)Even is not a cardinal, since it is a countable unionand each is countable.

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

Remark 6There is something fishy about the definition of a cardinal: it relies on anexternalfunction . That is, to verify is a cardinal I can’t just look at itself; I need to examine the entire universe to make sure there does not exist a bijection for . 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 7Thecardinalityof a set is theleastordinal such that . We denote it by .

Ques 8Why must be a cardinal?

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

Since cardinals are ordinals, it makes sense to ask whether , and so on. Our usual intuition works well here.

Proposition 10 (Restatement of Cardinality Properties)Let and be sets.

- if and only , if and only if there is a bijection between and .
- if and only if there is an injective map .

Ques 11Prove this.

## 3. Aleph Numbers

*Prototypical example for this section:* * is , and is the first uncountable*

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

Proposition 12We have for every set .

*Proof:* There is an injective map but there is no injective map by Cantor’s diagonal argument.

Thus we can define:

Definition 13For a cardinal , we define to be the least cardinal above , called thesuccessor cardinal.

This exists and has .

Next, we claim that:

Exercise 14Show that if is a set of cardinals, then is a cardinal.

Thus by transfinite induction we obtain that:

Definition 15For any , we define thealeph numbersas

Thus we have the following sequence of cardinals:

By definition, is the cardinality of the natural numbers, is the first uncountable ordinal, \dots.

We claim the aleph numbers constitute all the cardinals:

Lemma 16 (Aleph Numbers Constitute All Infinite Cardinals)If is a cardinal then either is finite (i.e. ) or for some .

*Proof:* Assume is infinite, and take minimal with . Suppose for contradiction that we have . We may assume , since the case is trivial.

If is a successor, then

which contradicts the fact the definition of the successor cardinal. If is a limit ordinal, then is the supremum . So there must be some has , which contradicts the minimality of .

Definition 17An infinite cardinal which is not a successor cardinal is called alimit cardinal. It is exactly those cardinals of the form , for a limit ordinal, plus .

## 4. Cardinal Arithmetic

*Prototypical example for this section:*

Recall the way we set up ordinal arithmetic. Note that in particular, and . Since cardinals count size, this property is undesirable, and we want to have

because and 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 and , defineand

Ques 19Check 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 ( but ). 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, will always refer to viewed as an ordinal; will always refer to the same set viewed as a cardinal. More generally,

Definition 20Let viewed as an ordinal.

However, as we’ve seen already we have that . In fact, this holds even more generally:

Theorem 21 (Infinite Cardinals Squared)Let be an infinite cardinal. Then .

*Proof:* Obviously , so we want to show .

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

Let’s copy this idea for a general .

We proceed by transfinite induction on . The base case is , done above. For the inductive step, first we put the “diagonal” ordering on as follows: for and in we declare if

- (they are on different diagonals), or
- and (same diagonal).

Then is a well-ordering of , so we know it is in order-preserving bijection with some ordinal . Our goal is to show that . To do so, it suffices to prove that for any , we have .

Suppose corresponds to the point under this bijection. If and are both finite, then certainly is finite too. Otherwise, let ; then the number of points below is at most

by the inductive hypothesis. So as desired.

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

Theorem 22 (Infinite Cardinal Arithmetic is Trivial)Given cardinals and , one of which is infinite, we have

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

## 5. Cardinal Exponentiation

*Prototypical example for this section:* *.*

Definition 23Suppose and are cardinals. ThenHere is the set of functions from to .

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

In particular, , and so from now on we can use the notation freely. (Note that this is totally different from ordinal arithmetic; there we had . In cardinal arithmetic .)

I have unfortunately not told you what equals. A natural conjecture is that ; 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 axioms.

## 6. Cofinality

*Prototypical example for this section:* *, , \dots are all regular, but has cofinality .*

Definition 24Let be a limit ordinal, and another ordinal. A map of ordinals is calledcofinalif for every , there is some such that . In other words, the map reaches arbitrarily high into .

Example 25 (Example of a Cofinal Map)

- The map by is cofinal.
- For any ordinal , the identity map is cofinal.

Definition 26Let be a limit ordinal. Thecofinalityof , denoted , is the smallest ordinal such that there is a cofinal map .

Ques 27Why must be an infinite cardinal?

Usually, we are interested in taking the cofinality of a cardinal .

Pictorially, you can imagine standing at the bottom of the universe and looking up the chain of ordinals to . You have a machine gun and are firing bullets upwards, and you want to get arbitrarily high but less than . 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 ( is Regular), because no finite subset of can reach arbitrarily high.

Example 29 ( is Regular). Indeed, assume for contradiction that some countable set of ordinals reaches arbitrarily high inside . Then is acountableordinal, because it is a countable union of countable ordinals. In other words . But is an upper bound for , contradiction.

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

Example 30 ( is Not Regular)Notice that reaches arbitrarily high in , despite only having terms. It follows that .

We now confirm a suspicion you may have:

Theorem 31 (Successor Cardinals Are Regular)If is a successor cardinal, then it is regular.

*Proof:* We copy the proof that was regular.

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

The number of elements in the union is at most

and hence .

## 7. Inaccessible Cardinals

So, what about limit cardinals? It seems to be that most of them are singular: if is a limit ordinal, then the sequence (of length ) is certainly cofinal.

Example 32 (Beth Fixed Point)Consider the monstrous cardinalThis might look frighteningly huge, as , but its cofinality is as it is the limit of the sequence

More generally, one can in fact prove that

But it is actually conceivable that is so large that .

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

An infinite cardinal is a strong limit cardinal if

for any cardinal . For example, is a strong limit cardinal.

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

A regular strong limit cardinal other than is called **strongly inaccessible**.

## 8. Exercises

Problem 1Compute .

Problem 2Prove that for any limit ordinal , is aregularcardinal.

Sproblem 3 (Strongly Inaccessible Cardinals)Show that for any strongly inaccessible , we have .

Problem 4 (Konig’s Theorem)Show thatfor every infinite cardinal .

(This post is a draft of a chapter from my Napkin project.)