From http://en.wikipedia.org/wiki/Analytical_hierarchy

"If the axiom of constructibility holds then there is a subset of the product of the Baire space with itself which is $\Delta^1_2$ and is the graph of a well ordering of the Baire space. If the axiom holds then there is also a $\Delta^1_2$ well ordering of Cantor space."

Can someone (give here or point me to) a (sketch or thorough description) of a $\Delta^1_2$ set that does this for (Baire space or Cantor space)?

I can see how V=L implies there is a definable well order, but I can't see how it would be in the analytical hierarchy.

  • 5
    $\begingroup$ You might want to give this question a more descriptive title. $\endgroup$ – Mike Shulman May 4 '10 at 2:01

In the constructible universe $L$, there is a definable well-ordering of the entire universe. This universe is built up in transfinite stages $L_\alpha$, and the ordering has $x\lt_L y$ when $x$ is constructed at an earlier stage, or else they are constructed at the same stage, but $x$ is constructed at that stage by an earlier definition, or with the same definition, but with earlier parameters. I also explain this in this MO answer.

One may extract from this definition a rather low-complexity definable well-ordering of the reals by capturing the countable pieces of the $L$ hieararchy by reals. That is, if $x$ is a real number of $L$, then it appears at some countable stage $L_\alpha$ for a countable ordinal $\alpha$, and the entire structure $L_\alpha$ is countable, and hence itself coded by a real. Here, we code a set by a real in any of the standard ways, for example, by coding a well-founded extensional relation on $\omega$ whose Mostowski collapse is the given set. Furthermore, the $L$-order is absolute to any $L_\alpha$, since $L_\alpha$ knows about the $L_\beta$-heirarchy for $\beta<\alpha$. Also, if a countable structure is well-founded and thinks $V=L$, then it is $L_\alpha$ for some $\alpha$. Note that if a real $z$ codes a first order structure $M$, then the question of whether $M$ satisfies a first order assertion is an arithmetic statement in $z$, since we need only quantify over the coded elements, which are coded by natural numbers.

Putting all this together, we get that the following are equivalent for any two reals $x$ and $y$:

  • $x\lt_L y$ in the $L$ order.
  • There is some countable ordinal $\alpha$ such that $L_\alpha$ satisfies $x\lt_L y$.
  • For every countable ordinal $\alpha$, if $x$ and $y$ are reals in $L_\alpha$, then $L_\alpha$ satisfies $x\lt_L y$.
  • There is a real $z$ coding a well-founded structure that thinks $V=L$ (and so this structure must be some $L_\alpha$) in which $x$ and $y$ are reals and the structure satisfies $x\lt_L y$.
  • All reals $z$ coding well-founded structures $L_\alpha$ in which $x$ and $y$ are reals satisfy $x\lt_L y$.

The fourth statement has complexity $\Sigma^1_2$, since being-well-founded is $\Pi^1_1$. Similarly the fifth statement has complexity $\Pi^1_2$, so overall the ordering is $\Delta^1_2$.

The end result is that in the universe $L$, there is a low-complexity definable well-ordering of the reals. In this universe, therefore, all of the supposedly non-constructive applications of AC turn out to be completely definable.

  • $\begingroup$ The differences between Baire space or Cantor space or $P(\omega)$ does not matter in the argument, which works equally well for any of them. $\endgroup$ – Joel David Hamkins May 4 '10 at 2:45
  • 1
    $\begingroup$ "if $x$ is a real number of $L$, then it appears at some countable stage $L_\alpha$ for a countable ordinal $\alpha$" So thaaat's how it works. (Could I find a proof that $\alpha$ must be countable somewhere?) As far as verifying that the structure thinks V=L, how would you define "the nth formula with the mth tuple of parameters constructs set x in the $\beta$th level" arithmetically? Or would you not actually need to do that? $\endgroup$ – user5810 May 4 '10 at 3:17
  • 1
    $\begingroup$ The fact that reals are added at a countable stage is part of Goedel's proof that CH holds in L. (Since $L_{\omega_1}$ is the union of all $L_\alpha$ for couintable $\alpha$, it has size $\omega_1$ and contains all reals. This part of the proof uses the Condensation principle. $\endgroup$ – Joel David Hamkins May 4 '10 at 4:02
  • 1
    $\begingroup$ For your question about satisfaction, you don't need to translate it separately into an arithmetic statement---the general phenomenon is that when a real codes a countable structure, then quantifying over that structure amounts to quantifying over the natural numbers, via the code. So satisfaction of any expressible formula is arithemtic in the code. Just imagine that you have a real coding a structure, and imagine how you could say using this code that this structure satisfied a first order statements. $\endgroup$ – Joel David Hamkins May 4 '10 at 4:04
  • $\begingroup$ "So satisfaction of any expressible formula is arithemtic in the code." The problem is that that does not hold uniformly. What I think would be needed is something like an arithmetical formula that takes (n,m,real) and returns whether the resulting formula is true. (exactly that can't actually exists) $\endgroup$ – user5810 May 4 '10 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy