11
$\begingroup$

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}


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

Any ideas?

  • 1
    See this MO question http://mathoverflow.net/questions/6593/vl-and-a-well-ordering-of-the-reals for an account of how it is at least consistent with ZFC that there is an explicit well-ordering of the reals (and hence also of $\mathbb{N}^\mathbb{N}$).2011-02-27
  • 0
    @JDH: I have heard that it impossible to construct an explicit well-ordering of the reals. Is that statement true in any sense?2011-02-27
  • 4
    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.2011-02-27
  • 0
    Jim, but your statement is true in the sense that there can be no definition in the language of set theory that in ZFC provably defines a well-ordering of the reals.2011-02-27
  • 0
    @JDH: I have to admit, I'm having a hard time wrapping my mind around the distinction.2011-02-27
  • 5
    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.2011-02-27
  • 4
    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.2011-02-27
  • 4
    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).2011-02-27
  • 2
    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.2011-02-27
  • 0
    @JDH @Andres: thanks for helping to clarify my confusion.2011-02-27
  • 0
    Thank you all! I see that my problem has to do with the very foundations of mathematics. All the discussion here is awesome and very informative. I appreciate all your comments.2011-02-27

4 Answers 4

5

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!

  • 0
    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).2011-02-27
3

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.

0

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

0

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

  • 1
    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.2011-02-27
  • 0
    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.2011-02-27