In mathematics, the constructible universe (or Gödel's constructible universe), denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1940 paper Consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory. In this, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.
L can be thought of as being built in "stages" resembling the von Neumann universe, V. The stages are indexed by ordinals. In von Neumann's universe, at a successor stage, one takes Vα+1 to be the set of ALL subsets of the previous stage, Vα. By contrast, in Gödel's constructible universe L, one uses ONLY those subsets of the previous stage that are:
By limiting oneself to sets defined only in terms of what has already been constructed, one ensures that the resulting sets will be constructed in a way that is independent of the peculiarities of the surrounding model of set theory and contained in any such model.
Define Def (X) = { {y | yεX and Φ(y,z1,...,zn) is true in (X,ε)} | Φ is a first order formula and z1,...,zn are elements of X}.
L is defined by transfinite recursion as follows:
If z is an element of Lα, then z = {y|yεLα and yεz} ε Def (Lα) = Lα+1. So Lα is a subset of Lα+1 which is a subset of the power set of Lα. Consequently, this is a tower of nested transitive sets. But L itself is a proper class.
The elements of L are called "constructible" sets; and L itself is the "constructible universe". The "axiom of constructibility", aka "V=L", says that every set (of V) is constructible, i.e. in L.
An equivalent definition for Lα is:
For any finite ordinal n, the sets Ln and Vn are the same (whether V equals L or not), and thus Lω = Vω: their elements are exactly the hereditarily finite sets. Equality beyond this point does not hold. Even in models of ZFC in which V equals L, Lω+1 is a proper subset of Vω+1, and thereafter Lα+1 is a proper subset of the powerset of Lα for all α > ω.
If α is an infinite ordinal then there is a bijection between Lα and α, and the bijection is constructible. So these sets are equinumerous in any model of set theory which includes them.
As defined above, Def(X) is the set of subsets of X defined by Δ0 formulas (that is, formulas of set theory which contain only bounded quantifiers) which use as parameters only X and its elements.
An alternate definition, due to Gödel, characterizes each Lα+1 as the intersection of the powerset of Lα with the closure of Lα under a collection of nine explicit functions. This definition makes no reference to definability.
All arithmetical subsets of ω and relations on ω belong to Lω+1 (because the arithmetic definition gives one in Lω+1). Conversely, any subset of ω belonging to Lω+1 is arithmetical (because elements of Lω can be coded by natural numbers in such a way that ∈ is definable, i.e., arithmetic). On the other hand, Lω+2 already contains certain non-arithmetical subsets of ω, such as the set of (natural numbers coding) true arithmetical statements (this can be defined from Lω+1 so it is in Lω+2).
All hyperarithmetical subsets of ω and relations on ω belong to (where
stands for the Church-Kleene ordinal), and conversely any subset of ω which belongs to
is hyperarithmetical.[1]
L is a standard model, i.e. it is a transitive class and it uses the real element relationship, so it is well-founded. L is an inner model, i.e. it contains all the ordinal numbers of V and it has no "extra" sets beyond those in V, but it might be a proper subclass of V. L is a model of ZFC, which means that it satisfies the following axioms:
Notice that the proof that L is a model of ZFC only requires that V be a model of ZF, i.e. we do NOT assume that the axiom of choice holds in V.
If W is any standard model of ZF sharing the same ordinals as V, then the L defined in W is the same as the L defined in V. In particular, Lα is the same in W and V, for any ordinal α. And the same formulas and parameters in Def (Lα) produce the same constructible sets in Lα+1.
Furthermore, since L is a subclass of V and, similarly, L is a subclass of W, L is the smallest class containing all the ordinals which is a standard model of ZF. Indeed, L is the intersection of all such classes.
If there is a set W in V which is a standard model of ZF, and the ordinal κ is the set of ordinals which occur in W, then Lκ is the L of W. If there is a set which is a standard model of ZF, then the smallest such set is such a Lκ. This set is called the minimal model of ZFC. Using the downward Löwenheim–Skolem theorem, one can show that the minimal model (if it exists) is a countable set.
Of course, any consistent theory must have a model, so even within the minimal model of set theory there are sets which are models of ZF (assuming ZF is consistent). However, those set models are non-standard. In particular, they do not use the normal element relation and they are not well founded.
Because both the L of L and the V of L are the real L and both the L of Lκ and the V of Lκ are the real Lκ, we get that V=L is true in L and in any Lκ which is a model of ZF. However, V=L does not hold in any other standard model of ZF.
There are various different 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 x<y or x>y. If x first appears in Lα+1 and y first appears in Lβ+1 and β is different from α, then let x<y if and only if α<β. Henceforth, we suppose that β=α.
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<y if and only if Φ<Ψ in the Gödel numbering. Henceforth, we suppose that Ψ=Φ.
Suppose that Φ uses n parameters from Lα. Suppose z1,...,zn is the sequence of parameters least in the reverse-lexicographic ordering which can be used with Φ to define x and w1,...,wn does same for y. Then let x<y if and only if either zn<wn or (zn=wn and zn-1<wn-1) or (zn=wn and zn-1=wn-1 and zn-2<wn-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.
Proving that the axiom of separation, axiom of replacement, and axiom of choice hold in L requires (at least as shown above) the use of a reflection principle for L. Here we describe such a principle.
By mathematical induction on n<ω, we can use ZF in V to prove that for any ordinal α, there is an ordinal β>α such that for any sentence P(z1,...,zk) with z1,...,zk in Lβ and containing fewer than n symbols (counting a constant symbol for an element of Lβ as one symbol) we get that P(z1,...,zk) holds in Lβ if and only if it holds in L.
There is a formula of set theory which expresses the idea that X=Lα. It has only free variables for X and α. Using this we can expand the definition of each constructible set. If sεLα+1, then s = {y|yεLα and Φ(y,z1,...,zn) holds in (Lα,ε)} for some formula Φ and some z1,...,zn in Lα. This is equivalent to saying that: for all y, yεs if and only if [there exists X such that X=Lα and yεX and Ψ(X,y,z1,...,zn)] where Ψ(X,...) is the result of restricting each quantifier in Φ(...) to X. Notice that each zkεLβ+1 for some β<α. Combine formulas for the z's with the formula for s and apply existential quantifiers over the z's outside and one gets a formula which defines the constructible set s using only the ordinals α which appear in expressions like X=Lα as parameters.
Example: The set {5,ω} is constructible. It is the unique set, s, which satisfies the formula:
,
where is short for:
Actually, even this complex formula has been simplified from what the instructions given in the first paragraph would yield. But the point remains, there is a formula of set theory which is true only for the desired constructible set s and which contains parameters only for ordinals.
All constructive sets are constructible, where a set being constructive means that it has a code which is recursive. On the other hand, constructible sets are not necessarily constructive. When constructing constructible sets one is given free use of the ordinal numbers and also of the hierarchy Lα. This may not be constructive because there are ordinals which are not the order type of a recursive well-ordering of the natural numbers. And generating Def(X) from X is not a constructive operation, especially quantifying over X when it is infinite. Nor is taking the union of Lβ at non-constructive limit ordinals.
Every set in Lω is constructive, but some non-constructive sets appear as early as Lω+1. Every ordinal less than is constructive. Every constructive set belongs to the admissible set
, which is a standard set model of Kripke–Platek set theory plus the axiom of infinity.
Sometimes it is desirable to find a model of set theory which is narrow like L, but which includes or is influenced by a set which is not constructible. This gives rise to the concept of relative constructibility, of which there are two flavors, denoted L(A) and L[A].
The class L(A) for a non-constructible set A is the intersection of all classes which are standard models of set theory and contain A and all the ordinals.
L(A) is defined by transfinite recursion as follows:
If L(A) contains a well-ordering of the transitive closure of {A}, then this can be extended to a well-ordering of L(A). Otherwise, the axiom of choice will fail in L(A).
A common example is L(R), the smallest model which contains all the real numbers, which is used extensively in modern descriptive set theory.
The class L[A] is the class of sets whose construction is influenced by A, where A may be a (presumably non-constructible) set or a proper class. The definition of this class uses DefA (X), which is the same as Def (X) except instead of evaluating the truth of formulas Φ in the model (X,ε), one uses the model (X,ε,A) where A is a unary predicate. The intended interpretation of A(y) is yεA. Then the definition of L[A] is exactly that of L only with Def replaced by DefA.
L[A] is always a model of the axiom of choice. Even if A is a set, A is not necessarily itself a member of L[A], although it always is if A is a set of ordinals.
It is essential to remember that the sets in L(A) or L[A] are usually not actually constructible and that the properties of these models may be quite different from the properties of L itself.