16
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ Ask Google: first uncountable ordinal immediately gives this, see also this $\endgroup$
    – t.b.
    Oct 11, 2011 at 14:59
  • 6
    $\begingroup$ But you were just told that this is not an adequate construction of all ordinals, much less a "standard way" to construct them. $\endgroup$ Oct 11, 2011 at 15:38
  • 1
    $\begingroup$ Of course there are only countably many ordinals with names, since there are countably many names :) $\endgroup$ Jun 2, 2012 at 18:05
  • $\begingroup$ I think for some audiences, none of the answers to this question are satisfactory and this question needs an answer that breaks the intuition that because you can never think of uncountably many ordinal numbers as you think of stronger systems of ordinal numbers, all ordinal numbers are countable. Maybe somebody can write an answer that breaks that intuition just like Asaf Karagila's answer to "ZF — Sets that can be proven to exist" breaks the intuition that there are only countably many sets. $\endgroup$
    – Timothy
    Apr 16, 2018 at 2:14
  • $\begingroup$ Does my answer at matheducators.stackexchange.com/questions/689/… answer your question? $\endgroup$
    – Timothy
    Jan 15, 2019 at 6:16

5 Answers 5

24
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ I think you have to do a little bit more work to say that $\alpha$ is the smallest uncountable ordinal. The argument above only shows that it's uncountable. $\endgroup$
    – kahen
    Oct 11, 2011 at 15:13
  • 9
    $\begingroup$ @kahen, the ordinals are well-ordered by $\in$, so every ordinal smaller than $\alpha$ is a member of $\alpha$ and thus, by definition, countable. $\endgroup$ Oct 11, 2011 at 15:36
  • 2
    $\begingroup$ This answer and the (essentially equivalent) one by Asaf Karagila rely on conventions unknown to Cantor. But Cantor proved that the set of all countable ordinals is uncountable. There should be a way to do this that doesn't require encoding ordinals as von Neumann ordinals. $\endgroup$ Oct 12, 2011 at 1:44
  • 4
    $\begingroup$ The problem with this argument is that you didn't prove that there is a set of all countable ordinal numbers. You could apply the same argument to the set of all ordinal numbers to derive the Burali-Forti paradox. See math.stackexchange.com/questions/216229/…. For those who have already learned that it has been proven without the axiom of choice that uncountable ordinal numbers exist, this answer might be good enough. $\endgroup$
    – Timothy
    Oct 29, 2017 at 2:12
  • $\begingroup$ Sir if there is infinite descending sequence of ordinals then what? $\endgroup$ Sep 22, 2019 at 16:02
8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I'm confused by the fact: is $\{ \{ \emptyset \} \}$ not downwards closed? Meaning it has a least element with respect to $\in$, or what does downwards closed mean? $\endgroup$ Jan 17, 2012 at 19:29
  • 2
    $\begingroup$ $\{\{\varnothing\}\}=\{1\}$ is not downwards closed. $A$ is downwards closed if $\beta\in A,\alpha<\beta\rightarrow\alpha\in A$. In the case of ordinals, which are transitive sets this is the same as to say $\beta\in A\rightarrow\beta\subseteq A$. $\endgroup$
    – Asaf Karagila
    Jan 17, 2012 at 19:31
  • $\begingroup$ Ah, I didn't know what downwards closed means. Thanks, Asaf! $\endgroup$ Jan 17, 2012 at 19:33
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 1) You have to consider the finite ordinals too, otherwise this logic fails. 2) From this explanation it's absolutely not clear why $f(n)<\alpha$: for example, $\{4,5\}$ is order-isomorphic to $\{0,1\}$, but I still don't believe that $4<2$... $\endgroup$ Sep 21, 2019 at 21:51
  • $\begingroup$ (1) The finite oridinals only add an $\omega$ to the front of the ordering. Since $\alpha > \omega$, this disappears, i.e., $\omega + \alpha = \alpha$. (2) You can define the next ordinal to be the order type of all the ordinals so far. Since this list is supposed to contain all the countable ordinals, its order type will be the next ordinal after them. If this is countable, it also needs to be on the list though. Which gives the contradiction. $\endgroup$
    – weux082690
    Sep 26, 2019 at 0:17
  • $\begingroup$ Don't get it at all: (1) $\omega + 1 > \omega$, but $\omega+\omega+1 \ne \omega + 1$. (2) You have only the fact, that your ordinal $\alpha$ is order-isomorphic to $\alpha^\prime$: the well-ordered set of all countable(and infinite!) ordinals. So by now it can happen that $f(1)=\omega, f(2)=\omega+1...; \alpha=\omega$. To show that $x<\alpha$ for each $x\in \alpha^\prime$ you need to add all the finite ordinals to $\alpha^\prime$, then show that $\alpha^\prime$ is an ordinal! It is exactly what mercio suggested in his answer. And why then do you need ordering on $\mathbb{N}$ and $f(n)$ at all? $\endgroup$ Sep 27, 2019 at 1:01
