12
$\begingroup$

Can you make a simple example of an uncountable ordinal? With simple I mean that it is easy to prove that the ordinal is uncountable. I know that the set of all the countable ordinals is an uncountable ordinal, but the only proof that I know is quite complicated.

  • 1
    Zar, the usual argument that the set $\omega_1$ of countable ordinals is an uncountable ordinal is as follows: To any countable ordinal $\alpha$ (by definition of countable) corresponds an $A\subseteq{\mathbb N}$ and$a$binary relation $E$ on $A$, so that $(A,E)\cong\alpha$. Of course, many different $(A,E)$ correspond to the same $\alpha$. We identify all of them (this is an equivalence relation). We order the relations by saying [(A,E)]<[(B,F)] iff $(A,E)$ is order isomorphic to a proper initial segment of $(B,F)$. This is a well-ordering, and its order type is precisely $\omega_1$.2019-02-06

4 Answers 4

18

The proof that the set $\Omega$ of all countable ordinals is uncountable is not difficult. First, it's an ordinal. Next, if $\Omega$ were countable, then $\Omega + 1$ would also be a countable ordinal. Finally, it is impossible for $\Omega + 1$ to be in $\Omega$, because that would mean that $\Omega + 1 < \Omega$.

11

Here is another way of arguing which is slightly different: Consider the set $X={\mathcal P}({\mathbb N}\times{\mathbb N})$ of all subsets of ${\mathbb N}^2$. Given $E\subseteq {\mathbb N}\times{\mathbb N}$, let $A_E$ be the set of all numbers that appear in either the domain or range of $E$ (this is sometimes called the field of $E$). If it happens that $E$ is a well-ordering of $A_E$, let $\alpha_E$ be the unique ordinal that is order isomorphic to $(A_E,E)$. Otherwise, let $\alpha_E=0$. Then $\{\alpha_E\mid E\in X\}$ is a set (is the image of $X$ under the map $E\mapsto\alpha_E$) and it is obvious that it consists precisely of the countable ordinals. One easily sees then that it is itself an ordinal, and uncountable (since no ordinal belongs to itself). This is $\omega_1$.

  • 1
    zar, the domain of $E$ is simply ${\rm dom}(E)=\{n\in{\mathbb N}\mid$ there is an $m\in{\mathbb N}$ such that $(n,m)\in E\}$, and the range of $E$ is ${\rm ran}(E)=\{m\in{\mathbb N}\mid$ there is an $n\in{\mathbb N}$ such that $(n,m)\in E\}$. The field of $E$ is then ${\rm dom}(E)\cup{\rm ran}(E)$.2010-12-27
5

The only two that I think have simple proofs are $\Omega$, as Carl says, and $2^{\aleph_0}$, the set of infinite binary sequences. Cantor's diagonal argument proves this one uncountable. Alternately, as all cardinals are ordinals, any cardinal greater than $\aleph_0$ is an uncountable ordinal just from the definition of countability. That's simple to write, but probably not what you are looking for.

  • 1
    Something about my previous comments was not clear, so I deleted them. All I'm saying is that $2^{\aleph_0}$ is not super-obviously an uncountable ordinal (it needs the theorem that any set can be well-ordered, which needs AC, which is fine, but the point is it isn't *obvious*), so is perhaps not the best answer to the question at hand, in that the Burali-Forti argument is simpler than the Well-Ordering Theorem.2010-12-28
4

The existence of an uncountable ordinal is established by the argument of the Burali-Forti "Paradox". See for instance Section 1.4 here. (Yes, this is the same argument as in Carl Mummert's answer.)

This is probably the simplest way to show the existence of an uncountable ordinal. As Section 1.2 of the notes linked to above shows, the usual operations of addition, multiplication and even exponentiation of ordinals do not produce uncountable ordinals from countable ones. That this is not the case for exponentiation is a big difference between ordinal and cardinal arithmetic.