1
$\begingroup$

Possible Duplicate:
Uncountability of countable ordinals

How does one prove that there are uncountable number of countable ordinals? Obviously, there are equal to or more than countable number of ordinals, but not sure how to prove there are uncountable number of countable numbers. Maybe, should I just assume that as uncountable ordinal has uncountable elements as a set, there should be uncountable number of countable ordinals?

  • 1
    The first uncountable ordinal is the set of all lesser ordinals, that is all countable ordinals. Perhaps you want to know what guarantees the existence of the first uncountable ordinal?2012-09-17

2 Answers 2

5

If $A$ is a countable set of countable ordinals, let $\beta=\sup\{\alpha+1:\alpha\in A\}$; then $\beta$ is countable, and $\alpha<\beta$ for every $\alpha\in A$. Thus, the set of countable ordinals cannot be countable.

Added: To see that $\beta$ is countable, just note that $\alpha+1$ is clearly countable if $\alpha$ is, so $\beta=\bigcup_{\alpha\in A}(\alpha+1)$ is a countable union of countable sets. This actually also covers the existence of $\beta$: given the set $\{\alpha+1:\alpha\in A\}$, whose existence follows from the axiom schema of replacement and the fact that $A$ is a set, the union axiom ensures the existence of $\sup\beta$.

  • 0
    This argument has the technical disadvantage of using choice (otherwise, we cannot prove that the supremum of a countable set of ordinals is countable). The existence of $\omega_1$ can be established without choice, and this gives the result. For details, see: http://math.stackexchange.com/questions/46833/how-do-we-know-an-aleph-1-exists-at-all/46836#468362012-09-17
3

Define $\Omega$ to be the smallest uncountable ordinal. It exists because uncountable ordinals exist, and ordinals are well-ordered (any nonempty class of ordinals has a smallest member).

Now $\Omega$ is the set of all countable ordinals, but it is itself uncountable by construction.

  • 0
    @ZhenLin: Of course. And that requires the e$x$istence of some uncountable set, together with the ability to well-order it. But if we want to pick nits, Brian's answer does leave open the possibility that all the countable ordinals taken together does not constitute a set. Nothing wrong with that, but then he should not have referred to the set of countable ordinals either. He still has a perfectly good proof that no countable set can contain all countable ordinals.2012-09-17