Constructible universe

(Redirected from Constructible hierarchy)

In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , 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".[1] In this paper, he proved that the constructible universe is an inner model of ZF set theory (that is, of Zermelo–Fraenkel set theory with the axiom of choice excluded), 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 L is

edit

  can be thought of as being built in "stages" resembling the construction of 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 the Def operator:[2]

 

  is defined by transfinite recursion as follows:

  •  
  •  
  • If   is a limit ordinal, then   Here   means   precedes  .
  •   Here Ord denotes the class of all ordinals.

If   is an element of  , then  .[3] 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 (of  ) is constructible, i.e. in  .

Additional facts about the sets Lα

edit

An equivalent definition for   is:

For any ordinal  ,  .

For any finite ordinal  , the sets   and   are the same (whether   equals   or not), 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   =   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,   is the set of subsets of   defined by   formulas (with respect to the Levy hierarchy, i.e., formulas of set theory containing only bounded quantifiers) that use as parameters only   and its elements.[4]

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   (because the arithmetic definition gives one in  ). Conversely, any subset of   belonging to   is arithmetical (because elements of   can be coded by natural numbers in such a way that   is definable, i.e., arithmetic). On the other hand,   already contains certain non-arithmetical subsets of  , such as the set of (natural numbers coding) true arithmetical statements (this can be defined from   so it is in  ).

All hyperarithmetical subsets of   and relations on   belong to   (where   stands for the Church–Kleene ordinal), and conversely any subset of   that belongs to   is hyperarithmetical.[5]

L is a standard inner model of ZFC

edit

  is a standard model, i.e.   is a transitive class and the interpretation 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  . However   might be strictly a subclass of  .   is a model of ZFC, which means that it satisfies the following axioms:

  • Axiom of regularity: Every non-empty set   contains some element   such that   and   are disjoint sets.
  is a substructure of  , which is well founded, so   is well founded. In particular, if  , then by the transitivity of  ,  . If we use this same   as in  , then it is still disjoint from   because we are using the same element relation and no new sets were added.
If   and   are in   and they have the same elements in  , then by  's transitivity, they have the same elements (in  ). So they are equal (in   and thus in  ).
 , which is in  . So  . Since the element relation is the same and no new elements were added, this is the empty set of  .
  • Axiom of pairing: If  ,   are sets, then   is a set.
If   and  , then there is some ordinal   such that   and  . Then  . Thus   and it has the same meaning for   as for  .
  • Axiom of union: For any set   there is a set   whose elements are precisely the elements of the elements of  .
If  , then its elements are in   and their elements are also in  . So   is a subset of  . Then  . Thus  .
  • Axiom of infinity: There exists a set   such that   is in   and whenever   is in  , so is the union  .
Transfinite induction can be used to show each ordinal   is in  . In particular,   and thus  .
  • Axiom of separation: Given any set   and any proposition  ,   is a set.
By induction on subformulas of  , one can show that there is an   such that   contains   and   and (  is true in   if and only if   is true in  ), the latter is called the "reflection principle"). So   =  . Thus the subset is in  .[6]
  • Axiom of replacement: Given any set   and any mapping (formally defined as a proposition   where   and   implies  ),   is a set.
Let   be the formula that relativizes   to  , i.e. all quantifiers in   are restricted to  .   is a much more complex formula than  , but it is still a finite formula, and since   was a mapping over  ,   must be a mapping over  ; thus we can apply replacement in   to  . So   =   is a set in   and a subclass of  . Again using the axiom of replacement in  , we can show that there must be an   such that this set is a subset of  . Then one can use the axiom of separation in   to finish showing that it is an element of  
  • Axiom of power set: For any set   there exists a set  , such that the elements of   are precisely the subsets of  .
