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

Solution 1:

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!

Solution 2:

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.