1
$\begingroup$

From the answers (and comments) to this question on the uncountability of countable ordinals I don't get a lucid picture:

How can I see that the uncountability of the set of countable ordinals is exactly at most the uncountability of the reals – and no bigger one?

(Assuming the continuum hypothesis, it cannot be a smaller one.)

I mean: We are shown that there are so tremendously many countable ordinals, and that they can get really tremendously large (in terms of "greater than their predecessors"), so one can lose the plot.

$\endgroup$
  • 3
    $\begingroup$ "How can I see that the uncountability of the set of countable ordinals is exactly the uncountability of the reals – and no bigger one?" This is false; you need to replace "exactly" with "at most". By definition, $\omega_1$ is the first uncountable ordinal, so the answer to the question in the title is "Barely." Under choice, the first uncountable ordinal is the fist uncountable size. On the other hand, the reals can be much much larger than that. You need to clarify the question so the answer is not "by definition" or "read this proof". $\endgroup$ – Andrés E. Caicedo Nov 28 '13 at 16:58
  • $\begingroup$ I worry the question will be answered with "By definition": $\mathbb R$ is uncountable, so it has size at least $\omega_1$. This is surely not what you are after. (Making the statement true shifted the focus from $\omega_1$ to $\mathbb R$.) $\endgroup$ – Andrés E. Caicedo Nov 28 '13 at 17:12
10
$\begingroup$

The set of countable ordinals as as least uncountable as can be. It is exactly the ordinal $\omega_1$ and has size $\aleph_1$. The real numbers, on the other hand, are provably uncountable, but can have an arbitrarily large cardinality. So it would be at least of size $\aleph_1$ (in $\sf ZFC$, anyway).

As for the term "see", if the above explanation is not sufficient and you are looking for a geometric visualization then you're asking for trouble. While we can easily understand the real numbers as a "line" the ordinals are more difficult because they have limit points, but $\omega_1$ has so many limit points that just drawing the limit points, or the limit of limit points, or the limit of limit of limit points, and so on, all that would amount to the same drawing.

So it becomes hard to visualize $\omega_1$, and these visualizations never help us understand the cardinality of anything anyway. But wait, it gets worse.

Given $M$ a [countable] transitive model of set theory, and $\alpha$ is an uncountable ordinal in $M$, there is a generic extension of $M$ where $\alpha$ is in fact countable internally. The fact it is a generic extension tells us that there are no new ordinals, so without adding new ordinals we made the ordinal countable.

So it's hard to get an accurate image of $\omega_1$. My rule of thumb is that whatever you think it is, it's larger, much larger. But still quite small -- being the least uncountable ordinal. And $\Bbb R$ is at least as big.

$\endgroup$
  • 2
    $\begingroup$ Would the downvoter explain their downvote? $\endgroup$ – Asaf Karagila Nov 28 '13 at 19:34
  • $\begingroup$ I think that it’s a nice, comfortable size: big enough to be interesting and useful, and small enough to be more or less manageable! $\endgroup$ – Brian M. Scott Nov 28 '13 at 19:51
  • $\begingroup$ Brian, within a fixed universe of $\sf ZFC$. But who wants that? :-) $\endgroup$ – Asaf Karagila Nov 28 '13 at 22:18
  • 3
    $\begingroup$ $\huge\mathsf{ME!}\quad\overset{\cdot\cdot}\smile$ $\endgroup$ – Brian M. Scott Nov 28 '13 at 22:20
  • $\begingroup$ Stop being such a Platonist! $\endgroup$ – Asaf Karagila Nov 28 '13 at 22:22
6
$\begingroup$

To add a little bit to Asaf's answer, there are a couple of reasons why it is difficult to "see" (meaning visualize) the fact that $|\omega_1| \le |\mathbb{R}|$. By this fact I mean the existence of an injection $\omega_1 \to \mathbb{R}$.

First, some fragment of the Axiom of Choice (more than the principle of Dependent Choices) is needed to prove this. There are models of $\mathsf{ZF} + \mathsf{DC}$ in which neither $\omega_1$ nor $\mathbb{R}$ injects into the other, meaning that the two sets are incomparable in cardinality. Constructions that make fundamental use of the Axiom of Choice beyond $\mathsf{DC}$, such as the Banach–Tarski paradox, tend to be hard to visualize.

Second, even assuming $\mathsf{AC}$ there cannot be an order-preserving injection $\omega_1 \to \mathbb{R}$. In other words, no set of reals with its usual ordering can be isomorphic to $\omega_1$. This is because if $f: \omega_1 \to \mathbb{R}$ were an order-preserving injection then the open intervals $(f(\alpha),f(\alpha+1))$ for $\alpha < \omega_1$ would all be disjoint—but because $\mathbb{R}$ is separable it has the countable chain condition, meaning that every pairwise disjoint family of open sets in $\mathbb{R}$ is countable. For me it is difficult to visualize any linear ordering that does not embed into the real line.

By the way, in order to answer the question in the title, "how uncountable is the set of countable ordinals," I'm not sure that a comparison with the set of reals will be helpful; the parallel question "how uncountable is the set of reals" can be thought of as a harder question (the Continuum Hypothesis.) To answer the question in the title it might be better to study the construction of $\omega_1$ on its own, as the Hartogs number of $\omega$, and leave $\mathbb{R}$ out of it.

$\endgroup$
6
$\begingroup$

Although, as Trevor wrote, you need the axiom of choice if you want to map the set $\omega_1$ of countable ordinals one-to-one into the reals, there are explicitly definable maps of the reals onto $\omega_1$, which might provide some intuition for why $\omega_1$ is "small". Here's one such map. First, map every non-negative integer (in $\mathbb R$) to itself (considered as an element of $\omega_1$); this is just to get the finite ordinals out of the way for the following construction. Next, let $C$ be the set of those reals in the interval $(0,1)$ whose decimal representation involves only the digits 5 and 6. (There's nothing special about 5 and 6, but I want to avoid 0 and 9 so that I needn't worry about a number having two decimal representations.) For any $x\in C$, consider the set $R_x$ of those ordered pairs $\langle m,n\rangle$ of natural numbers for which the $2^m3^n$-th digit in $x$ is 5. If $R_x$ happens to be a well-ordering of the set $\omega$ of all natural numbers, then map $x$ to the order-type of that well-ordering. This ensures that the map will map onto all countable ordinals. Finally, for those real numbers that I haven't yet mapped anywhere (because they're not natural numbers and either they're not in $C$ or the associated $R_x$ isn't a well-ordering of $\omega$), map them to any countable ordinal you like, say 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.