In general, some subsets of a set in   will not be in   So the whole power set of a set in   will usually not be in  . What we need here is to show that the intersection of the power set with   is in  . Use replacement in   to show that there is an α such that the intersection is a subset of  . Then the intersection is  . Thus the required set is in  .
  • Axiom of choice: Given a set   of mutually disjoint nonempty sets, there is a set   (a choice set for  ) containing exactly one element from each member of  .
One can show that there is a definable well-ordering of L, in particular based on ordering all sets in   by their definitions and by the rank they appear at. So one chooses the least element of each member of   to form   using the axioms of union and separation in  

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  .

L is absolute and minimal

edit

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   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 (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 that 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 "  constructed within  " and "  constructed within  " result in 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

edit

Since  , properties of ordinals that depend on the absence of a function or other structure (i.e.   formulas) 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# (see the list of large cardinal properties) will be retained in  .

However,   is false in   even if true in  . So all the large cardinals whose existence implies   cease to have those large cardinal properties, but retain the properties weaker than   which they also possess. For example, measurable cardinals cease to be measurable but remain Mahlo in  .

If   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   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  .[citation needed] This gives   a nice structure of repeating segments.

L can be well-ordered

edit

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   uses formulas with parameters from   to define the sets   and  . 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 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 (  and  ) or (  and   and  ), 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 (by Gödel numbers) of well-orderings. And   is well-ordered by the ordered sum (indexed by  ) 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   (some other standard model of ZF with the same ordinals) 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   (as we have done here with  ) 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.

L has a reflection principle

edit

Proving that the axiom of separation, axiom of replacement, and axiom of choice hold in   requires (at least as shown above) 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 (counting a constant symbol for an element of   as one symbol) we get that   holds in   if and only if it holds in  .

The generalized continuum hypothesis holds in L

edit

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 K, 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 (at most) 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

edit

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 [there exists   such that   and   and  ] 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

edit

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 by   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:

  •   = the smallest transitive set containing   as an element, i.e. the transitive closure of  .
  •   =  
  • If   is a limit ordinal, then  .
  •  .

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 (presumably non-constructible) set or a proper class. The definition of this class uses  , which is the same as   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   replaced by  .

  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.

See also

edit

Notes

edit
  1. ^ Gödel 1938.
  2. ^ K. J. Devlin, "An introduction to the fine structure of the constructible hierarchy" (1974). Accessed 20 February 2023.
  3. ^ K. J. Devlin, Constructibility (1984), ch. 2, "The Constructible Universe, p.58. Perspectives in Mathematical Logic, Springer-Verlag.
  4. ^ K. Devlin 1975, An Introduction to the Fine Structure of the Constructible Hierarchy (p.2). Accessed 2021-05-12.
  5. ^ Barwise 1975, page 60 (comment following proof of theorem 5.9)
  6. ^ P. Odifreddi, Classical Recursion Theory, pp.427. Studies in Logic and the Foundations of Mathematics

References

edit
  • Barwise, Jon (1975). Admissible Sets and Structures. Berlin: Springer-Verlag. ISBN 0-387-07451-1.
  • Devlin, Keith J. (1984). Constructibility. Berlin: Springer-Verlag. ISBN 0-387-13258-9.
  • Felgner, Ulrich (1971). Models of ZF-Set Theory. Lecture Notes in Mathematics. Springer-Verlag. ISBN 3-540-05591-6.
  • Gödel, Kurt (1938). "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 24 (12). National Academy of Sciences: 556–557. Bibcode:1938PNAS...24..556G. doi:10.1073/pnas.24.12.556. JSTOR 87239. PMC 1077160. PMID 16577857.
  • Gödel, Kurt (1940). The Consistency of the Continuum Hypothesis. Annals of Mathematics Studies. Vol. 3. Princeton, N. J.: Princeton University Press. ISBN 978-0-691-07927-1. MR 0002514.
  • Jech, Thomas (2002). Set Theory. Springer Monographs in Mathematics (3rd millennium ed.). Springer. ISBN 3-540-44085-2.