Constructible hierarchy

The constructible hierarchy is a way of "building up" the constructible universe, the smallest ideal model of set theory which contains the ordinals. Therefore, it is important in inner model theory, as well as in the study of \(\alpha\)-recursion theory, stability, Gandy ordinals and reflection principles.

Definition

Say a subset \(X\) of \(Y\) is definable if there are some \(z_0, z_1, \cdots, z_n \in Y\) and some formula \(\varphi\) in the language of set theory so that the elements of \(X\) are precisely the \(x\) so that \(Y\) satisfies \(\varphi(x, z_0, z_1, \cdots, z_n)\). For example, under the von Neumann interpretation, the set of even numbers, the set of odd numbers, the set of prime numbers, the set of perfect squares greater than 17, and so on, are all definable. Using elementary cardinal arithmetic, you can note that there \(\max(\aleph_0, |Y|) = |Y|\) definable subsets of an infinite set \(Y\), and thus "almost all" subsets of an infinite set are not definable. The parameters \(\vec{z}\) aren't of importance in the context of definable subsets of the natural numbers, since all elements of the natural numbers are definable, but they will be if \(Y\) is uncountable, because no uncountable be pointwise definable, and ensure that there aren't just always \(\aleph_0\) definable subsets of a set.

Like with the von Neumann hierarchy, the constructible hierarchy is built up in stages, denoted \(L_\alpha\).

• \(L_0\) is the empty set.
• \(L_{\alpha+1}\) is the collection of definable subsets of \(L_\alpha\).
• For limit \(\alpha\), \(L_\alpha\) is the union of \(L_\beta\) for \(\beta < \alpha\).

Note that this is a cumulative hierarchy, and thus the reflection principle applies.

This is always contained in the respective rank of the von Neumann hierarchy: \(L_\alpha \subseteq V_\alpha\). This can be shown by a transfinite induction argument. It initially completely actually agrees with \(V\): all subsets of a finite set are definable, therefore \(L_\alpha = V_\alpha\) for \(\alpha \leq \omega\). However, while \(V_{\omega+1}\) is uncountable, there are (as we mentioned) only countably many subsets of a countable subset, and thus \(L_{\omega+1}\) is countable and a proper subset of \(V_{\omega+1}\). In general, \(|L_\alpha| = |\alpha|\) for \(\alpha \geq \omega\).

