Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to understand the relation between ordinals and well founded relations on $\mathbb N$. I found a nice starting point here cut-the-knot/ordinals.

Ordinals start like this 0={}, 1={0}, 2={0,1}, 3={0,1,2}, ..., $\omega$={0,1,2,3,...}, $\omega+1$={0,1,2,3, ..., {$\omega$}}, ..., $2\omega$={0,1,2,3,...,{$\omega$},{$\omega+1$},...} and $\beta < \alpha$ iff $\beta \in \alpha$.

The rank of a well founded relation $\langle \mathbb N, <_\alpha \rangle$ is the least ordinal $\alpha$ for which you have an order preserving map $\alpha \to \mathbb N_{<_\alpha}$ that embeds all ordinals strictly less than $\alpha$ into the countable set.

Here I define some well orderings with specific ranks

We easily define well founded relations of rank $n \in \mathbb N$ by e.g. $a <_7 b$ iff $a < b$ and $a,b < 7$.

The normal relation $\langle \mathbb N, < \rangle$ has rank $\omega$, but we will call it $<_\omega$ later.

There is an easy bijection (hilbert hotel) between $\mathbb N$ and $\mathbb N \cup \{\infty\}$ and the well founded relation $n <_\infty m$ iff $n < m$ or $m=\infty$ and $n \not = \infty$ has rank $\omega + 1$.

To define a well order with rank $2 \omega$ we can split $\mathbb N$ into two copies, even and odd - then define an order relation that odd numbers are always smaller than even numbers to get. Similarly we define well founded relations of rank $n \omega$.

Using Cantor pairing, the lexicographic order on $\mathbb N^2$ has rank $\omega^2$, similarly we get well founded relations $<_{\omega^n}$ of rank $\omega^n$.

To define an order of rank $\omega^\omega$ I did this

$$(n,a) <_{\omega^\omega} (m,b) :\!\!\!\iff \begin{cases} n <_\omega m \\ n = m \land a <_{\omega^n} b \end{cases}$$

I think it's correct because you can embed ordinals of size $\omega^n$ into it for any $n$.


How can I produce an explicit well ordering with rank $\omega^{(\omega^\omega)}$? (and other finite towers)

I thought we need to build a well ordering that can hold $\omega$, $\omega^2$, $\omega^3$, ..., $\omega^{\omega}$, $\omega^{2 \omega}$, $\omega^{3 \omega}$, ... $\omega^{\omega^2}$, $\omega^{\omega^3}$, $\omega^{\omega^4}$, ... so I should build $\omega^{\omega^2}$ first but I don't know how to do that either.

share|cite|improve this question
There is an error in the second paragraph: $2 \cdot \omega = \text{"}\omega\text{ copies of }2\text{"} = \omega \neq \omega \cdot 2$. – arjafi Mar 1 '13 at 12:05
I write multiplication backwards. is that ok? – user58512 Mar 1 '13 at 12:06
If you explicitly mention that you write products backwards it will be less of a problem. But all-in-all it is better to follow the notational standard. – arjafi Mar 1 '13 at 12:09
The answer to the last question is "all ordinals less than the Chrurch-Kleene ordinal $\omega_1^\text{CK}$" and this would still be true if you replaced "decidable" with "hyperarithmetical." – Trevor Wilson Mar 1 '13 at 18:02
Thank you kindly – user58512 Mar 3 '13 at 21:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.