It is probably a trivial question, but I have no clue about the answer. I know that the elements of $\omega_1$, the first uncountable ordinal, are the countable ordinals, of which there are uncountably many, but I am not sure if that applies to the number of limit ordinals before $\omega_1$ too.
6
$\begingroup$
$\endgroup$
asked Mar 22 '13 at 18:23
13
$\begingroup$
$\endgroup$
No: the set of countable limit ordinals has the same cardinality as the set of countable ordinals, i.e., $\omega_1$ (or $\aleph_1$, for those who prefer the aleph notation). Let $\Lambda$ be the set of non-successor countable ordinals (i.e., the countable limit ordinals together with $0$); then the map
$$\omega_1\to\Lambda:\alpha\mapsto\omega\cdot\alpha$$
is a bijection, where $\cdot$ is ordinal multiplication.
answered Mar 22 '13 at 18:24
-
1$\begingroup$ @julian: The bijection that I gave actually gives you the successor limit ordinal: the successor to $\omega\cdot\alpha$ is $\omega\cdot(\alpha+1)=\omega\cdot\alpha+\omega$. In general, if $\eta$ is any limit ordinal, countable or not, then $\eta+\omega$ (ordinal addition) is the next larger limit ordinal. $\endgroup$ – Brian M. Scott Mar 22 '13 at 18:40
-
1$\begingroup$ @julian: You’re confusing two rather different concepts. Look at the rational numbers: in their usual order no rational number has an immediate successor. However, there is a bijection $\Bbb N\to\Bbb Q$, and we can use that to define a different order on $\Bbb Q$ in which each rational does have an immediate successor. Assuming the axiom of choice, there is also a bijection $f$ from some well-ordered cardinal number $\kappa$ to $\Bbb R$, and we can use it to define a different order on $\Bbb R$ in which every element has a successor: the successor of $f(\xi)$ is $f(\xi+1)$. This isn’t ... $\endgroup$ – Brian M. Scott Mar 22 '13 at 18:52
-
1$\begingroup$ @julian: Uncountability simply means we can't inject into the natural numbers. There do exist uncountable well-ordered sets, though--such as $\omega_1$--and in a well-ordered set, you can always tell which one (if any) is "next" after a given element. The real numbers aren't well-ordered in the standard order, but even if they could be well-ordered, uncountability means that they still can't be matched one-to-one with the naturals. $\endgroup$ – Cameron Buie Mar 22 '13 at 18:55
-
1$\begingroup$ @julian: Being able to say which of two elements comes first just means that you have a linear (also called total) order; a well-order is a linear order in which each non-empty set has a first element. (Thus, $\Bbb N$ is well-ordered in its usual order, but $\Bbb Z$ is not.) If $\langle X,\le\rangle$ is some well-order, $x\in X$, and $S(x)=\{y\in X:x<y\}\ne\varnothing$, then $S(x)$ has a first element, and that element must be the successor of $x$. // It’s not hard to visualize a well-ordered set that isn’t ordered like $\Bbb N$, though this particular example can be rearranged to look ... $\endgroup$ – Brian M. Scott Mar 22 '13 at 20:21
-
2$\begingroup$ @julian: Because $\omega$ does not have an immediate predecessor; it’s simply the first ordinal larger than all of the natural numbers. However, even what you call a string need not be countable. Let $X$ be the set of all ordered pairs $\langle x,n\rangle$ such that $0\le x\in\Bbb R$, $n\in\Bbb Z$, and $n\ge 0$ if $x=0$. Linearly order $X$ by putting $\langle x,m\rangle\preceq\langle y,n\rangle$ iff $x<y$, or $x=y$ and $m\le n$. (This is called the lexicographic order on $X$. Then $\langle 0,0\rangle$ is the first element of $X$, ... $\endgroup$ – Brian M. Scott Mar 22 '13 at 20:52
5
$\begingroup$
$\endgroup$
Here is a slightly worse proof than that given by Brian.
Suppose that the $A$ is the set of countable limit ordinals, then $\bigcup A=\delta=\sup A$ is a countable limit ordinal, therefore $\delta\in A$, but this means that $\delta=\max A$. It is easy to see that $\delta+\omega>\delta$ and it is a countable limit ordinal, in contradiction to the fact that $\delta$ is the largest countable limit ordinal.
answered Mar 22 '13 at 18:57
-
$\begingroup$ Is "slightly worse" code for "using choice"? $\endgroup$ – Andrés E. Caicedo Mar 22 '13 at 19:00
-
$\begingroup$ Andres: Well, not that but it is also an indirect argument by contradiction, whereas Brian's answer is a clear and straightforward bijection. But nonetheless, LOL. :-) $\endgroup$ – Asaf Karagila♦ Mar 22 '13 at 19:29
-
$\begingroup$ yes, the argument seems clear. What is not clear is my mind (see my last comment on Scott's answer). There is no way I can imagine a string (meaning that there is one element next to another with nothing in between them) of elements that cannot be labeled by N. $\endgroup$ – Wolphram jonny Mar 22 '13 at 20:21
-
$\begingroup$ @julian: Use the fact that everything you can think about is really just a recursive function, or even primitive recursive function, and convince yourself that there is a non-recursive ordinal which is countable. Can you imagine any bijection between that ordinal and $\omega$? No, it's far too complicated. $\omega_1$ is really just "all the ways $\omega$ can be well-ordered". And it turns out that this is also an ordinal, and it cannot be countable for reasons similar to those in my answer above. $\endgroup$ – Asaf Karagila♦ Mar 22 '13 at 21:36
