Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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!

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer
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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.