# Well-ordering of the reals in ZF with constructibility?

The question Do we know that we can't define a well-ordering of the reals? states:

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$).

What is an example of such a $\varphi$?

• Work in $L$. "$x<y$ iff $x,y$ are reals, and $x$ appears before $y$ in the standard construction of $L$." In the standard construction, $L$ is produced by stages $L_0\subsetneq L_1\subsetneq\dots$. There is a formula in one parameter $\alpha$ that defines $L_\alpha$. That $x$ appears before $y$ means that if we define $\alpha_x$ as the unique $\alpha$ such that $x\in L_{\alpha+1}\setminus L_\alpha$, then either $\alpha_x<\alpha_y$, or they are equal but $x$ appears before $y$ in the standard construction of $L_{\alpha+1}$ from $L_\alpha$. In order to define this construction, we need ... Jun 14 '16 at 1:54
• ... to fix a (recursive) enumeration of the formulas in the language of set theory. $L_{\alpha+1}$ is defined as the collection of subsets of $L_\alpha$ that are definable over $L_\alpha$ using parameters from $L_\alpha$. This definability involves the formulas you have enumerated. So, if $\alpha_x=\alpha_y=\alpha$, we say that $x$ appears before $y$ if the first formula (in your fixed enumeration) that defines $x$ over $L_\alpha$ precedes the first formula defining $y$, or else this first formula is the first for both, but ... Jun 14 '16 at 1:58
• ... the parameters used to define $x$ precede those that are used to define $y$. This is a recursive definition, since this preceding is with respect to the lexicographic ordering of finite sequences defined with respect to the well-ordering we are describing restricted to $L_\alpha$. Jun 14 '16 at 2:00
• @AndrésCaicedo thanks :) is there a reason you didn't post this as an answer? Jun 14 '16 at 2:14
• @AndrésE.Caicedo Wait - two things. First: how can we fix a unique choice of defining formula for each set in a formula without parameters? Second: what if two reals are defined by the same formula, but with different parameters from each other? Jun 24 '16 at 23:42

$$L$$ has such a nice canonical structure that one can use it to define a global well-ordering. That is, there is a formula $$\phi(u,v)$$ that (provably in $$\mathsf{ZF}$$) well-orders all of $$L$$, so that its restriction to any specific set $$A$$ in $$L$$ is a set well-ordering of $$A$$.

The well-ordering $$\varphi$$ you are asking about can be obtained as the restriction to $$\mathbb R^L$$ of this global well-ordering $$\phi$$.

In detail, recall that $$L=\bigcup_{\alpha\in\mathrm{ORD}}L_\alpha,$$ where $$L_0=\emptyset$$, $$L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha$$ for $$\lambda$$ a limit ordinal, and $$L_{\alpha+1}=\{A\subseteq L_\alpha : A\mbox{ is definable (with parameters) in }(L_\alpha,\in)\}.$$ Some presentations of $$L$$ define $$L_{\alpha+1}$$ quite explicitly as I indicate. This requires some work, since one needs to formalize internally the relevant notions of definability and satisfiability in set structures in order to make sense of the statement that "$$A$$ is definable (with parameters) in $$(L_\alpha,\in)$$'' as a formula in the language of set theory (as opposed to an informal statement about model theory in natural language). An example of a book providing the relevant details of this approach is

MR0750828 (85k:03001). Devlin, Keith J. Constructibility. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1984. xi+425 pp. ISBN: 3-540-13258-9.

Other presentations instead describe the collection $$L_{\alpha+1}$$ of definable subsets of $$(L_\alpha,\in)$$ in terms of certain natural operations without explicitly referring to definability in terms of first-order formulas. This approach is also favored nowadays in some presentations of model theory, as it highlights the naturalness of first-order definability to those already familiar with, say, the theory of real algebraic sets. (For instance, if $$A$$ is a definable set of pairs, the set $$\{x:\exists y\,(x,y)\in A\}$$ should also be definable. Rather than talking about the existential quantifier, one can simply discuss the projection of $$A$$ to its first coordinate.) An example of a book discussing $$L$$ along these lines is

MR0597342 (82f:03001). Kunen, Kenneth. Set theory. An introduction to independence proofs. Studies in Logic and the Foundations of Mathematics, 102. North-Holland Publishing Co., Amsterdam-New York, 1980. xvi+313 pp. ISBN: 0-444-85401-0.

Whichever approach you follow, by the recursion theorem this gives you that there is a formula $$\psi$$ in one parameter $$a$$ that, whenever $$a$$ is an ordinal $$\alpha$$, defines $$L_\alpha$$. That is, $$\psi(a,x)$$ has the property that (provably in $$\mathsf{ZF}$$, although it suffices for what we are doing here that this is true under the assumption of $$V=L$$) for any ordinal $$\alpha$$, the set $$L_\alpha$$ is the unique set $$b$$ such that $$\psi(\alpha,b)$$ holds.

