Constructible universe

The constructible universe or Goedel's constructible universe, commonly denoted by \(L\), is a proper class defined as the union of a hierarchy (called the constructible hierarchy) \((L_{\alpha})_{\alpha \in \textrm{On}}\) of sets, indexed by the proper class \(\textrm{On}\) of ordinals. We denote by \(V\) the von Neumann universe. Since the equality \(V = L\) is independent of ZFC set theory as long as it is consistent, we sometimes explicitly assume that every set is constructible in the sense that it is an element of \(L\).

Hierarchy

For a set \(X\), we denote by \(\textrm{Def}(X)\) the set of subsets of \(X\) definable by a first-order formula with parameters from \(X\). A first-order formula with parameters from \(X\) is a first order formula in set theory of the form \(\Phi(y,z_1,...,z_n)\) where y is a free variable (i.e. a variable which is not quantified within the formula) and \(z_1,...,z_n\in X\). A subset \(Y \subset X\) is defined in \(X\) by a formula \(\Phi\) if it exactly coincides with \(\{z\in X:\exists(z_1,\cdots,z_n\in X)\Phi(z,z_1,\cdots,z_n)\}\), i.e. every \(y \in Y\) satisfies \(\Phi\) and there are no elements \(z\in X - Y\) that satisfy \(\Phi\) (here \(-\) denotes relative complement of two sets).

Formally, \(\textrm{Def}(X)\) is the set of all \(x\subseteq X\) such that there exists some formula \(\phi\) such that \(\exists(a_0,\cdots,a_n\in X)(x=\{z\in X:X\vDash\phi(z,a_0,\cdots,a_n)\})\).

Although the definability in the explanation above looks like an ill-defined predicate requiring the "quantification of formulae", which is not allowed in the set theory itself because formulae are objects in the metatheory rather than the set theory, it is actually formalisable as a predicate in set theory itself using a non-trivial coding. Therefore the precise definition of the definability is much more complicated than the short explanation above.

Be careful that googologists often refer to the "definability" without understanding the precise formalised definition in set theory, and hence the intuitive meaning of the unformalised "definability" is usually different from the original terminology in mathematics explained above. For example, when googologists refer to something ill-defined like "the least natural number greater than any natural number definable by a first order theory using at most \(10^{100}\) symbols", then it is irrelevant to the original terminology of the definability, because it cannot be referred to in that unformalisable way.

For a class \(A\), we denine a hierarchy \((L_{\alpha}(A))_{\alpha \in \textrm{On}}\) in the following transfinite inductive way:

• If \(\alpha = 0\), then \(L_{\alpha}(A)\) is the smallest transitive class containing \(A\). (A class \(X\) is said to be transitive if \(x \subset X\) for any \(x \in X\).)
• If \(\alpha \neq 0\), then \(L_{\alpha}(A) = \bigcup_{\beta < \alpha} \text{Def}(L_{\beta}(A)) = \bigcup \{\textrm{Def}(L_{\beta}(A)) \mid \beta \in \alpha\}\).

Then the constructible universe \(L(A)\) relativised to \(A\) is defined as \(\bigcup_{\alpha \in \textrm{On}} L_{\alpha}(A)\).

When \(A = \emptyset\), then we simply denote \(L_{\alpha}(A)\) by \(L_{\alpha}\). The constructible universe \(L\) is defined as \(L(\emptyset)\), and hence is the union of the hierarchy \((L_{\alpha})_{\alpha \in \textrm{On}}\).

By the definition, we have \(L_{\alpha} \subset V_{\alpha}\) for any ordinal \(\alpha\). Note that even if we assume \(V = L\), the equality \(L_{\alpha} = V_{\alpha}\) does not necessarily hold for a given ordinal \(\alpha\) as we observe in the next section.

Example

Finite stages

By \(L_0 \subset V_0 = \emptyset\), we immediately have \(L_0 = \emptyset = \{\}\). By \(L_1 \subset V_1 = \{\{\}\}\) and \(\{\} = \{x \in L_0 \mid x=x\}\), we have \(L_1 = \{\{\}\}\). By \(L_1 \subset L_2 \subset V_2 = \{\{\},\{\{\}\}\}\) and \(\{\{\}\} = \{x \in L_1 \mid x=x\}\), we have \(L_1 = V_1\). In general, we have \(L_{\alpha} = V_{\alpha}\) for any \(\alpha \in \omega\) (more generally, this is also true for \(\alpha\in\omega+1\) as we will show below).

Stage ω

\(L_\omega=\bigcup_{\alpha\in\omega}L_\alpha\) and \(V_\omega=\bigcup_{\alpha\in\omega}V_\alpha\), so applying the above result, both unions (i.e. \(L_\omega\) and \(V_\omega\)) are equal. Also note that all elements of \(L_\omega\) have finite cardinality.

Stage ω+1 and beyond

On the other hand, we have \(L_{\omega+1} \subsetneq V_{\omega+1}\). Indeed, \(L_{\omega+1}\) is of cardinality \(\aleph_0\) by the countability of the set of formulae with paramters in the countable set \(L_{\omega} = V_{\omega}\), while \(V_{\omega+1}\) is of cardinality \(\aleph = 2^{\aleph_0}\) of \(\mathbb{R}\) because it is the power set of \(V_{\omega}\). Also \(\mathbb N\in L_{\omega+1}\) (see \(\textrm{Def}(L_\omega)\) with respect to \(\Phi(x)\) being the predicate "\(x\) is an ordinal")

Application

The constructible hierarchy is frequently used to define models of set theories. For example, if \(\alpha\) is a weakly inaccessible cardinal, then \(L_{\alpha}\) forms a model of \(\textrm{ZFC}\) set theory. By the soundness of first order logic, it implies that \(\textrm{ZFC}\) set theory augmented by the existence of a weakly inaccessible cardinal proves the formalised consistency \(\textrm{Con}(\textrm{ZFC})\) of \(\textrm{ZFC}\) set theory itself. Therefore by Goedel's incompleteness theorem, the existence of a weakly inaccessible cardinal is not provable under \(\textrm{ZFC}\) set theory as long as it is consistent.

Also, since the equality \(V = L\) is independent of \(\textrm{ZFC}\) set theory as long as it is consistent, the provability in a set theory weaker than or equal to \(\textrm{ZFC}\) set theory augumented by \(V = L\) implies the unrefutability. For example, the axiom of choice \(\textrm{AC}\) and the general continuum hypethesis \(\textrm{GCH}\) are unrefutable by \(\textrm{ZF}\) set theory as long as it is consistent, because \(L\) in \(\textrm{ZF}\) set theory forms a class model of \(\textrm{ZFC}\) set theory augmented by \(\textrm{GCH}\).

Although it is not obvious from the definition, \(\textrm{KP}\) set theory is deeply related to the constructible hierarchy. The relation appears in the connection between computation theory and set theory, and is studied in mathematics. It is also used to define the notion of the admissibility of an ordinal.

See also

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)