most recent 30 from http://mathoverflow.net 2013-05-24T13:44:14Z http://mathoverflow.net/feeds/question/6593 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6593/vl-and-a-well-ordering-of-the-reals Jimmy Miller 2009-11-23T17:37:29Z 2009-11-23T18:10:14Z

<p>A fairly simple question: I've read in multiple sources that Godel proved that if we accept the axiom of constructibility in ZFC, then we can create an explicit formula that well-orders the real numbers. I tried searching for a paper or some other source that explains what this formula is, but I came up empty-handed. Can someone explain what this formula is, or perhaps point me to a resource that does?</p>

http://mathoverflow.net/questions/6593/vl-and-a-well-ordering-of-the-reals/6600#6600 Joel David Hamkins 2009-11-23T18:10:14Z 2009-11-23T18:10:14Z

<p>The order is very easy. Under V=L, the set-theoretic universe is built according the hierarhcy L_alpha, where L_0 is empty, L_{alpha+1} consists of all definable subsets of L_alpha, and L_lambda is the union of all earlier L_alpha when lambda is a limit ordinal. </p> <p>Since we can order the definitions used to go from L_alpha to L_{alpha+1}, we obtain a definable well-ordering of the entire universe. Namely, x is less than y iff (1) x appears before y in the hiearchy or (2) they appear at the same stage, but x appears with an earlier definition than y. </p> <p>If one analyzes the complexity of the resulting definition for real numbers, it has complexity Delta^1_2 in the descriptive set theoretic hierarchy. </p>