View source for Gödel constructive set

''Gödel constructible set, constructible set''

A set arising in the process of constructing sets described below. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445201.png" /> be a set and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445202.png" />. Consider the first-order language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445203.png" /> containing one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445204.png" />-place predicate symbol denoting the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445205.png" />, and individual constants, denoting the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445206.png" /> (for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445207.png" /> its constant is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445208.png" />). The statement  "the formula f of the language LR, X is valid in the model M=X, R"  is written:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g0445209.png" /></td> </tr></table>

A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452010.png" /> is called definable in the model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452011.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452012.png" />-definable) if there exists a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452013.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452014.png" /> with one free variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452015.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452016.png" /></td> </tr></table>

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452017.png" /> denote the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452018.png" />-definable sets. To each ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452019.png" /> is associated the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452020.png" /> defined recursively by the relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452021.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452022.png" /> is the membership relation restricted to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452023.png" />. Hence it follows that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452024.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452025.png" /></td> </tr></table>

A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452026.png" /> is called constructible if there exists an ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452027.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452028.png" />. The class of all constructible sets is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452029.png" />. In 1938, K. Gödel defined <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452030.png" /> and introduced the following axiom of constructibility: Every set is constructible. On the basis of the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452031.png" />, he proved that in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452032.png" /> all axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452033.png" /> hold and also the axiom of constructibility, and that the axiom of choice and the generalized continuum hypothesis ( "for every ordinal number a one has 2a=a+ 1" ) follow in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452034.png" /> from the axiom of constructibility.

The class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452035.png" /> can also be characterized as the smallest class that is a model of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452036.png" /> and contains all the ordinal numbers; there are other ways of defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452037.png" /> (see [[#References|[2]]]–[[#References|[4]]]). The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452038.png" /> can be expressed by a formula in the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452039.png" />, which is moreover of a simple syntactic structure (a so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452040.png" />-formula, cf. ).

Some results relating to constructible sets. The set of constructible real numbers (cf. [[Constructive real number|Constructive real number]]), that is, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452041.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452042.png" /> is the set of all real numbers, that is, sequences of zeros and ones, is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452043.png" />-set (see [[#References|[5]]]). It has been shown that the axiom of constructibility implies the existence of a Lebesgue non-measurable set of real numbers of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452044.png" /> (see [[#References|[6]]]), the negation of the [[Suslin hypothesis|Suslin hypothesis]] and the non-existence of measurable cardinal numbers (see [[#References|[2]]]).

====References====
<table><TR><TD valign="top">[1a]</TD> <TD valign="top">  K. Gödel,   "The consistency of the axiom of choice and of the generalized coninuum hypothesis"  ''Proc. Nat. Acad. Sci. USA'' , '''24'''  (1938)  pp. 556–557</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top">  K. Gödel,   "Consistency proof for the generalized coninuum hypothesis"  ''Proc. Nat. Acad. Sci. USA'' , '''25'''  (1939)  pp. 220–224</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  T.J. Jech,   "Lectures in set theory: with particular emphasis on the method of forcing" , ''Lect. notes in math.'' , '''217''' , Springer  (1971)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A. Mostowski,   "Constructible sets with applications" , North-Holland  (1969)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  C. Karp,   "A proof of the relative consistency of the continuum hypothesis"  J. Crossley (ed.) , ''Sets, models and recursion theory'' , North-Holland  (1967)  pp. 1–32</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  J.W. Addison,   "Some consequences of the axiom of constructibility"  ''Fund. Math.'' , '''46'''  (1959)  pp. 337–357</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  P.S. Novikov,   "On the non-contradictability of certain propositions of descriptive set theory"  ''Trudy Mat. Inst. Steklov.'' , '''38'''  (1951)  pp. 279–316  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  U. Felgner,   "Models of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452045.png" />-set theory" , Springer  (1971)</TD></TR></table>



====Comments====
Concerning (the notation) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452046.png" /> see [[Descriptive set theory|Descriptive set theory]].

As a consequence of Gödel's findings, if the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452047.png" /> are non-contradictory, they remain so after addition of the axiom of choice and the generalized continuum hypothesis. This was the first relative consistency result for the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452048.png" /> of any importance, to be surpassed only after a quarter of a century in 1963 by P. Cohen's [[Forcing method|forcing method]]. By forcing it is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452049.png" /> cannot prove the axiom of constructibility (unless it is contradictory). Most set theorists think there are no sufficient reasons to believe it to be true. Nevertheless, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044520/g04452050.png" /> is an important subclass of the set-theoretic universe well worth investigating.

New results can be found in [[#References|[a1]]], which is also a good introduction to constructibility. Reference [[#References|[a2]]] contains (most of) the material touched upon in the main article.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K.J. Devlin,   "Constructibility" , Springer  (1984)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T.J. Jech,   "Set theory" , Acad. Press  (1978)  pp. 523ff  (Translated from German)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K. Kunen,   "Set theory, an introduction to independence proofs" , North-Holland  (1980)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  K. Gödel,   "The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory" , Princeton Univ. Press  (1940)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  K. Devlin,   "Constructibility"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 453–490</TD></TR></table>