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$?

  • 5
    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
  • 4
    ... 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
  • 4
    ... 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
  • 5
    @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
up vote 5 down vote accepted

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

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.