# 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 the (Gödel) constructible universe, 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).

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.