Uncountability of countable ordinals

According to Wikipedia, there are uncountably many countable ordinals. What is the easiest way to see this? If I construct ordinals in the standard way, $$1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega +2,\ \ldots,\ \omega\cdot 2,\ \omega\cdot 2 +1,\ \ldots,\ \omega^{2},\ \ldots,\ \omega^{3},\ \ldots\ \omega^{\omega},\ \ldots,\ \omega^{\omega^{\omega}},\ \ldots, \epsilon_{0},\ \ldots$$ I seem to get only countably many countable ordinals.

Solution 1:

Let $\alpha$ be the set of all countable ordinals.

It is an ordinal : if $\beta \in \alpha$, then $\beta \subset \alpha$ because the elements of $\beta$ are countable ordinals.

It is uncountable : if it were countable, $\alpha$ would be a member of itself, so there would be an infinite descending sequence of ordinals.

Therefore, $\alpha$, the set of all countable ordinals, is the smallest uncountable ordinal.

Solution 2:

Fact: If $A$ is a set of ordinals which is downwards closed, then $A$ is an ordinal.

Now consider the following set: $A=\{\alpha\mid\exists f\colon\alpha\to\omega,\ f \text{ injective}\}$, this is the set of all countable ordinals.

If $\alpha\in A$ then clearly $\beta<\alpha$ implies $\beta\in A$, simply because $\beta\subseteq\alpha$. We have, if so, that $A$ is itself an ordinal. If $A$ was a countable ordinal then $A\in A$, which is a contradiction. Therefore $A$ is uncountable, in fact $A$ is the least uncountable ordinal, also known as $\omega_1$.

There are just many ordinals which you cannot describe nicely. It just shows you that you can well order a countable set in so many ways...

Solution 3:

I have searched and searched for an answer to this question that makes intuitive sense and have yet to find one. So, after some thought of my own, this is what I came up with.

Suppose that the countable ordinals were countable. Let f be a one-to-one correspondence between the natural numbers and every well-ordering of the natural numbers. For instance:

1 <--> 1 < 3 < 5 <... 2 < 4 < 6 <...
2 <--> 1 < 2 < 3 < 4 <...
3 <--> 1 < 2 < 4 < 8 <... 3 < 6 <... 5 < 10 <...
...

Then, you only need to show there is a well-ordering of the natural numbers that is not on this list.

For each natural number $n$, let $f(n)$ be the order type of the ordering corresponding to $n$. Following the example list above, $f(1) = \omega*2$, $f(2) = \omega$, $f(3) = \omega^2$, and so on. Define an ordering on the natural numbers from $m < n$ iff $f(m) < f(n)$. This ordering of the natural numbers is a well-ordering since the ordering of the ordinals is a well-ordering. Therefore, it has some order type, call it $\alpha$. For all $n$, $f(n) < \alpha$, which follows from each ordinal being order-isomorphic to the ordered set of ordinals less than it. We are assuming $\alpha$ is countable, so it must be somewhere in our list, say $f(n) = \alpha$. But $f(n) < \alpha$ also, which is the contradiction we want. Therefore, $\alpha$ is nowhere on the list. Therefore, the countable ordinals are uncountable.

As far as whether the countable ordinals are the first uncountable ordinal, use again the fact that each ordinal is order-isomorphic to the ordered set of ordinals less than it. The order type of the countable ordinals must be the first uncountable ordinal, because all ordinals less than it are countable, from the order-isomorphism with the countable ordinals.