3
$\begingroup$

I will prove without assuming the axiom of choice that there are uncountably many countable ordinals. First, I will show that there is a set of all countable ordinals.

Take the set of all well-ordering relations on the set of all natural numbers. Let $f$ be the function that assigns to each of the relations in that set its order type. By the axiom of replacement, there is a set of all images of that function, and that's the set of all infinite countable ordinals. By the axiom of union, the union of that set and the set of all finite ordinals is also a set, and that's the set of all countable ordinals.

By definition, $\omega_1$ is the smallest ordinal such that the set of all ordinal numbers smaller than it is uncountable if such an ordinal exists. The supremum of the set of all countable ordinals is $\omega_1$ so $\omega_1$ exists. Therefore, the set of all countable ordinals is uncountable.

$\endgroup$
6
  • $\begingroup$ Comments are for suggesting how to improve a question or answer so I don't see how this answer would be suitable as a comment. Is it that Stack Exchange is for really good experts who find marcio's answer satisfactory because they're quite well aware that's it's even a theorem of ZF let alone ZFC that $\omega_1$ exists? Also, en.wikipedia.org/wiki/Ordinal_number gives an alternate equivalent definition of an ordinal number which is the definition I used. $\endgroup$
    – Timothy
    Dec 17, 2017 at 4:03
  • 1
    $\begingroup$ If $\omega_1$ does not exist, then the collection of countable ordinals is not even a set, let alone a countable set. Your answer here is irrelevant. $\endgroup$
    – Asaf Karagila
    Dec 17, 2017 at 13:02
  • $\begingroup$ I don't see what's wrong with my answer. Don't I need to show that there is a set of all countable ordinals to show that there are uncountably many countable ordinals. $\endgroup$
    – Timothy
    Dec 18, 2017 at 1:12
  • 1
    $\begingroup$ No, you don't. Saying something is countable automatically implies it is a set. If there is no set of countable ordinals, then there are uncountably many of them. As a side note, insisting on working without choice is not always the right thing, and certainly not from a pedagogical point of view. Yes, some things deserve to be mentioned, but sometimes comments are enough. $\endgroup$
    – Asaf Karagila
    Dec 18, 2017 at 6:36
  • $\begingroup$ @AsafKaragila A lot of people might think saying "there are uncountably many ordinals" is another way of saying "the set of all countable ordinals is uncountable" and like my answer for that reason. For those who know it really means "there is no countable set of all ordinals", my answer also proves the answer to that interpretation of the question is yes. Also, the body of the question seemed to ask how can it be that uncountable ordinals exist and my answer proves they exist. $\endgroup$
    – Timothy
    Jan 22, 2018 at 21:23
0
$\begingroup$

Not sure, if people aren't making this too difficult by looking at a generalized case.

If you look at the successor cardinal of Omega, it is the union of all ordinals lower than itself. If there only were countably many, then it would be a union of countably many countable sets, hence countable itself.

$\endgroup$
3
  • 1
    $\begingroup$ It could be that there is no set of all countable ordinals, so that all ordinals are countable. What does your sketch do in that case? $\endgroup$ Nov 22, 2018 at 19:54
  • $\begingroup$ By Omega, do you mean $\omega$? Omega ($\Omega$) tends to mean something else. You talk of the successor cardinal of $\Omega$, so you seem to be already assuming its existence. $\endgroup$ Nov 22, 2018 at 19:58
  • 1
    $\begingroup$ Without the axiom of choice, it is possible that some countable unions of countable sets are uncountable. Your argument does not seem to address this option, and yet the existence of $\omega_1$ does not require the axiom of choice. $\endgroup$ Nov 22, 2018 at 20:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .