MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 19 down vote accepted

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.

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.

If one analyzes the complexity of the resulting definition for real numbers, it has complexity Delta^1_2 in the descriptive set theoretic hierarchy.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.