Finding a well-ordering of the natural numbers of a given order type

Question

Let $X$ be the set of all well-orderings of the set of natural numbers, and let $O$ be the set of countable ordinals, i.e. the set of ordinals that are order types of the well-orderings in $X$. Then my question is, is it possible to use transfinite recursion to define a function $f:O\rightarrow X$ where for each ordinal $\alpha\in O$, $f(\alpha)$ is a well-ordering of the set of natural numbers with order type $\alpha$?

The base case is easy enough; we can let $f(\omega)$ be the standard order on $\mathbb{N}$. And the successor case is easy; if we know what $f(\alpha)$ is, then to define $f(\alpha+1)$ we can apply (an analogue of) $f(\alpha)$ to $\mathbb{N}-0$ and then append 0 to the end of it.

But how do we do the limit case, i.e. if $\lambda$ is a limit ordinal in $O$ and we know the values of $f(\alpha)$ for all $\alpha<\lambda$, how can we define $f(\lambda)$?

Answer 1

Yes, but not really.

For a limit ordinal $\alpha$, you can choose a cofinal increasing sequence $\alpha_n$ going to $\alpha$ with $\alpha_0=0$, then partition $\Bbb N$ into infinitely many infinite sets, $A_n$, then order $A_n$ with the well-ordering given by $f(\alpha_{n+1}\setminus\alpha_n)$ (composing it with the natural enumeration that is), and thus create a well-order of type $\alpha$. Of course, if $\alpha_{n+1}\setminus\alpha_n$ is a finite ordinal, require that $A_n$ is of the right size instead of infinite.

But to do so for all the countable ordinals, you need to choose for all limit ordinals these cofinal sequences. Of course, this is doable with the axiom of choice. But if you're appealing to the axiom of choice, it's easier to just consider the function $\operatorname{otp}\colon X\to O$, mapping each well-order to its order type, noting it is surjective, and just choosing an inverse map.

Without the axiom of choice, which is perhaps what you'd like to do, and have this done more... constructively, it is consistent that no such injection exists. Or that there are no injections at all from the set of countable ordinals into the set of well-orderings of $\Bbb N$.

---

To sum up, you can do this, but not constructively. And since you're already applying the axiom of choice, might as well leave the recursive construction behind and just use choice directly.

Answer 2

I think you're having some confusion with Asaf's answer, so let me rephrase it a bit. The goal is to break our $\lambda$ into a bunch of blocks, and "paste together" fixed copies of each block to build a copy of $\lambda$ itself.

Walking up an ordinal

Suppose I have a countable limit ordinal $\lambda$. There is (exercise) a sequence $(\alpha_n)_{n\in\mathbb{N}}$ such that:

• $\alpha_1<\alpha_2<\alpha_3<...$, and

• $\lambda=\sup\{\alpha_n: n\in\mathbb{N}\}$.

We call such a sequence a fundamental sequence of $\lambda$. Note that every element of a fundamental sequence of $\lambda$ is $<\lambda$.

Importantly, fundamental sequences are not unique, and indeed the fact that we have lots of choices is going to be where nonconstructivity/the axiom of choice creep in.

Clarification: choice is not needed to show that every countable ordinal has a fundamental sequence. However, it is required to get a map assigning each countable ordinal a fundamental sequence. Similarly, we need choice to prove that the $f$ you want exists, even though ZF proves that for each countable $\alpha$ there is a map assigning each ordinal $<\alpha$ to a relation on the naturals of that ordertype. As an extreme example of a way the $f$ you want can fail to exist in ZF, note that there are models of ZF in which $\omega_1$ is a countable union of countable sets; in such a model, the existence of an $f$ as you describe would imply the countability of $\omega_1$.

Examples

• $\lambda=\omega+\omega$: the sequence $$\alpha_1=\omega, \alpha_2=\omega+1,\alpha_3=\omega+2,...,\alpha_{n+1}=\omega+n,...$$ is a fundamental sequence for $\lambda$. But so is the sequence $$\beta_1=5,\beta_2=13,\beta_3=\omega+4,\beta_4=\omega+6,\beta_5=\omega+8,...,\beta_{n+2}=\omega+2n,...$$

• $\lambda=\omega^2$: the sequence $$\alpha_1=\omega,\alpha_2=\omega\cdot 2,\alpha_3=\omega\cdot 3,...,\alpha_n=\omega\cdot n,...$$ is the "most obvious" fundamental sequence for $\lambda$. However, there are lots of other possibilities, like $$\beta_1=\omega\cdot 2,\beta_2=\omega\cdot 4,\beta_3=\omega\cdot6,...,\beta_n=\omega\cdot 2n, ...$$

Breaking an ordinal into blocks

Now we come to the key step. Suppose $\lambda$ is a limit ordinal and $(\alpha_i)_{i\in\mathbb{N}}$ is a fundamental sequence for $\lambda$. Then we can break $\lambda$ into "blocks" given by the fundamental sequence:

Given a countable limit ordinal $\lambda$ and a fundamental sequence $(\alpha_i)_{i\in\mathbb{N}}$ for $\lambda$, there is a unique sequence $(A_i)_{i\in\mathbb{N}}$ of ordinals such that $$\sum_{1\le i\le n}A_i=\alpha_n.$$ More importantly, we have $$\sum_{i\in\mathbb{N}}A_i=A_1+A_2+A_3+...=\sup\{\alpha_i: i\in\mathbb{N}\}=\lambda.$$

The proof is a good exercise. Intuitively, for the existence part (which is the only part we actually need here) we want "$A_{i+1}=\alpha_{i+1}-\alpha_i$," although obviously we have to be careful what we mean by that ...

For example, if we let $\lambda=\omega$ and $\alpha_i=2i$, then we have $A_i=2$ for each $i$: counting up to $\omega$ by even numbers cuts $\omega$ into a sequence of blocks each of length $2$.

Making the induction work

We can now prove the result you want:

Suppose I have a countable limit ordinal $\lambda$, and for each $\eta<\lambda$ I have a well-ordering $W_\lambda$ of (a subset of) $\mathbb{N}$ of ordertype $\eta$. (This is, after all, the only step of the induction you're missing.)

It's slightly easier to work with well-orderings of sets of natural numbers, as opposed to well-orderings of all of $\mathbb{N}$ - e.g. it means that finite blocks aren't a problem - but it's a purely cosmetic choice.

Fix a fundamental sequence $(\alpha_i)_{i\in\mathbb{N}}$ of $\lambda$, and let $(A_i)_{i\in\mathbb{N}}$ be the corresponding "sequence of blocks" as per the fact above. By the induction hypothesis - note that $A_i<\lambda$ for all $i$, since $A_i\le\alpha_i<\lambda$ - I get a sequence of well-orderings of (subsets of) $\mathbb{N}$ corresponding to the $A_i$s, namely $(W_i)_{i\in\mathbb{N}}$. Intuitively, I now want to add the $W_i$s together. I can do that as follows:

• Let $W$ be the following well-ordering:

  • The underlying set $dom(W)$ of $W$ is $$\{\langle i, x\rangle: x\in dom(W_i)\}.$$ (Here "$\langle\cdot\cdot\rangle$" is your favorite pairing function $\mathbb{N}^2\cong\mathbb{N}$.)

  • The ordering relation on $W$ is given by $$\langle i,x\rangle\le \langle j,y\rangle\iff (i<j)\vee (i=j\wedge x\le_{W_i}y).$$

It's now easy to show that the ordertype of $W$ is $$A_1+A_2+A_3+...=\sup\{\alpha_n:n\in\mathbb{N}\}=\lambda.$$