(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 1 Two sets and are equinumerous, written , if there is a bijection between them.
Definition 2 A cardinal is 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 union
and each 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 . 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.
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 is the least ordinal such that . We denote it by .
Ques 8 Why must be a cardinal?
Remark 9 One 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 11 Prove 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 12 We 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 13 For a cardinal , we define to be the least cardinal above , called the successor cardinal.
This exists and has .
Next, we claim that:
Exercise 14 Show that if is a set of cardinals, then is a cardinal.
Thus by transfinite induction we obtain that:
Definition 15 For any , we define the aleph numbers as
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 17 An infinite cardinal which is not a successor cardinal is called a limit 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 , define
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 ( 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 20 Let 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 23 Suppose and are cardinals. Then
Here 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.
Prototypical example for this section: , , \dots are all regular, but has cofinality .
Definition 24 Let be a limit ordinal, and another ordinal. A map of ordinals is called cofinal if 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 26 Let be a limit ordinal. The cofinality of , denoted , is the smallest ordinal such that there is a cofinal map .
Ques 27 Why 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 a countable ordinal, 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 cardinal
This 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 33 Why must strong limit cardinals actually be limit cardinals? (This is offensively easy.)
A regular strong limit cardinal other than is called strongly inaccessible.
Problem 1 Compute .
Problem 2 Prove that for any limit ordinal , is a regular cardinal.
Problem 4 (Konig’s Theorem) Show that
for every infinite cardinal .
(This post is a draft of a chapter from my Napkin project.)