Constructible universe


In mathematics, in set theory, the constructible universe, denoted L, is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". 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.

What is

can be thought of as being built in "stages" resembling the von Neumann universe,. The stages are indexed by ordinals. In von Neumann's universe, at a successor stage, one takes to be the set of all subsets of the previous stage,. By contrast, in Gödel's constructible universe, 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
L is defined by transfinite recursion as follows:
If is an element of, then = ∈ Def =. So is a subset of, which is a subset of the power set of. Consequently, this is a tower of nested transitive sets. But itself is a proper class.
The elements of are called "constructible" sets; and itself is the "constructible universe". The "axiom of constructibility", aka " = ", says that every set is constructible, i.e. in.

Additional facts about the sets {{sub|}}

An equivalent definition for is:
For any finite ordinal, the sets and are the same, and thus = : their elements are exactly the hereditarily finite sets. Equality beyond this point does not hold. Even in models of ZFC in which equals, is a proper subset of, and thereafter is a proper subset of the power set of for all >. On the other hand, = does imply that equals if =, for example if is inaccessible. More generally, = implies Hereditarily countable set| = for all infinite cardinals.
If is an infinite ordinal then there is a bijection between and, and the bijection is constructible. So these sets are equinumerous in any model of set theory that includes them.
As defined above, Def is the set of subsets of defined by Δ formulas that use as parameters only and its elements.
Another definition, due to Gödel, characterizes each as the intersection of the power set of with the closure of under a collection of nine explicit functions, similar to Gödel operations. This definition makes no reference to definability.
All arithmetical subsets of and relations on belong to . Conversely, any subset of belonging to is arithmetical. On the other hand, already contains certain non-arithmetical subsets of, such as the set of true arithmetical statements.
All hyperarithmetical subsets of and relations on belong to , and conversely any subset of that belongs to is hyperarithmetical.

is a standard inner model of ZFC

is a standard model, i.e. it is a transitive class and it uses the real element relationship, so it is well-founded. is an inner model, i.e. it contains all the ordinal numbers of and it has no "extra" sets beyond those in, but it might be a proper subclass of. is a model of ZFC, which means that it satisfies the following axioms:
Notice that the proof that is a model of ZFC only requires that be a model of ZF, i.e. we do not assume that the axiom of choice holds in.

is absolute and minimal

If is any standard model of ZF sharing the same ordinals as, then the defined in is the same as the defined in. In particular, is the same in and, for any ordinal. And the same formulas and parameters in Def produce the same constructible sets in.
Furthermore, since is a subclass of and, similarly, is a subclass of, is the smallest class containing all the ordinals that is a standard model of ZF. Indeed, is the intersection of all such classes.
If there is a set in that is a standard model of ZF, and the ordinal is the set of ordinals that occur in, then is the of. If there is a set that is a standard model of ZF, then the smallest such set is such a. This set is called the minimal model of ZFC. Using the downward Löwenheim–Skolem theorem, one can show that the minimal model 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 that are models of ZF. 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 of and the of are the real and both the of and the of are the real, we get that = is true in and in any that is a model of ZF. However, = does not hold in any other standard model of ZF.

L and large cardinals

Since Ord ⊂ ⊆, properties of ordinals that depend on the absence of a function or other structure are preserved when going down from to. Hence initial ordinals of cardinals remain initial in. Regular ordinals remain regular in. Weak limit cardinals become strong limit cardinals in because the generalized continuum hypothesis holds in. Weakly inaccessible cardinals become strongly inaccessible. Weakly Mahlo cardinals become strongly Mahlo. And more generally, any large cardinal property weaker than 0 will be retained in.
However, 0 is false in even if true in. So all the large cardinals whose existence implies 0 cease to have those large cardinal properties, but retain the properties weaker than 0 which they also possess. For example, measurable cardinals cease to be measurable but remain Mahlo in.
If 0 holds in, then there is a closed unbounded class of ordinals that are indiscernible in. While some of these are not even initial ordinals in, they have all the large cardinal properties weaker than 0 in. Furthermore, any strictly increasing class function from the class of indiscernibles to itself can be extended in a unique way to an elementary embedding of into. This gives a nice structure of repeating segments.

