6
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 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$

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.

$\endgroup$
  • $\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

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.