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.K. Kunen, Set Theory: An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics, Volume 102, North Holland, 1983. 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\).Keith J. Devlin, Constructibility, Perspectives in Mathematical Logic, Volume 6, Springer-Verlag, 1984. 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 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)\})\)K. Devlin, An introduction to the fine structure of the constructible hierarchy (p.2).
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 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.
== References ==
== See also ==
ja:宇宙 (数学)
Category:Proper class
Category:Set theory