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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... [...]I dont believe in natural science. ... This article or section does not cite any references or sources. ... In mathematical logic, suppose T is a theory in the language . If M is a model of describing a set theory and N is a class of M such that is a model of T then we say that N is an inner model of T (in M). ... Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ... An axiom is a sentence or proposition that is not proved or demonstrated and is considered as obvious or as an initial necessary consensus for a theory building or acceptation. ...

What is L?

L can be thought of as being built in "stages" resembling von Neumann's 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: A separate article covers Saint John Neumann, the American priest. ... In axiomatic set theory and related branches of mathematics, the Von Neumann universe, or Von Neumann hierarchy of sets is the class of all sets, divided into a transfinite hierarchy of individual sets. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... When defining the ordinal numbers, an absolutely fundamental operation that we can perform on them is a successor operation S to get the next higher one. ...

• definable by a formula in the formal language of set theory
• with parameters from the previous stage and
• with the quantifiers interpreted to range over the previous stage.

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. In mathematics and in the sciences, a formula (plural: formulae, formulæ or formulas) is a concise way of expressing information symbolically (as in a mathematical or chemical formula), or a general relationship between quantities. ... In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... A parameter is a measurement or value on which something else depends. ... In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. ...

Define Def (X) = { {y|yεX and Φ(y,z₁,...,z_n) is true in (X,ε)} | Φ is a first order formula and z₁,...,z_n are elements of X}.

L is defined by transfinite recursion as follows: Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. ...

• L₀ = {}.
• L_α+1 = Def (L_α)
• If λ is a limit ordinal, then .
• .

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. In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In set theory, a set (or class) A is transitive, if whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently, whenever x ∈ A, and x is not an urelement, then x is a subset of A. The transitive closure of a set A is the smallest (with respect...

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. The axiom of constructibility is a possible axiom for set theory in mathematics. ...

Additional facts about the sets L_α

An equivalent definition for L_α is:

For any ordinal α, .

For any finite ordinal n, the sets L_n and V_n are the same (whether V equals L or not), and thus L_ω = V_ω. 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 α > ω. Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ...

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. Two sets A and B are said to be equinumerous if they have the same cardinality, i. ...

As defined above, Def(X) is the set of subsets of X defined by Δ₀ formulas (that is, formulas of set theory which contain only bounded quantifiers) which use as parameters only X and its elements. In the study of formal theories in mathematical logic, bounded quantifiers are often added to a language. ...

An alternate definition, due to Gödel himself, 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. In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ...

All hyperarithmetical subsets of ω and relations on ω belong to .

L is a standard inner model of ZFC

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: In set theory, a set (or class) A is transitive, if whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently, whenever x ∈ A, and x is not an urelement, then x is a subset of A. The transitive closure of a set A is the smallest (with respect... Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... An axiom is a sentence or proposition that is not proved or demonstrated and is considered as obvious or as an initial necessary consensus for a theory building or acceptation. ...

• Axiom of regularity: Every non-empty set x contains some element y such that x and y are disjoint sets.

(L,ε) is a substructure of (V,ε) which is well founded, so L is well founded. In particular, if xεL, then by the transitivity of L, yεL. If we use this same y as in V, then it is still disjoint from x because we are using the same element relation and no new sets were added.

• Axiom of extensionality: Two sets are the same if and only if they have the same elements.

If x and y are in L and they have the same elements in L, then by L's transitivity, they have the same elements (in V). So they are equal (in V and thus in L).

• Axiom of empty set: {} is a set.

{} = L₀ = {y|yεL₀ and y=y} ε L₁. So {} ε L. Since the element relation is the same and no new elements were added, this is the empty set of L.

• Axiom of pairing: If x, y are sets, then {x,y} is a set.

If xεL and yεL, then there is some ordinal α such that xεL_α and yεL_α. Then {x,y} = {s|sεL_α and (s=x or s=y)} ε L_α+1. Thus {x,y} ε L and it has the same meaning for L as for V.

• Axiom of union: For any set x there is a set y whose elements are precisely the elements of the elements of x.

If x ε L_α, then its elements are in L_α and their elements are also in L_α. So y is a subset of L_α. y = {s|sεL_α and there exists zεx such that sεz} ε L_α+1. Thus y ε L.

• Axiom of infinity: There exists a set x such that {} is in x and whenever y is in x, so is the union y U {y}.

From transfinite induction, we get that each ordinal α ε L_α+1. In particular, ω ε L_ω+1 and thus ω ε L.

• Axiom of separation: Given any set S and any proposition P(x,z₁,...,z_n), {x|xεS and P(x,z₁,...,z_n)} is a set.

By induction on subformulas of P, one can show that there is an α such that L_α contains S and z₁,...,z_n and (P is true in L_α if and only if P is true in L (this is called the "Reflection Principle")). So {x|xεS and P(x,z₁,...,z_n) holds in L} = {x|xεL_α and xεS and P(x,z₁,...,z_n) holds in L_α} ε L_α+1. Thus the subset is in L.

• Axiom of replacement: Given any set S and any mapping (formally defined as a proposition P(x,y) where P(x,y) and P(x,z) implies y = z), {y | there exists xεS such that P(x,y)} is a set.

Let Q(x,y) be the formula which relativizes P to L, i.e. all quantifiers in P are restricted to L. Q is a much more complex formula than P, but it is still a finite formula; and we can apply replacement in V to Q. So {y|yεL and there exists xεS such that P(x,y) holds in L} = {y | there exists xεS such that Q(x,y)} is a set in V and a subclass of L. Again using the axiom of replacement in V, we can show that there must be an α such that this set is a subset of L_α ε L_α+1. Then one can use the axiom of separation in L to finish showing that it is an element of L.

• Axiom of power set: For any set x there exists a set y, such that the elements of y are precisely the subsets of x.

In general, some subsets of a set in L will not be in L. So the whole power set of a set in L will usually not be in L. What we need here is to show that the intersection of the power set with L *IS* in L. Use replacement in V to show that there is an α such that the intersection is a subset of L_α. Then the intersection is {z|zεL_α and z is a subset of x} ε L_α+1. Thus the required set is in L.

• Axiom of choice: Given a set x of mutually disjoint nonempty sets, there is a set y (a choice set for x) containing exactly one element from each member of x.

One can show that there is a definable well-ordering of L which definition works the same way in L itself. So one chooses the least element of each member of x to form y using the axioms of union and separation in L.

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. The axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of empty set is one of the axioms of Zermelo_Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of union is one of the axioms of Zermelo_Fraenkel set theory, stating that, for any two sets, there is a set that contains exactly the elements of both. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory. ... In mathematics, the axiom of power set is one of the Zermelo-Fraenkel axioms of axiomatic set theory. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...

L is absolute and minimal

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. In mathematical logic, the classic Löwenheim–Skolem theorem states that for any countable first-order language L with signature and L-structure M, there exists a countably infinite elementary substructure N M. A natural and useful corollary of this theorem is that every consistent L-theory has a countable...

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.

L can be well-ordered

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 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 same for y. Then let x<y if and only if either z_n<w_n or (z_n=w_n and z_n-1<w_n-1) or (z_n=w_n and z_n-1=w_n-1 and z_n-2<w_n-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 what is called "global choice" and is more powerful than the axiom of choice because it applies to proper classes of non-empty sets.

L has a reflection principle

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. In set theory, a branch of mathematics, a reflection principle says that we can find sets that resemble the class of all sets. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...

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(z₁,...,z_k) with z₁,...,z_k in L_β and containing fewer than n symbols (counting a constant symbol for an element of L_β as one symbol) we get that P(z₁,...,z_k) holds in L_β if and only if it holds in L.

Constructible sets are definable from the ordinals

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,z₁,...,z_n) holds in (L_α,ε)} for some formula Φ and some z₁,...,z_n 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,z₁,...,z_n)] where Ψ(X,...) is the result of restricting each quantifier in Φ(...) to X. Notice that each z_kε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 Ord(a) 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.

