Constructible Universe - L Can Be Well-ordered

L Can Be Well-ordered

There are various ways of well-ordering L. Some of these involve the "fine structure" of L which was first described by Ronald Bjorn Jensen in his 1972 paper entitled "The fine structure of the constructible hierarchy". Instead of explaining the fine structure, we will give an outline of how L could be well-ordered using only the definition given above.

Suppose x and y are two different sets in L and we wish to determine whether xy. If x first appears in L_α+1 and y first appears in L_β+1 and β is different from α, then let x

Remember that L_α+1 = Def (L_α) which uses formulas with parameters from L_α to define the sets x and y. If one discounts (for the moment) the parameters, the formulas can be given a standard Gödel numbering by the natural numbers. If Φ is the formula with the smallest Gödel number which can be used to define x, and Ψ is the formula with the smallest Gödel number which can be used to define y, and Ψ is different from Φ, then let x

Suppose that Φ uses n parameters from L_α. Suppose z₁,...,z_n is the sequence of parameters least in the reverse-lexicographic ordering which can be used with Φ to define x, and w₁,...,w_n does the same for y. Then let xnn or (z_n=w_n and z_n-1n-1) or (z_n=w_n and z_n-1=w_n-1 and z_n-2n-2) or etc.. It being understood that each parameter's possible values are ordered according to the restriction of the ordering of L to L_α, so this definition involves transfinite recursion on α.

The well-ordering of the values of single parameters is provided by the inductive hypothesis of the transfinite induction. The values of n-tuples of parameters are well-ordered by the product ordering. The formulas with parameters are well-ordered by the ordered sum (by Gödel numbers) of well-orderings. And L is well-ordered by the ordered sum (indexed by α) of the orderings on L_α+1.

Notice that this well-ordering can be defined within L itself by a formula of set theory with no parameters, only the free-variables x and y. And this formula gives the same truth value regardless of whether it is evaluated in L, V, or W (some other standard model of ZF with the same ordinals) and we will suppose that the formula is false if either x or y is not in L.

It is well known that the axiom of choice is equivalent to the ability to well-order every set. Being able to well-order the proper class V (as we have done here with L) is equivalent to the axiom of global choice which is more powerful than the ordinary axiom of choice because it also covers proper classes of non-empty sets.