Folklore has it that it is impossible to define a well-ordering of the reals explicitly.

There exist pointwise definable models of ZFC where every set is definable without parameters: it is the unique element of the model that satisfies some finite formula $\varphi(x)$. So there is a formula $\varphi(x)$ such that $$ \tag{*} \forall x(\varphi(x)\rightarrow x\text{ well-orders }\mathbb R) \land \exists ! x\,\varphi(x) $$ is consistent with ZFC. (And it is not difficult to write down a concrete $\varphi$ which will work in a model with $\mathbf V=\mathbf L$).

Is it known that there is no $\varphi(x)$ such that $\text{(*)}$ is a theorem of ZFC?

Of course, since there are models of ZF that don't have a well-order of $\mathbb R$, in such a model $\varphi(x)$ would either be unsatisfiable or be satisfied by something that doesn't well-order $\mathbb R$. So the Axiom of Choice would have to be used in some essential way in the proof of $\text{(*)}$. But that doesn't in itself seem to preclude the possibility that $\varphi$ might exist.

  • I think that I answered this before. Hang on. – Asaf Karagila Jun 7 '15 at 12:54
  • Okay, not quite this question, but related to the answer that I will now type into the answer box. This one. – Asaf Karagila Jun 7 '15 at 12:57
  • 1
    Also for an extra easy relative consistency, recall that if there is a definable well-ordering, then it is ordinal definable; now combine this with (1) no well-ordering of $\Bbb R$ is measurable; (2) In the full Solovay model (only collapsing an inaccessible; without passing to an inner model) every set of reals definable from an ordinal and a real parameter is measurable. – Asaf Karagila Jun 7 '15 at 14:13
  • It might be more difficult, but one could in fact "write down a concrete $\phi$ which $\hspace{1.55 in}$ will work in a model with" $\: \mathbb{R} \subset$ $\mathbf{OD}$$\;$. $\;\;\;\;$ – user57159 Jun 7 '15 at 22:53
up vote 16 down vote accepted

The answer is that we can't write a formula which provably defines a well-ordering of $\Bbb R$ in $\sf ZFC$ (at least assuming that $\sf ZFC$ is consistent), although I don't know whose to credit for it.

Suppose that $\varphi(x,y)$ provably defines a bijection of $\Bbb R$ with an ordinal (this is equivalent to the way you state it, just making it easier to work with later on). Note that $\sf ZF$ proves that every well-ordering has a unique isomorphism with a unique ordinal, so it doesn't depend on anything.

Let $M$ be a countable transitive model [of enough axioms] of $\sf ZFC$. Consider the forcing which adds one Cohen real. The conditions of this forcing are finite functions $p\colon\omega\to2$ (here we mean partial functions, of course), ordered by reverse inclusion.

Denote by $\dot c=\{(p,\check k)\mid p(k)=1\}$ the canonical name for the Cohen real. Let $G$ be an $M$-generic filter, and let $c$ denote the interpretation of our Cohen real by $G$.

In $M[G]$ there is some $\alpha$ such that $M[G]\models\varphi(c,\alpha)$, therefore for some $p\in G$ we have that $p\Vdash\varphi(\dot c,\check\alpha)$.

Now pick any $m,n\notin\operatorname{dom}(p)$ and consider the permutation of $\omega$ which is the cycle $(m\ n)$. This permutation is in $M$, and we can apply it to the conditions of the forcing (by the action $\pi p(\pi n)=p(n)$). So we can think of it as an automorphism of the forcing. Some basic facts:

  1. An automorphism of the forcing extends uniquely to an automorphism of the names.
  2. $p\Vdash\phi(\dot x)$ if and only if $\pi p\Vdash\phi(\pi\dot x)$ for an automorphism $\pi$.
  3. In the Cohen forcing, if $\pi$ is an automorphism induced as above by a permutation of $\omega$, and it is not the identity automorphism, then $1\Vdash\pi\dot c\neq\dot c$.
  4. If $x\in M$, then $\pi\check x=\check x$, where $\check x$ is the canonical name for $x$.

We now have that $\pi p\Vdash\varphi(\pi\dot c,\pi\check\alpha)$. But $\pi p=p$, and therefore $p\Vdash\varphi(\pi\dot c,\check\alpha)$. Which is a contradiction since now $p\Vdash\varphi\text{ defines an injective function}\land\pi\dot c\neq\dot c\land\varphi(\dot c,\check\alpha)\land\varphi(\pi\dot c,\check\alpha)$.

  • I don't know how familiar you are with forcing and automorphisms thereof. Let me know if you need me to fill any gaps in the answer. – Asaf Karagila Jun 7 '15 at 13:53
  • 1
    Enough to follow the gist of the argument (though not enough to certify independently that it works), +1. – Henning Makholm Jun 7 '15 at 14:30
  • Andres gave an excellent answer which should explain the mechanics of how this works. – Asaf Karagila Jun 7 '15 at 14:31
  • 1
    Actually, I think this one makes more sense to me. I'm not quite familiar enough to fill in the blanks at the broader conceptual level he's writing at, but the details here match things I remember reading about. – Henning Makholm Jun 7 '15 at 14:47
  • 1
    "one Cohen reals, namely" $\: \mapsto \:$ "one Cohen real, namely" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ – user57159 Jun 7 '15 at 22:55

Forcing with sufficiently homogeneous forcing that adds reals is enough to obtain the negation of $(*)$. The point is that if a formula $\phi$ defines a parameter-free well-ordering of $\mathbb R$, then for any ordinal $\alpha$, the statement "$x$ is the $\alpha$-th real in the well-ordering defined by $\phi$" uniquely characterizes $x$ in terms of $\alpha$. If the forcing we used is homogeneous, this implies that $x$ is in the ground model, as you can then proceed to uniquely characterize $x$ (for instance, you can verify whether "its first digit is $0$", "its second digit is $1$", etc). The way that homogeneity is used is in noticing that all these statements I am writing have the form $\psi(\check t_1,\dots,\check t_n)$ when written in the forcing language (for some $\psi$ in the language of set theory, and some $t_1,\dots,t_n$ in the ground model). But any such statement is either always or never forced (by homogeneity), and so, from the ground model, you can read off every real in the extension, so the forcing cannot add reals.

So you are done once you find a homogeneous forcing that adds reals. Cohen forcing is an example. One can go further and obtain models where there are no well-orderings definable using parameters from the ground model by a simple extension of the sketch above, and even models where there are no well-orderings definable, even if (ordinal definable, or small-sized) parameters from the extension are allowed (though now we need to add more than just one Cohen real to achieve this).

Since many natural forcing posets are sufficiently homogeneous to carry out the arguments just described, one of the surprising realizations that has come out of the study of forcing axioms is that they tend to imply the existence of definable well-orderings (either from a parameter, or even parameter-free if we force from a definable inner model). I have a few papers explaining this phenomenon, or see this talk. Some questions remain; for instance, it is still open whether if Martin's Axiom holds and $\omega_1=\omega_1^L$, then there is a projective well-ordering of the reals. In the early 2000s, I would have thought asking this was ridiculous. But we do not know.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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