can be well-ordered

There are various ways of well-ordering. Some of these involve the "fine structure" of, 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 could be well-ordered using only the definition given above.
Suppose and are two different sets in and we wish to determine whether < or >. If first appears in and first appears in and is different from, then let < if and only if <. Henceforth, we suppose that =.
The stage = Def uses formulas with parameters from to define the sets and. If one discounts 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 that can be used to define, and is the formula with the smallest Gödel number that can be used to define, and is different from, then let < if and only if < in the Gödel numbering. Henceforth, we suppose that =.
Suppose that uses parameters from. Suppose,..., is the sequence of parameters that can be used with to define, and,..., does the same for. Then let < if and only if either < or or etc. This is called the reverse lexicographic ordering; if there are multiple sequences of parameters that define one of the sets, we choose the least one under this ordering. It being understood that each parameter's possible values are ordered according to the restriction of the ordering of to, 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 -tuples of parameters are well-ordered by the product ordering. The formulas with parameters are well-ordered by the ordered sum of well-orderings. And is well-ordered by the ordered sum of the orderings on.
Notice that this well-ordering can be defined within itself by a formula of set theory with no parameters, only the free-variables and. And this formula gives the same truth value regardless of whether it is evaluated in,, or and we will suppose that the formula is false if either or is not in.
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 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.

has a reflection principle

Proving that the axiom of separation, axiom of replacement, and axiom of choice hold in requires the use of a reflection principle for. Here we describe such a principle.
By induction on <, we can use ZF in to prove that for any ordinal, there is an ordinal > such that for any sentence with,..., in and containing fewer than symbols we get that holds in if and only if it holds in.

The generalized continuum hypothesis holds in

Let, and let be any constructible subset of. Then there is some with, so for some formula and some drawn from. By the downward Löwenheim–Skolem theorem and Mostowski collapse, there must be some transitive set containing and some, and having the same first-order theory as with the substituted for the ; and this will have the same cardinal as. Since is true in, it is also true in, so for some having the same cardinal as. And because and have the same theory. So is in fact in.
So all the constructible subsets of an infinite set have ranks with the same cardinal as the rank of ; it follows that if is the initial ordinal for, then serves as the "power set" of within. Thus this "power set". And this in turn means that the "power set" of has cardinal at most ||||. Assuming itself has cardinal, the "power set" must then have cardinal exactly. But this is precisely the generalized continuum hypothesis relativized to.

Constructible sets are definable from the ordinals

There is a formula of set theory that expresses the idea that =. It has only free variables for and. Using this we can expand the definition of each constructible set. If ∈, then = for some formula and some,..., in. This is equivalent to saying that: for all, ∈ if and only if where is the result of restricting each quantifier in to. Notice that each ∈ for some <. Combine formulas for the 's with the formula for and apply existential quantifiers over the 's outside and one gets a formula that defines the constructible set using only the ordinals that appear in expressions like = as parameters.
Example: The set is constructible. It is the unique set that 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 that is true only for the desired constructible set and that contains parameters only for ordinals.

Relative constructibility

Sometimes it is desirable to find a model of set theory that is narrow like, but that includes or is influenced by a set that is not constructible. This gives rise to the concept of relative constructibility, of which there are two flavors, denoted and .
The class for a non-constructible set is the intersection of all classes that are standard models of set theory and contain and all the ordinals.
is defined by transfinite recursion as follows:
If contains a well-ordering of the transitive closure of, then this can be extended to a well-ordering of. Otherwise, the axiom of choice will fail in.
A common example is, the smallest model that contains all the real numbers, which is used extensively in modern descriptive set theory.
The class is the class of sets whose construction is influenced by, where may be a set or a proper class. The definition of this class uses Def, which is the same as Def except instead of evaluating the truth of formulas in the model, one uses the model where is a unary predicate. The intended interpretation of is ∈. Then the definition of is exactly that of only with Def replaced by Def.
is always a model of the axiom of choice. Even if is a set, is not necessarily itself a member of , although it always is if is a set of ordinals.
The sets in or are usually not actually constructible, and the properties of these models may be quite different from the properties of itself.