Set Theory and V=L - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T22:38:14Z http://mathoverflow.net/feeds/question/23393 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23393/set-theory-and-vl Set Theory and V=L Ricky Demer 2010-05-04T01:15:14Z 2010-05-04T03:13:01Z <p>From <a href="http://en.wikipedia.org/wiki/Analytical_hierarchy" rel="nofollow">http://en.wikipedia.org/wiki/Analytical_hierarchy</a></p> <p>"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."</p> <p>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)?</p> <p>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.</p> http://mathoverflow.net/questions/23393/set-theory-and-vl/23399#23399 Answer by Joel David Hamkins for Set Theory and V=L Joel David Hamkins 2010-05-04T02:17:25Z 2010-05-04T03:13:01Z <p>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 <a href="http://mathoverflow.net/questions/6593/vl-and-a-well-ordering-of-the-reals/6600#6600" rel="nofollow">this MO answer</a>.</p> <p>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&lt;\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. </p> <p>Putting all this together, we get that the following are equivalent for any two reals $x$ and $y$:</p> <ul> <li>$x\lt_L y$ in the $L$ order. </li> <li>There is some countable ordinal $\alpha$ such that $L_\alpha$ satisfies $x\lt_L y$.</li> <li>For every countable ordinal $\alpha$, if $x$ and $y$ are reals in $L_\alpha$, then $L_\alpha$ satisfies $x\lt_L y$. </li> <li>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$. </li> <li>All reals $z$ coding well-founded structures $L_\alpha$ in which $x$ and $y$ are reals satisfy $x\lt_L y$. </li> </ul> <p>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$. </p> <p>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. </p>