# Simple example of uncountable ordinal

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.

-
Thank to all your answers. The proof I know is the one written by Cantor, in his work "Contributions to the founding of the theory of transfinite numbers", where he makes a complex demonstrations which involves a renumbering of all the ordinals, a lot of indexes, a limit, and so on... Cantor's original assertion is: "The power of the totality $\{a\}$ of all numbers $a$ of the second number-class is not equal to $\aleph_0$". –  zar Dec 27 '10 at 16:45
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$. –  Andres Caicedo Dec 27 '10 at 16:47

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$.

-
Carl, I would think that the difficulty the OP has is precisely with arguing that $\omega_1=\Omega$ is a set. –  Andres Caicedo Dec 27 '10 at 16:41
Well, this is simple! Very different from the original proof by Cantor. –  zar Dec 27 '10 at 17:04
(Andres, what does "OP" mean?) –  zar Dec 27 '10 at 17:06
(Original Poster) –  Andres Caicedo Dec 27 '10 at 17:21
Oh, ok, it's me :-) So the proof that $\omega_1$ is a set is not so obvious? Can you sketch it? –  zar Dec 27 '10 at 17:36

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$.

-
Could you please define the domain or range of $E$? (English is not my first language, I don't know that definition, sorry) –  zar Dec 27 '10 at 21:42
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)$. –  Andres Caicedo Dec 27 '10 at 22:40
Oh, ok, thanks. –  zar Dec 28 '10 at 9:33

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.

-
Thank you for the link. It says that $\omega_1$ is the least ordinal. Is it equal to the set of all countable ordinals? –  zar Dec 27 '10 at 17:03
$\omega_1$ is the least uncountable ordinal. Yes, its underlying set is the set of all countable ordinals. –  Pete L. Clark Dec 27 '10 at 18:23

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.

-
@Pete: I think you are right, but I am a great believer in AC. And when asking for a "simple proof" like this, I think OP is willing to accept it. But you make a good point. –  Ross Millikan Dec 27 '10 at 14:16
@Pete L. Clark: Most set theorists define cardinals to be certain kinds of ordinals. What requires AC is the statement that every set is bijectable with some cardinal. But if you want to treat cardinals as actual objects, like one does ordinals, then they are generally defined as those ordinals which are not bijectable with any strictly smaller (in the ordinal order) ordinal. –  Arturo Magidin Dec 27 '10 at 16:13
To clarify: We need some amount of choice to ensure that $\omega_1$, the first uncountable ordinal, injects into $2^{\aleph_0}$. This fails, for example, in Solovay's model where all reals are Lebesgue measurable. –  Andres Caicedo Dec 27 '10 at 16:19
@Pete L. Clark: your comment is right in spirit but there is a technical issue. In ZF without choice, by convention we don't define cardinal numbers to be a type of ordinal, because that would mean that we cannot be sure that every set has a cardinality, which would be absurd. So in ZF without choice we keep the fact that every set has a cardinality, and give up instead the theorem of ZFC that every cardinality contains an ordinal. There is a method called Scott's trick that can be used to select set representatives for all cardinalities in ZF without the axiom of choice. –  Carl Mummert Dec 28 '10 at 2:21
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. –  Pete L. Clark Dec 28 '10 at 3:20