In the sketch below, I follow the first approach. I'm leaving some details out, but the first reference above should complement what I say here. Begin by coding in set theory a recursive enumeration of the set of first-order formulas in the language $$\{\in\}$$, say $$\phi_0,\phi_1,\dots$$ If $$x\in L$$, write $$\operatorname{rk}_L(x)$$ for the least ordinal $$\alpha$$ such that $$x\in L_{\alpha+1}$$. Now, if $$\alpha=\operatorname{rk}_L(x)$$, this means that there is a formula $$\phi_n(u_1,\dots,u_m,v)$$ in the language of set theory such that $$x=\{y\in L_\alpha:(L_\alpha,\in)\models\phi_n(a_1,\dots,a_m,y)\}$$ for some parameters $$a_1,\dots,a_m\in L_\alpha$$. (That there is such a formula $$\phi_n$$ and such parameters is precisely what is meant by "$$x$$ is definable (with parameters) in $$(L_\alpha,\in)$$''.) Write $$\min_L(x)$$ for the least $$n$$ such that $$x$$ can be defined as above using $$\phi_n$$ from some parameters.

Now, to define the global well-ordering of $$L$$, assume $$V=L$$. I proceed to define by recursion a well-ordering $$<_\alpha$$ of $$L_\alpha$$ with the property that if $$\alpha<\beta$$ (as ordinals) then $$<_\alpha\subset <_\beta$$. In fact, $$<_\beta$$ is an end-extension of $$<_\alpha$$, meaning that if $$x\in L_\alpha$$ and $$y\in L_\beta\smallsetminus L_\alpha$$, then $$x<_\beta y$$.

The definition is as follows: $$<_0=\emptyset$$. For limit ordinals $$\lambda$$, $$<_\lambda$$ is just $$\bigcup_{\alpha<\lambda}<_\alpha$$. Now, assuming we have defined $$<_\alpha$$, we define $$<_{\alpha+1}$$ as follows: Note that $$<_\alpha$$ induces an ordering $$<_{\alpha,f}$$ of finite tuples of members of $$L_\alpha$$: given $$a_1,\dots,a_m,b_1,\dots,b_k\in L_\alpha$$, set $$(a_1,\dots,a_m)<_{\alpha,f}(b_1,\dots,b_k)$$ if and only if either

• $$k>m$$ or else
• $$k=m$$ and there is an $$i$$, $$1\le i\le m$$, such that $$a_i<_\alpha b_i$$ but $$a_j=b_j$$ for all $$j.

Note that this is a well-ordering of the set of finite tuples.

Finally, given $$x,y\in L_{\alpha+1}$$ set $$x<_{\alpha+1}y$$ if and only if either

• $$\operatorname{rk}_L(x)<\operatorname{rk}_L(y)$$, or else
• $$\operatorname{rk}_L(x)=\operatorname{rk}_L(y)<\alpha$$ and $$x<_\alpha y$$, or else
• $$\operatorname{rk}_L(x)=\operatorname{rk}_L(y)=\alpha$$ and $$\min_L(x)<\min_L(y)$$, or else
• $$\operatorname{rk}_L(x)=\operatorname{rk}_L(y)=\alpha$$ and $$\min_L(x)=\min_L(y)=n$$, say, and the least tuple $$(a_1,\dots,a_m)$$ of parameters in $$L_\alpha$$ from which $$\phi_n$$ defines $$x$$ in $$(L_\alpha,\in)$$ is $$<_{\alpha,f}$$-below the least such tuple $$(b_1,\dots,b_k)$$ from which $$\phi_n$$ defines $$y$$.

One readily verifies that each $$<_\alpha$$ is indeed a well-ordering of $$L_\alpha$$ and the end-extension property holds. Finally, you can define a well-ordering $$<_L$$ of $$L$$ by setting $$x<_L y$$ (for $$x,y\in L$$) if and only if for some $$\alpha$$, $$x<_\alpha y$$ (equivalently, for all sufficiently large $$\alpha$$, $$x<_\alpha y$$).

(In short, all we are saying is that $$x<_L y$$ if and only if "$$x$$ appears before $$y$$" in the standard iterative construction of $$L$$.)

At the end of the day, the same idea can be applied to much more general inner models than just $$L$$. This is in broad strokes how one defines global well-orderings of the canonical $$L[\vec E]$$ models of inner model theory, for instance.

The definition is canonical enough that, when restricted to the reals, produces a well-ordering of the reals of the inner model of low (in fact, optimal) complexity in the sense of the projective hierarchy. Verifying this requires a further layer of coding, where one checks that for countable $$\alpha$$ the structures $$L_\alpha$$ (or their appropriate versions when looking at the $$L[\vec E]$$) can be "reasonably" coded as real numbers. For the $$L[\vec E]$$ models, one needs further verify that one can code in such a reasonable fashion the comparison process that allows us to conclude that one structure precedes another. This last detail is not needed in the case of $$L$$, where $$L_\alpha$$ precedes $$L_\beta$$ if and only if $$L_\alpha\subset L_\beta$$, but the right notion is not simply containment in general.