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

Question

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?

Answer 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!

Answer 2

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

Answer 3

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

Answer 4

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.