5
$\begingroup$

My notes say that the ordinals $\omega + 1, \omega + 2, ... , 2 \omega, ... , 3 \omega, ... \omega^2, ... $ are all countable, and hence have cardinality equal to $\omega = \aleph_\mathbb{0}$. So I was wondering if it's fair to say that every ordinal has cardinality no greater than $\aleph_\mathbb{0}$?

Alternatively, I guess it's possible that that the sequence of infinite ordinals listed above, does not include some of the ordinals with a cardinality greater than the naturals.. but I wasn't sure.

$\endgroup$
  • 4
    $\begingroup$ en.wikipedia.org/wiki/First_uncountable_ordinal $\endgroup$ – Samuel May 18 '13 at 10:55
  • 2
    $\begingroup$ Now lets wait for Asaf :P $\endgroup$ – Isomorphism May 18 '13 at 11:01
  • $\begingroup$ What about $2^{\omega}$? $\endgroup$ – Metta World Peace May 18 '13 at 11:08
  • 2
    $\begingroup$ @MettaWorldPeace $2^\omega=\omega$, where $2^\omega$ is ordinal exponentiation. $\endgroup$ – Hanul Jeon May 18 '13 at 11:14
  • $\begingroup$ @tetori: Ah, my bad. Thank you for pointing . $\endgroup$ – Metta World Peace May 18 '13 at 11:21
7
$\begingroup$

You are not correct, of course, there are ordinals of unbounded cardinalities.

Note that it is sufficient to prove that there is a set of countable ordinals. If there is a set of countable ordinals, then Peter's hint completes the problem. To do that, note that you can find in $\mathcal P(\omega\times\omega)$ copies of every countable ordinal (as well-orderings of $\omega$). Conclude using replacement that countable ordinals make a set.

But there is another side to your question. Countable ordinals are closed under [definable] countable operations (and more if we assume the axiom of choice). This means that whenever we have a countable process (denoted in your post by $\ldots$) its limit is going to be countable as well. In order to get to $\omega_1$, the first uncountable ordinal we have to use a process which continues for uncountably many steps.

Therefore your suggestion that we increase by $1$, then increase by $\omega$, then multiply by $\omega$... all that is a description which is inherently countable, so you can't find a countable sequence whose limit is uncountable. In order to step up you need something stronger.

What two operations are stronger? Well, in $\sf ZFC$ there are two of them:

  1. Cardinal successor, which means that we go from the ordinal $\alpha$ to the least $\beta$ such that $\alpha<\beta$ - and there is no bijection between $\alpha$ and $\beta$. In the case of $\omega$ we end up at the first uncountable ordinal, known as $\omega_1$.
  2. Cardinal exponentiation, or its particular case - the power set operation. This assures us that we grow in cardinality, by Cantor's theorem. Assuming the axiom of choice, growing in cardinality means ordinals which are at least as large as the cardinal successor.

    Note that I'm talking about $\alpha\mapsto\ ^\alpha\beta$ for some $\beta>1$, of course.


Also relevant:

$\endgroup$
  • 2
    $\begingroup$ I am very interested to hear what the downvote signifies. $\endgroup$ – Asaf Karagila May 18 '13 at 13:42
  • $\begingroup$ I wonder if the downvotes have to do with the length of this answer, the user posting it, or its content. $\endgroup$ – Asaf Karagila May 19 '13 at 8:22
6
$\begingroup$

A hint to start you off. Take all the countable ordinals, ordered in size. Ask: are they well-ordered? if so, ask: What is the order-type of that sequence of objects? Is it an ordinal? Must it be bigger than any countable ordinal?

$\endgroup$
  • 2
    $\begingroup$ You also need to prove that this is a set, rather than a class. $\endgroup$ – Asaf Karagila May 18 '13 at 12:20
2
$\begingroup$

(In ZFC) by Cantor's theorem, $2^{\aleph_{0}}=\vert \mathcal{P}(\omega)\vert> \vert \omega\vert=\aleph_{0}$, so that $\vert P(\omega)\vert (\approx \mathbb{R})$ is an uncountable cardinal and therefore an uncountable (limit) ordinal (here $2^{\aleph_{0}}$ is cardinal exponentiation). The claim that $2^{\aleph_{0}}=\aleph_{1}$, i.e that the least cardinal strictly greater than $\aleph_{0}$ is $2^{\aleph_{0}}$, is known as Continuum Hypothesis.

$\endgroup$
  • $\begingroup$ You need to use the axiom of choice for that, though. $\endgroup$ – Asaf Karagila May 18 '13 at 12:19
  • 3
    $\begingroup$ Axiom of choice in which point exactly? $\endgroup$ – Edoardo Lanari May 18 '13 at 12:21
  • 2
    $\begingroup$ @Lana: It is consistent that there is no ordinal which is in bijection with $2^{\aleph_0}$, and in fact it is also consistent that the only ordinals that can be injected into the continuum are countable. $\endgroup$ – Asaf Karagila May 18 '13 at 12:26
  • $\begingroup$ @AsafKaragila Axiom of Choice to (be sure that we can) assign a cardinality to $\mathcal{P}(\omega)$ I suppose, right? $\endgroup$ – Marco Vergura May 18 '13 at 12:39
  • $\begingroup$ We can assign a cardinality to $\mathcal P(\omega)$ without the axiom of choice. It just that this cardinality need not be an $\aleph$-number, i.e. an ordinal. Namely, without the axiom of choice there can be cardinals which are not ordinals. See math.stackexchange.com/a/172326/622 and math.stackexchange.com/q/53770/622 and math.stackexchange.com/q/53752/622 for more information. $\endgroup$ – Asaf Karagila May 18 '13 at 12:44
2
$\begingroup$

The ordinal $\omega_1$ has cardinality $\aleph_1$ which is greater than $\aleph_0$. Similarly, $\omega_2$, $\omega_3$,.... has cardinalities which are all greater than $\aleph_0$.

You can say that every countable ordinal has cardinality which is not greater than $\aleph_0$, in fact the cardinality is equal to $\aleph_0$.

Note that the ordinals $\omega + 1, \omega + 2, ... , 2 \omega, ... , 3 \omega, ... \omega^2, ... $ are all countable ordinal, however $\omega_1$ is the first uncountable ordinal.

$\endgroup$
  • 6
    $\begingroup$ I'm wondering why you are using boldface font here. Boldface is used to emphasize a particular part of the answer. Here it uses to emphasize all, but one part, of the answer. $\endgroup$ – Asaf Karagila May 18 '13 at 13:15

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.