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

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)$?

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.

• Let me add that in proof theory there is interest in exploring systems of ordinal notations, which essentially provide us with explicit ways of carrying out the recursive procedure Asaf suggests for a long while. This amounts to explicit ways of picking these cofinal sequences for the limit ordinals in the initial segment of the ordinals that the ordinal notation manages to describe. For instance, there is a very natural way of picking up such sequences for any limit ordinal up to $\epsilon_0$, but typical systems reach much farther. – Andrés E. Caicedo Aug 15 '18 at 13:43
• @Keshav If you are trying to build a well-ordering of type $\alpha$, and $\alpha$ is limit, and you know how to build well-orderings of all shorter order types, you pick a subset of $\alpha$ of type $\omega$ and cofinal in $\alpha$ (this is possible since $\alpha$ is countable), and use its elements $\alpha_n$ to guide the construction of the well-ordering you are after. – Andrés E. Caicedo Aug 15 '18 at 13:45
• @Keshav: Yes. Every increasing sequence with supremum $\alpha$ is cofinal in $\alpha$. You're right, and my suggestion works for limits of limits, not for "successor limits". But those are easy to handle. – Asaf Karagila Aug 15 '18 at 13:56
• @Keshav The idea is this: You split $\omega$ into countably many infinite sets $A_n$. Then you consider the order where $A_n$ is ordered in type $\alpha_n$ and any member of $A_m$ is strictly below any member of $A_k$ for $m<k$. This gives a well-ordering of $\omega$ of order type $\alpha_0+\alpha_1+\dots$, which is at least $\alpha$, but may very well be longer. If it is longer, an initial segment of it has type $\alpha$ and there is an infinite subset of $\omega$ that has type $\alpha$ under this ordering you built, so you also easily get an ordering of $\omega$ of type $\alpha$. – Andrés E. Caicedo Aug 15 '18 at 13:59
• @Keshav Let me add that ordinals like $\omega+\omega$ are not the ones you need to focus on. If $\alpha=\beta+\gamma$ with $\beta,\gamma<\alpha$, and you know how to build orderings of types $\beta,\gamma$, then you know how to build an ordering of type $\alpha$, there is no problem here. The issue is when you reach indecomposable ordinals, those of the form $\omega^\alpha$. – Andrés E. Caicedo Aug 15 '18 at 14:27

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.$$

• Working in ZF, if the function $f$ of the Q is assumed to exist, does it imply there exists $S\subset \Bbb R$ with $|S|=\omega_1$? – DanielWainfleet Aug 27 '18 at 3:58
• @DanielWainfleet Sorry, I just noticed this! Yes, yes it does: from $f$ we get a subset of the set of binary relations on $\mathbb{N}$ which has size $\omega_1$, and the set of binary relations on $\mathbb{N}$ is uncomplicatedly bijective with $\mathbb{R}$. In particular, this means that the "tamer" $\mathbb{R}$ is, the "messier" any such $f$ must be - e.g. $\mathsf{ZF+AD}$ disproves the existence of any such $f$, and $\mathsf{ZFC+PD}$ disproves the existence of any projective such $f$. – Noah Schweber Feb 19 at 17:00