If \(\kappa = \beth_\kappa\), then \(|L_\kappa| = |V_\kappa|\). However, the existence of a \(\kappa > \omega\) so that \(L_\kappa = V_\kappa\) (they're equal, not just equinumerous) is independent from the axioms of \(\mathrm{ZFC}\), if they're consistent. This is because some models of \(\mathrm{ZFC}\) think it's true, and others think it's false, thus the completeness theorem applies.

The constructible universe is defined analogously to \(V\), by letting \(L\) be the union of \(L_\alpha\) among all ordinals \(\alpha\).

For all \(\alpha\), the ordinals which are elements of \(L_\alpha\) are precisely the ordinals less than \(\alpha\). That is, \(\mathrm{Ord} \cap L_\alpha = \alpha\). We show this by induction:

• \(\mathrm{Ord} \cap L_0 = \mathrm{Ord} \cap \emptyset = \mathrm{Ord} \cap 0 = 0\).
• Assume \(\mathrm{Ord} \cap L_\alpha = \alpha\). Then \(\alpha\) is a definable subset of \(L_\alpha\) since \(\alpha\) is just the set of \(x \in L_\alpha\) which \(L_\alpha\) thinks are ordinals, so \(\alpha \in L_{\alpha+1}\). For \(\beta > \alpha\), \(\alpha \notin L_\alpha\) yet \(\alpha \in \beta\), therefore \(\beta\) is not a definable subset of \(L_\alpha\) and so \(\beta \notin L_{\alpha+1}\). Lastly, we have \(\gamma \in L_{\alpha+1}\) for \(\gamma < \alpha\), therefore \(\mathrm{Ord} \cap L_\alpha = \alpha \cup \{\alpha\} = \alpha+1\).
• If \(\alpha\) is a limit ordinal, \(\mathrm{Ord} \cap L_\alpha = \mathrm{Ord} \cap (\bigcup_{\beta < \alpha} L_\beta) = \bigcup_{\beta < \alpha} (\mathrm{Ord} \cap L_\beta) = \bigcup_{\beta < \alpha} \beta = \alpha\).

In particular, \(\mathrm{Ord} \cap L_\alpha = \mathrm{Ord} \cap V_\alpha\) for all \(\alpha\), and \(L\) contains all the ordinals. A similar method can be used to show that \(L_\alpha\) is transitive for all \(\alpha\), and that \(L_\alpha \in L_\beta\) for all \(\alpha < \beta\).

Alternate characterisations

Kurt Gödel, the inventor of the constructible universe, isolated 10 basic "Gödel operations", relatively simple operations on sets which can be used to built up the universe of sets. They are:

• \((X, Y) \mapsto \{X, Y\}\), i.e. the unordered pair of \(X\) and \(Y\)
• \((X, Y) \mapsto X \times Y\), i.e. the Cartesian product of \(X\) and \(Y\)
• \((X, Y) \mapsto \{(x,y): y \in Y \land x \in X \cap y \}\), i.e. the restriction of the elementhood relation to \(X \times Y\)
• \((X, Y) \mapsto X \setminus Y\), i.e. the complement of \(Y\) relative to \(X\)
• \((X, Y) \mapsto X \cap Y\), i.e. the intersection of \(X\) and \(Y\)
• \(X \mapsto \bigcup X\), i.e. the union of \(X\)
• \(X \mapsto \{x: \exists y ((x, y) \in X)\}\), i.e. the domain of \(X\)
• \(X \mapsto \{(x,y): (y,x) \in X\}\), i.e. the inverse of \(X\)
• \(X \mapsto \{(x,z,y): (x,y,z) \in X\}\)
• \(X \mapsto \{(z,x,y): (x,y,z) \in X\}\)

For a set \(X\), we let \(\mathrm{cl}(X)\) be the closure of \(X\) under the Gödel operations - i.e. under taking unions, intersections, permutations, and more.

He proved that, for all sets \(X\), a subset of \(X\) is definable iff it is an element of \(\mathrm{cl}(X \cup \{X\})\). The proof is based on his normal form theorem, which asserts that, if \(\varphi(x_1, x_2, \cdots, x_n)\) is a \(\Delta_0\)-formula, then, for all \(X_1, X_2, \cdots, X_n\), the set \(\{(x_1, x_2, \cdots, x_n) \in X_1 \times X_2 \times \cdots \times X_n: \varphi(x_1, x_2, \cdots, x_n)\}\) is given by a composition of the Gödel operations. Therefore, we can alternatively define the constructible hierarchy like so:

• \(L_0 = \emptyset\).
• \(L_{\alpha+1} = \mathrm{cl}(L_\alpha \cup \{L_\alpha\}) \cap \mathcal{P}(L_\alpha)\).
• For limit \(\alpha\), \(L_\alpha = \bigcup_{\beta < \alpha} L_\beta\).

As we've mentioned earlier, \(L\) contains all the ordinals. And since it's closed under unions, unordered pair, and further, it is possible to show that \(L\) is a model of \(\mathrm{ZFC}\). See the Wikipedia article for a full proof. Therefore, \(L\) is an inner model (i.e. a transitive model of ZFC containing all the ordinals), and a famous theorem proves that \(L\) is the minimal inner model. That is, for all \(X \subset L\), we either have:

• \(X\) does not satisfy ZFC.
• There is an ordinal not in \(X\).
• \(X\) is not transitive.

Work of Jensen showed that, within \(L\), various fine structure and combinatorics hold. This includes the generalized continuum hypothesis and the diamond principle. However, Scott proved that measurable cardinals can not exist in \(L\) (if \(\kappa\) is measurable, \(\kappa\) is still an element of \(L\), but the necessary measure witnessing its measurability can't be in \(L\), and thus \(L\) doesn't realize it's measurable). This is because \(L\) thinks \(V = L\), yet the existence of a measurable cardinal implies \(V \neq L\):

Assume \(\kappa\) is measurable, and let \(\mathcal{U}\) witness this. Assume \(V = L\). Set \(\mathcal{M} = (V^\kappa / \mathcal{U}, \in_{\mathcal{U}})\) be the ultrapower. By \(\kappa\)-completeness, the relation \(\in_{\mathcal{U}}\) is well-founded, extensional and set-like. Therefore, the Mostowski collapse lemma implies that there is some transitive \(M\) so that \((M, \in) \cong \mathcal{M}\). Let \(\pi: V^\kappa / \mathcal{U} \to M\) be the isomorphism, and \(\tilde{j}: V \to V^\kappa / \mathcal{U}\) be the canonical ultrapower embedding. Set \(j = \pi \circ \tilde{j}\). Then \(j: V \to M\). Clearly, \(M\) is an inner model, thus \(L \subseteq M\), and since \(V = L\), \(V = M\). Thus, \(j: V \to V\) is an elementary embedding. You can see that the critical point is \(\kappa\): for all \(\alpha < \kappa\), \([\alpha, \alpha, \cdots] \in_{\mathcal{U}} [0, 1, 2, \cdots]\) and thus \(\pi([0, 1, 2, \cdots]) = \kappa\), and \([0, 1, 2, \cdots] \in_{\mathcal{U}} [\kappa, \kappa, \kappa, \cdots]\). Thus, \(j(\kappa) > \kappa\) and, for all \(\alpha < \kappa\), \(j(\alpha) = \alpha\). \( Let \(\varphi(x)\) be the formula "\(x\) is the least measurable cardinal", which is first-order expressible. Then, since \(V \models \varphi(\kappa)\), we have \(V \models \varphi(j(\kappa))\). Therefore, \(j(\kappa)\) is the least measurable cardinal. Contradiction!

Inner model theory is the practice of finding canonical inner models which are defined in a similar way to \(L\) and have the same fine structure but are able to accomodate large cardinals.