Ordinal and cardinal numbers

Continuing my series about infinity.

We’ve previously made a lot of references to things like \(\aleph_0\), \(\aleph_1\), etc. What are these mysterious alephs? What do they mean?

They’re essentially a kind of “infinite number” called a cardinal number. In much the same way that we used the sets \(\{1, \ldots, n\}\) as canonical representatives of finite sets of a given size and said those sets had cardinality \(n\), we will find canonical representatives of every size of set and use those to label cardinalities.

It turns out that this isn’t quite the right place to start. Rather than canonical representatives for sizes, we’ll want canonical representatives for well orderings – they’re easier to build, and then our canonical representative for sizes will be the smallest well-ordering of that size as per our construction of \(\aleph_1\) at the end of the last post.

So how are we going to construct these things?

There turn out to be a lot of clues for how such a thing would work in our construction of \(W(A)\) in the last post. We implicitly proved the following theorem:

Theorem: Let \(A\) be a well-ordered set. Then \(A\) is isomorphic to the set \(\{I_a : a \in A\}\) ordered by \(\preceq\).

We can of course replace the \(I_a\) with any other sets isomorphic to it. In particular, if we have canonical representatives for every well-ordered set, we can replace the \(I_a\) with their canonical representatives.

This gives us a strategy: We’ll define our canonical representatives by transfinite induction (recall that we showed as part of our work around \(W(A)\) that \(\preceq\) well-ordered isomorphism classes of well-ordered sets). The representative for \(A\) is the set of all representatives for initial segments of \(A\).

Definition: Let \(A\) be a well-ordered set. Define \(\mathrm{ord}(A) = \{ \mathrm{ord}(I_a) : a \in A\}\). Give \(\mathrm{ord}(A)\) the ordering \(\preceq\).

As a corollary to our previous result, \(A \sim \mathrm{ord}(A)\). So this gives us our canonical representatives. We call something that is \(\mathrm{ord}(A)\) for some well-ordered \(A\) and ordinal number.

Note that we’re doing something subtly different from normal: The class of all well-ordered sets is not itself a set (because if it were it were you could construct \(W(A)\) which is a strictly larger well-ordered set). However, for any well-ordered set the isomorphism classes of well ordered sets \(\preceq\) it is a set, so we can still do transfinite induction like this.

First we need to show that this is a canonical representative:

Theorem: If \(A \sim B\) then \(\mathrm{ord}(A) = \mathrm{ord}(B)\).


Suppose \(\mathrm{ord}(A) \neq \mathrm{ord}(B)\).

Let \(f: A \to B\) be an order isomorphism. Consider the initial segments of \(A\). If \(\mathrm{ord}(I_a) \neq \mathrm{ord}(f(I_a))\) for some \(I_a\), replace \(A\) with the minimal such \(I_a\). Else, for every initial segment of \(A\), \(\mathrm{ord}(I_a) = \mathrm{ord}(I_b)\)

But \(\mathrm{ord}(A) = \{ \mathrm{ord}(I_a) : a \in A\}\). And because \(f\) is an isomorphism, \(\{f(I_a) : a \in A \} = \{I_b : b \in B\}\). So \(\mathrm{ord}(A) = \{ \mathrm{ord}(I_a) : a \in A\} = \{ \mathrm{ord}(f(I_a)) : a \in A\} = \{ \mathrm{ord}(I_b) : b \in B\} = \mathrm{ord}(B)\). QED

So the ordinals are indeed canonical representatives in the sense that they give us a way of choosing a distinct element out of every isomorphism class.

We’re now pretty much done.

A cardinal is an ordinal \(\alpha\) such that for \(\beta < \alpha\), \(|\beta| < |\alpha|\). i.e. every smaller ordinal is strictly smaller in size. The cardinality of a set is the unique cardinal number of the same size as that set.

Why does this cardinality always exist?

Well, form a well-ordering of \(A\) and take its ordinal \(\alpha\). Either this ordinal is a cardinal or \(\{\beta : \beta < \alpha, |\beta| = |A|\}\) is non-empty and the minimal element of that is a cardinal.

So these give us our canonical sets representing the cardinality of any given set. \(|A|\) can thus be considered as being that cardinal number.

But how do we write down cardinal numbers?

Well, that’s mostly just notation.

First we need some notation for ordinal numbers. We’re just going to name a few for now. In particular the ordinal numbers corresponding to finite sets (there’s a unique up to isomorphism total order of any finite size) we will just write as their size. So \(n\) is the ordinal number corresponding to ordering a finite set of size \(n\). For the normal order on \(\mathbb{N}\) we will write \(\omega\). These are enough ordinals for us for now.

Our notation for cardinal numbers comes as follows. We want to label cardinals by ordinals, so that the cardinal \(\aleph_\alpha\) is the \(\alpha\)th cardinal.

The easiest way to do this is by transfinite induction. Let \(\aleph_\alpha\) be the smallest infinite cardinal that is greater than \(\aleph_\beta\) for every \(\beta < \alpha\). This is well-defined because any set of cardinals is well ordered and because there are arbitrarily large cardinals so there will always be some cardinal greater than any set of cardinals (e.g. the power set of the union).

Note that \(\aleph_0 = \omega\): If \(\alpha < \omega\) then \(\alpha\) is isomorphic to an initial segment of \(\mathbb{N}\) so is finite. Note also that by construction if \(\alpha > \beta\) then \(\aleph_\alpha > \aleph_\beta\).

Lemma: \(\alpha \leq \aleph_\alpha\)

Proof: Intuitively this makes sense because there are large gaps in the ordinals between each cardinal. In practice we’re just going to prove it by transfinite induction.

Suppose \(\beta \leq \aleph_\beta < \aleph_\alpha\) for \(\beta < \alpha\).

Then if \(\alpha_\alpha < \alpha\) we would have \(\aleph_\alpha < \aleph_\alpha\), which is a contradiction. QED

It might be tempting to think that \(\alpha < \aleph_\alpha\) for all \(\alpha\) – at the earlier cardinals (e.g. \(\aleph_0, \aleph_1\)) the corresponding ordinal is unimaginably smaller than its \(\aleph\). This turns out to not be necessarily true, but providing you with a counter-example requires a lot of theory I’m disinclined to get into right now.

Theorem: Every cardinal is \(\aleph_\alpha\) for some ordinal \(\alpha\).

Proof: Let \(\kappa\) be some cardinal. Then \(\aleph_\kappa \geq \kappa\), so there is at least one ordinal such that its \(\aleph\) is larger than \(\kappa\).

Let \(\alpha\) be the smallest ordinal such that \(\aleph_\alpha \geq \kappa\).

Then \(\kappa > \aleph_\beta\) for \(\beta < \alpha\). Because \(\aleph_\alpha\) is chosen to be the minimal upper bound for the \(\aleph_\beta\), this means that \(\aleph_\alpha \leq \kappa\) and thus \(\aleph_\alpha = \kappa\) as desired. QED

And there you have it. The final piece in what I promised at the beginning of this series (modulo skipping a bit). I’ve taught you just enough set theory to make sense of \(\aleph_0\), \(\aleph_1\) and \(2^{\aleph_0}\), and probably more than enough to convince you that you don’t care.

There’s a hell of a lot more to this subject. However there’s not really a hell of a lot more to this subject that I know. Once you fill out the details I’ve elided, I’ve probably blogged about 10% of my set theory knowledge in this series of posts. I doubt I’ve even touched on 1% of what you need to get started on modern set theory research. Still, I hope it’s been an interesting journey and you now have a slightly better grasp of mathematical infinity.

This entry was posted in Numbers are hard on by .