# Ordinals and Countability

I've been watching Prof Su's (Harvey Mudd College) incredible lecture on Ordinals and Transfinite Induction, and I have a few related questions. He starts by drawing and examining three sets of dots, strictly well-ordered by position ($> \implies \text{to the right of}$), where clustered dots represent carrying on adding dots forever:

(a) $\{\cdot \cdot \cdot \ \cdot \}$

(b) $\{ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdots$ } ($\mathbb{N}$)

(c) $\{ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdots \ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdots \ \cdot \cdot \ \cdot \}$ (2 sets of $\mathbb{N}$ + 3 other things to the right)

He then notes that there are finitely many things in (a) and countably many things in both (b) and (c). Therefor (b) and (c) have the same cardinality. My first question is how can we say that (c) is countably infinite? Isn't the definition of a countable set a set that can be put in to bijection with some subset of (or the entirety of) $\mathbb{N}$? I get how that's true for (b), but what bijection could you use for (c) that would map every element of (c) to an element of the $\mathbb{N}$, and preserve distinctness? Wouldn't you run out of places to map things to after the first set of dots?

Next he constructs the ordinal numbers as a way to classify well-ordered sets. An ordinal is defined to be a set that is:

(i) transitive/complete - every member is a subset, and

(ii) strictly well ordered by membership

We start off with $\phi$ (the empty set, which is vacuously well-ordered) and define, the Successor function:

$$S(\alpha) = \alpha \ \cup \ \{ \alpha \},$$

which ensures that $S(\alpha)$ will satisfy (i) and (ii) if $\alpha$ does, and helps us to define the "next" few ordinals:

$$\{ \phi \}, \ \{ \phi, \{\phi \} \}, \ \{ \phi, \{\phi \}, \{ \phi, \{\phi \} \} \}, \ \dots$$

We can also define the Supremum function for a set set of ordinals, A:

$$\sup(A) = \bigcup\limits_{i} a_{i}, \ a_{i} \in A$$

If A is a collection of ordinals, then $\sup(A)$ is also an ordinal

We can then start assign labels to ordinals:

$$"0" \to \phi, \ "1" \to \{ \phi \}, \ "2" \to \{ \phi, \{\phi \} \},$$ etc.

He then introduces a theorem by Von-Neumann:

Thm. Any well-ordered set is order isomorphic to one of the ordinals

e.g. (a) is order isomorphic to "4".

He then goes on to say that $\mathbb{N}$ is order isomorphic to the supremum of the successor of all the finite ordinals, which we call $\omega$:

$$\omega \equiv \sup( \ S(\alpha): |\alpha|<\infty)$$

This is said to be a limit ordinal and the first infinite ordinal. It is also the first ordinal that is not a successor of any ordinal. From there, we can continue to take the Successor:

$$S(\omega) = \omega \cup \{ \omega \} \to "\omega + 1"$$

and we're off to the races. We have, in order:

$$1, 2, 3, \dots, \omega, \omega + 1, \omega + 1, \dots \omega\cdot 2, \omega\cdot 2 + 1, \omega\cdot 2 + 2, \dots \omega\cdot 3, \dots \omega^2, \omega^2 + 1, \omega^2 + 2, \dots \omega^2 + \omega, \dots \omega^3, \dots \omega^4, \dots, \omega^{\omega}, \dots \omega^{{\omega}^{\omega}}, \dots,$$

all of which are apparently countable, even as we move through $\epsilon_{0}$, which is defined to be the first ordinal that satisfies: $\epsilon_{0} = \omega^{\epsilon_0}$. Then we have $\epsilon_{1}$ which also satisfies this (i.e. $\epsilon_{1} = \omega^{\epsilon_{1}}$) but is not the first to do so... and $\epsilon_2, \epsilon_3,$ etc. all of which are apparently countable, until we get to $$\boxed{\omega_1},$$ defined to be the supremum of all of the countable ordinals, which is the first uncountable ordinal.

My second set of questions is How can anything after $\omega$ by countable? isn't the set $\omega + 1$ too big to be put in bijection with $\mathbb{N}$? And how can the union of an infinite number of things (the Supremum of all the countable numbers) be said to be uncountable, if we've already had limit ordinals before, that we say are still countable, that are unions of infinite numbers infinite sets. Shouldn't they start to be uncountable at $\omega$?

What am I not understanding here?

## 4 Answers

The other answers address your first question; let me tackle the second.

