I'm reading a book on stochastic games which apparently needs ordinals somewhere. This is the first time I meet a concept, and although the definition is clear to me, the lack of practice makes it harder to think of them. That's why I need some help with examples.

As far as I understood, the ordinals are exactly equivalence classes w.r.t. order isomorphism of well-ordered sets. In the Wikipedia article on the topic there is a remark, saying that formally such classes are too big to be sets in ZF system of axioms, so one shall rather talk about order types - OK for me as well, so far it is all quite natural.

  1. I can also imagine sets which have order types of the ordinal $\xi = 5$ or $7$, or any other natural number - this would be just any well-ordered set with $5$ or $7$ elements, right? It's easy for me to think of $\omega$ as well: one of the examples that has such order type is the set of all natural numbers.

  2. What is harder for me, is to find an example of a set which has order types of $\omega+1$, $2\cdot \omega$, $\omega^2$ or $\omega^\omega$. Even more, for the latter I used to think that this is an unordered set of all infinite sequences of natural numbers. However, still it reads that $\omega^\omega$ is a countable ordinal.

It would be nice if the example for $\omega+1$ would be something more intuitive than $\omega+1$ itself (which perhaps is not even a set, right?), such as $\Bbb N$ for $\omega$.


First thing first, let's answer the simple thing: $\omega^\omega$ can be used to denote both the ordinal and cardinal exponentiation. The former is indeed countable, but the latter is not. Yes, it's quite confusing.

Now, if you want to understand countable ordinal slightly better, you can think about them in terms of sequences of rational numbers.

For example, $\omega+1$ is the order type of $\{\frac{n}{n-1}\mid n\in\Bbb N\}\cup\{1\}$. Or in terms of reordering of $\Bbb N$ itself, set $0$ to be larger than all the other numbers. In that case $\omega^2$ would be the lexicographic order of $\Bbb N^2$, and $\omega^4+\omega$ would be the lexicographic order of $\Bbb N^4$ followed by a copy of $\Bbb N$ which is larger than all of them.

I like to think about ordinals as the line to the bathroom, this means that $\omega$-th place is the least place which has infinitely many people before that guy in line, but all those have only finitely many people before them. The poor guy is going to explode before he sees a toilet.

  • $\begingroup$ Thanks, Asaf - this is clear, besides the point that I was sure the guy is going to take a shower before I saw the last word of your reply. Shall I think of $\omega^\omega$ then as $\Bbb N$ copies of $\Bbb N$ where each element in the one row is strictly smaller than any element in the next row? $\endgroup$ – Ilya Jun 7 '13 at 10:25
  • 1
    $\begingroup$ Ilya, $\omega^\omega$ can be thought of as ordering all the polynomials with coefficients in $\Bbb N$, with order being inversely lexicographically (we start with the largest elements, which is fine since only finitely many coordinates are non-zero). $\endgroup$ – Asaf Karagila Jun 7 '13 at 10:30
  • $\begingroup$ Also, if infinitely many people have to take a shower before you, then you'll stink to the seven hells; if they use the toilet before you... then it stinks to the seven hells. I don't know what's worse. $\endgroup$ – Asaf Karagila Jun 7 '13 at 10:32
  • $\begingroup$ Since the $\omega$-guy will never use it, it doesn't matter to him anyways. $\endgroup$ – Ilya Jun 7 '13 at 10:37
  • $\begingroup$ Ilya, if he is a set theorist he will. $\endgroup$ – Asaf Karagila Jun 7 '13 at 10:38

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.