Gödel constructive set

Gödel constructible set, constructible set

A set that arises in the process of constructing sets described below. Let $ X $ be a set and $ R \subseteq X \times X $ a relation on $ X $. Then consider the first-order language $ L(R,X) $ containing (i) a binary predicate symbol $ \underline{R} $ denoting the relation $ R $ and (ii) individual constant symbols denoting the elements of $ X $ (for each $ x \in X $, its corresponding constant symbol is $ \underline{x} $). The statement “the formula $ \phi $ of the language $ L(R,X) $ is valid in the model $ M = (X,R) $” is written as $$ M \models \phi. $$

A set $ Y \subseteq X $ is called “definable” in the model $ M = (X,R) $ (or $ M $-definable) if and only if there exists a formula $ \phi(v) $ of $ L(R,X) $ with one free variable $ v $ such that $$ \forall x \in X: \quad x \in Y \iff M \models \phi(x). $$

Let $ \operatorname{Def}(M) $ denote the set of all $ M $-definable sets. To each ordinal $ \alpha $ is associated the set $ L_{\alpha} $ that is recursively defined by the relation $$ L_{\alpha} = \bigcup_{\beta < \alpha} \operatorname{Def} \left( L_{\beta},\in \!\! |_{L_{\beta}} \right), $$ where $ \in \!\! |_{L_{\beta}} $ denotes the membership relation restricted to $ L_{\beta} $. Hence, it follows that \begin{align} L_{0} & = \varnothing, \\ L_{1} & = \{ \varnothing \}, \\ L_{2} & = \{ \varnothing,\{ \varnothing \} \}, \\ & \vdots \\ L_{\omega} & = \bigcup_{n < \omega} L_{n}, \\ & \vdots \end{align}

A set $ z $ is called “constructible” if and only if there exists an ordinal $ \alpha $ such that $ z \in L_{\alpha} $. The class of all constructible sets is denoted by $ L $. In 1938, Kurt Gödel defined $ L $ and introduced the following axiom of constructibility: Every set is constructible. On the basis of the axioms of $ \mathsf{ZF} $, he proved that in $ L $, all axioms of $ \mathsf{ZF} $ hold as well as the axiom of constructibility, and that the axiom of choice and the generalized continuum hypothesis (“for every ordinal $ \alpha $, one has $ 2^{\aleph_{\alpha}} = \aleph_{\alpha + 1} $”) follow in $ \mathsf{ZF} $ from the axiom of constructibility.

The class $ L $ can also be characterized as the smallest class that is a model of $ \mathsf{ZF} $ and contains all the ordinals; there are other ways of defining $ L $ (see [2]–[4]). The relation $ z \in L_{\alpha} $ can be expressed by a formula in the language of $ \mathsf{ZF} $, which is moreover of a simple syntactic structure (a so-called $ \Delta_{1}^{\mathsf{ZF}} $, cf. ).

Some results relating to constructible sets. The set of constructible real numbers (cf. Constructive Real Number), that is, the set $ \mathbb{R} \cap L $ (where $ \mathbb{R} $ is the set of all real numbers, viewed as sequences of $ 0 $’s and $ 1 $’s), is a $ \Sigma_{1}^{2} $-set (see [5]). It has been shown that the axiom of constructibility implies the existence of a non-Lebesgue-measurable set of real numbers of type $ \Sigma_{1}^{2} $ (see [6]), the negation of the Suslin Hypothesis and the non-existence of measurable cardinals (see [2]).

References

[1a]	K. Gödel, “The consistency of the axiom of choice and of the generalized continuum hypothesis”, Proc. Nat. Acad. Sci. USA, 24 (1938), pp. 556–557.
[1b]	K. Gödel, “Consistency proof for the generalized continuum hypothesis”, Proc. Nat. Acad. Sci. USA, 25 (1939), pp. 220–224.
[2]	T.J. Jech, “Lectures in set theory: with particular emphasis on the method of forcing”, Lect. Notes in Math., 217, Springer (1971).
[3]	A. Mostowski, “Constructible sets with applications”, North-Holland (1969).
[4]	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.
[5]	J.W. Addison, “Some consequences of the axiom of constructibility”, Fund. Math., 46 (1959), pp. 337–357.
[6]	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).
[7]	U. Felgner, “Models of $ \mathsf{ZF} $-set theory”, Springer (1971).

Comments

Concerning (the notation) $ \Sigma_{1}^{2} $, see Descriptive Set Theory.

As a consequence of Gödel’s findings, if the axioms of $ \mathsf{ZF} $ are non-contradictory, then they remain so after adding the axiom of choice and the generalized continuum hypothesis. This was the first relative consistency result of any importance for $ \mathsf{ZF} $, to be surpassed only after a quarter of a century in 1963 by Paul Cohen’s method of forcing. By forcing, it is known that $ \mathsf{ZF} $ cannot prove the axiom of constructibility (unless it is contradictory). Most set theorists think that there are no sufficient reasons to believe it to be true. Nevertheless, $ L $ is an important subclass of the set-theoretic universe that is well worth investigating.

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

References

[a1]	K.J. Devlin, “Constructibility”, Springer (1984).
[a2]	T.J. Jech, “Set theory”, Acad. Press (1978), pp. 523ff (translated from German).
[a3]	K. Kunen, “Set theory, an introduction to independence proofs”, North-Holland (1980).
[a4]	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).
[a5]	K. Devlin, “Constructibility”, J. Barwise (ed.), Handbook of mathematical logic, North-Holland (1977), pp. 453–490.