Note that if $\alpha$ is countable, so is $\alpha+1$ (Hilbert's hotel). So $\omega_1$ (this is the standard notation for the supremum of the countable ordinals) can't be countable, since otherwise $\omega_1+1$ would also be countable and we would therefore have to have $\omega_1\ge\omega_1+1$, by definition of $\omega_1$. Basically, $\omega_1$ is the first thing you get after you've run out of countable ordinals, so it clearly can't be countable!

As far as intuition goes, I would argue that makes it different from countable limit ordinals - even really big ones like $\epsilon_0=\omega^{\omega^{\omega^{. . .}}}$ - is cofinality. Basically, each countable limit ordinal can be written as a countable limit of smaller countable ordinals. This is not true for $\omega_1$: the countable union of countable sets is countable (technically this uses a very small amount of choice), so if $\alpha_1<\alpha_2<\alpha_3< . . . <\omega_1$, then $\sup\{\alpha_i: i\in\mathbb{N}\}$ is also less than $\omega_1$.

• What is the proof that you ever actually do run our of countable ordinals? – D. W. May 1 '16 at 1:35
• @D.W. Great question! By definition if $\alpha$ is countable then $\alpha$ can be put into bijection with $\mathbb{N}$. This means that there is a binary relation $R_\alpha$ on $\mathbb{N}$ (not unique of course) such that $\mathbb{N}$, ordered by $R_\alpha$, "looks like" $\alpha$. (Formally: $(\mathbb{N}, R_\alpha)$ has order type $\alpha$.) This proves that the countable ordinals form a set (since the collection of such $R_\alpha$s is a set, by Powerset and Separation). Now, order this set by "is longer than" and (exercise) you get an ordinal; but (exercise) it is uncountable. (cont'd) – Noah Schweber May 1 '16 at 1:40
• In fact, this ordinal is just $\omega_1$! You may hope for a more "concrete" description of $\omega_1$, but - for various meanings of the word "concrete" - we can prove that can't happen (this is developed in the field descriptive set theory). Note that a similar argument shows that given any set $A$, there is an ordinal which does not inject into $A$, and (Burali-Forti) that the collection of all ordinals is therefore not a set, but a proper class. – Noah Schweber May 1 '16 at 1:42
• When/why would I ever run out of $R_{\alpha}$s? For every next $\alpha$ ($S(\alpha)$), couldn't I just map the next $R_{\alpha}$ to the next element in $\mathbb{N}$ ad infinitum? – D. W. May 1 '16 at 1:46
• You've just argued that there isn't a "last" countable ordinal, and this is exactly right. However, because of limit ordinals, this doesn't mean we never run out! It's analogous (but slightly more complicated) to the fact that there are non-finite ordinals. At first it might seem like we can't run out of finite ordinals - given any finite $\alpha$, $\alpha+1$ is also finite - but we do in fact run out after $\omega$-many steps. Note, in particular, that the moment we run out is exactly the first non-finite ordinal! Similarly, we run out of countable ordinals at stage first-uncountable-ordinal. – Noah Schweber May 1 '16 at 1:50

(c) $3,5,7,9,\dots$, $4,6,8,10,\dots$, $0,1,2$.

$\omega + 1 \longleftrightarrow 1,2,3,4,\dots,0$.

That's how all those sets are countable.

• Wow, very nice, thank you. But how can you continue to do this for things like $\omega^{\omega}$ and onward? – D. W. May 1 '16 at 1:28
• You can use that $\omega\times\omega$ is biyective with $\omega$ (that's one of Cantor's ideas). – Pedro Sánchez Terraf May 1 '16 at 1:30

To answer your first question,

Define a function $f(n)$ such that $f(0)$ maps to the first of the three finalmost elements, $f(1)$ maps to the second, and $f(2)$ to the third. For each positive integer greater than 2, let $f(n)$ map 3 as the first element of the first group, 4 as the first element of the second, 5 as the second element of the first, and so on, alternating between each of the two countable clusters of elements.

• Wonderful, keep forgetting (or failing to conceptualize) that you'll never run out of things to map from in $\mathbb{N}$ – D. W. May 1 '16 at 1:26
• Keep in mind that for all integer n, $\mathbb{N}^n$ has the same cardinality as $\mathbb{N}$ – Neil May 1 '16 at 1:28
• What kind of bijection can you construct from $\mathbb{N}$ to $\mathbb{N}^n$ – D. W. May 1 '16 at 1:30
• First, note that a bijection from $\mathbb{N}$ to $\mathbb{N}^2$ is sufficient, as from there you can biject iteratively. Some people like to simply draw out $\mathbb{N}^2$, and then draw a certain type of winding, crooked curve, but that strikes me as a little informal. Let $f(m,n)=2^m(2n-1)$. – Neil May 1 '16 at 1:32
• Do you mean $2^m(2n+1)$? Wouldn't $f(0,0)=-1 \not\in \mathbb{N}$ – D. W. May 1 '16 at 1:39

To answer your first question as simply as possible, if we look at set c, take the the three elements at the end, and consider them mapped onto 1, 2 and 3 in the set of natural numbers. If we then map the first element of the first set of b within c and map that to 4, the first element of the second set of b within c onto 5, the second element of the first set of b within c onto 6 and so on and so forth, we have a bijection between c and the set of natural numbers.

In answering the first question we can solve the second problem easily, if you have the successor ordinal: ω + 1, we map the +1 onto 1, the next the each element of ω onto the set of the natural number set in turn. Any countable ordinal works this way, even ε0, we map ω onto 1, ω^ω onto 2 An day so on and so forth for each well ordered element within ε0, the fact that it is well ordered means it has a mapping function onto the set of natural numbers.

Hopefully this helps, I tried to explain this in a way that’s would make sense to people that aren’t very familiar with these concepts. I remember watching a good YouTube series on this topic once, so there are resources out there to help people starting to learn this section of set theory.