The difference between constructible and constructive

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. In set theory, a code for a set x the notation standing for the hereditarily countable sets, is a set E ω×ω such that there is an isomorphism between (ω,E) and (X,) where X is the transitive closure of {x}. If X is finite (with cardinality n), then use n×n... In mathematics, especially in set theory, ordinals may be used to label the elements of any given well-ordered set (the smallest element being labeled 0, the one after that 1, the next one 2, and so on) and to measure the length of the whole set by the least... In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...

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. In set theory, an admissible ordinal is any ordinal number α such that Lα is a standard set model of Kripke–Platek set theory. ... The Kripke–Platek axioms of set theory (KP) are a system of axioms of axiomatic set theory, developed by Saul Kripke and Richard Platek. ...

Relative constructibility

Sometimes people want to make a model of set theory which is narrow like L, but they want it to include or to be influenced by a set which is not constructible. This gives rise to the concept of relative constructibility, of which there are two flavors: 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: Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. ...

• L₀(A) = the smallest transitive set containing A as an element, i.e. the transitive closure of {A}.
• L_α+1(A) = Def (L_α(A))
• If λ is a limit ordinal, then .
• .

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). In set theory, a set (or class) A is transitive, if whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently, whenever x ∈ A, and x is not an urelement, then x is a subset of A. The transitive closure of a set A is the smallest (with respect...

A common example is L(R), the smallest model which contains all the real numbers, which is used extensively in modern descriptive set theory. In mathematics, descriptive set theory is the study of certain classes of well-behaved sets of real numbers, e. ...

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 Def_A (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 Def_A.

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.

See also

• Axiom of constructibility
• Statements true in L
• Reflection principle
• Axiomatic set theory
• Axiom of choice
• Transitive set
• L(R)

The axiom of constructibility is a possible axiom for set theory in mathematics. ... The axiom of constructibility is a powerful statement that resolves many propositions in set theory and some interesting questions in analysis. ... In set theory, a branch of mathematics, a reflection principle says that we can find sets that resemble the class of all sets. ... This article or section is in need of attention from an expert on the subject. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... In set theory, a set (or class) A is transitive, if whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently, whenever x ∈ A, and x is not an urelement, then x is a subset of A. The transitive closure of a set A is the smallest (with respect... In set theory, L(R) (pronounced L of R) is the smallest transitive inner model of ZF containing all the ordinals and all the reals. ...

References

• Devlin, Keith J. (1984). Constructibility. Berlin: Springer-Verlag. ISBN 0387132589. 
• Ulrich Felgner,Models of ZF-Set Theory,1971,Lecture Notes in Mathematics,Springer-Verlag. ISBN 3540055916
• Thomas Jech,Set Theory,3rd millennium Ed.,2002,Springer Monographs in Mathematics,Springer. ISBN 3540440852