# Explicit well-ordering of $\mathbb{N}^{\mathbb{N}}$

Is there an explicit well-ordering of $\mathbb{N}^{\mathbb{N}}:=\{g:\mathbb{N}\rightarrow \mathbb{N}\}$?

I've been thinking about that for awhile but nothing is coming to my mind. My best idea is this:

Denote by $<$ the usual "less than" relation on $\mathbb{N}$. Since $\mathbb{N}^{\mathbb{N}}$ is the set of infinite sequences ${\{x_{n}\}}_{n\in \mathbb{N}}$ with $x_{n}\in \mathbb{N}$, we can define ${\{x_{n}\}}_{n\in \mathbb{N}}\leq ^{\prime }{\{y_{n}\}}_{n\in \mathbb{N}}$ as follows. If $x_{0}<y_{0}$, then ${\{x_{n}\}}_{n\in \mathbb{N}}\leq ^{\prime }{\{y_{n}\}}_{n\in \mathbb{N}}$. If $x_{k-1}=y_{k-1}$, for $k\in \mathbb{N}\setminus \{0\}$, then ${\{x_{n}\}}_{n\in \mathbb{N}}\leq ^{\prime }{\{y_{n}\}}_{n\in \mathbb{N}}$ if and only if $x_{k}<y_{k}$.

I think that under this relation not every subset of $\mathbb{N}^{\mathbb{N}}$ has a least element.

Any ideas?

-
It is not true that you can prove in ZFC that there is no explicit well-ordering of the reals, since if ZFC is consistent, then it is consistent with ZFC that there is a well-ordering of complexity $\Delta^1_2$, which is just a step up from Borel in the descriptive set theoretic hierarchy. – JDH Feb 27 '11 at 1:14
The distinction is that you can't prove there is no explicit well-order and you also can't prove there is one. In some set-theoretic universes, there is an explicit order and in others there isn't. – JDH Feb 27 '11 at 1:58
I think the confusion may be cleared up as follows: Given any formula $\phi(x,y)$ in two variables ranging over ${\mathbb N}^{\mathbb N}$ that provably describes a linear ordering of ${\mathbb N}^{\mathbb N}$, there are models of set theory where the formula does not describe a well-ordering. So, in this explicit sense, we cannot explicitly describe a well-ordering (and this negative result can be strengthened in a variety of ways). Of course, as Joel mentioned, there are also "simple", explicit formulas and models of set theory where these formulas describe well-orderings. – Andrés E. Caicedo Feb 27 '11 at 2:16
In fact, there are formulas $\varphi(x,y)$ such that given any model of set theory, there is a larger model of set theory (a forcing extension) where the formula describes a well-ordering of the reals. But all these formulas are necessarily somewhat complex (in a technical sense). – Andrés E. Caicedo Feb 27 '11 at 2:19
Anyway, an easy infinite descending family in your ordering is given by the sequences $(0,\dots,0,1,\dots)$ that have an initial finite sequence of zeroes and then are 1 from then on. – Andrés E. Caicedo Feb 27 '11 at 2:25

If you had a well-ordering of $\mathbb N^{\mathbb N}$ it wouldn't be too hard to construct a well-ordering of $\mathbb R$ from that. However, it is believed that there is no explicit well-ordering of $\mathbb R$, so I'm afraid there won't be one for $\mathbb N^{\mathbb N}$ either. JDH is the expert on this!

-
You are essentially correct. The first of my comments above indicates how your idea can be made rigorous. The actual construction of the models where a given formula is not giving us a well-ordering uses the technique of forcing (A precise example is given by using the poset that adds $\omega_1$ Cohen reals. In the resulting extension, there are no definable well-orderings). – Andrés E. Caicedo Feb 27 '11 at 2:23

Since $\mathbb N^\mathbb N$ has the cardinality of $\mathbb R$ (in fact in some set theoretical frameworks this is the definition of $\mathbb R$) a well ordering of $\mathbb N^\mathbb N$ is the same as well ordering the real numbers (via transfer of structure).

Now comes the point where the "explicit" becomes ambiguous. If you want a well ordering of $\mathbb R$ which is defined in ZF without the axiom of choice then this is plainly impossible for several possible reasons:

1. There exists a subset of the real numbers which cannot be well-ordered (Cohen's first model); if we can well-order the real numbers then we can well-order every subset of the real numbers. If we have constructed a model in which there is a subset of the real numbers which cannot be well-ordered then the real numbers cannot be well ordered.

2. There is no uncountable subset of the real numbers which can be well-ordered; for example in the Solovay model where all the sets of real numbers are Lebesgue measurable or in the Feferman-Levy model where the continuum is a countable union of countable sets(!).

In both the models there are no subsets of the real numbers which have cardinality $\aleph_1$. That is only countable subsets of the real numbers can be well-ordered.

3. We do not treat the real numbers directly in a construction, but the resulting model can be shown to have properties inconsistent with well-ordering of the real numbers (every set is measurable; no Hamel basis for $\mathbb R$ over $\mathbb Q$; etc.) so we may have not attempted to destroy any well-ordering of the real numbers, but it happened anyway.

In the other extreme, if you assume something like $V=L$ (so in particular you get the axiom of choice, free of charge!) then there is a well-ordering of the real numbers which has a relatively low complexity $\Delta^1_2$ as JDH commented. This is not too far from being a Borel set, and Borel sets are relatively constructible in a good sense that we have this recipe to create them.

Do note that for a well-ordering to be $\Delta^1_2$ means that there is a certain formula $\varphi(x,y)$ and the relation $\{\langle x,y\rangle\mid \varphi(x,y)\}$ is a well-ordering of $\mathbb R$. The formula will always define a relation, and as Andres commented this relation will not always be a well-ordering of the real numbers. This would depend on your universe.

-

What is the least element of $\mathbb{N}^{\mathbb{N}} \setminus (0,0,0,\dots)$? I don't think one is defined.

-
Or note that the sequence $e_n$ with $(e_n)_i = 1$ for $i=n$ and $0$ otherwise is an infinite decreasing sequence, so it's not a well-order. – Henno Brandsma Feb 27 '11 at 8:17
Henno: Good point. I thought to add this afterward. In a sense, they are saying the same thing in two different ways. It is similar to asking what is the least x>0. – Ross Millikan Feb 27 '11 at 14:56

This answers the second thing you said: Why $\mathbb{N}^\mathbb{N}$ is not well ordered under the relation you mention (I am aware this doesn't answer your actual question):

Take the set $$S=\{ \overline {x}: \text{There exists } n\in\mathbb{N} \text{ with } x_n\neq 0, \text{and } x_i=0\ \text{ for } 0\leq i< n\}$$

For it to have a least element it would need to contain $\overline{0}$, which it doesn't.

Hope that helps,

Edit: I deleted my strange explanation of why arrive at this conclusion

-