# 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 ... – Andrés E. Caicedo 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 ... – Andrés E. Caicedo 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$. – Andrés E. Caicedo Jun 14 '16 at 2:00
• @AndrésCaicedo thanks :) is there a reason you didn't post this as an answer? – benzrf 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? – benzrf 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{ZFC}$) well-orders all of $L$, so that its restriction to any specific set $A$ 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{ZFC}$, 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<i$.

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.