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?


The order is very easy. Under $V=L$, the set-theoretic universe is built according the hierarchy $(L_\alpha \mid \alpha \in \mathrm{Ord})$, 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 hierarchy 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.


Your Answer

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

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