# Abstract Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the sixth publication in the Perspectives in Logic series, Keith J. Devlin gives a comprehensive account of the theory of constructible sets at an advanced level. The book provides complete coverage of the theory itself, rather than the many and diverse applications of constructibility theory, although applications are used to motivate and illustrate the theory. The book is divided into two parts: Part I (Elementary Theory) deals with the classical definition of the Lα-hierarchy of constructible sets and may be used as the basis of a graduate course on constructibility theory. and Part II (Advanced Theory) deals with the Jα-hierarchy and the Jensen 'fine-structure theory'. # Chapter I. Preliminaries ## 9. The language $\mathcal{L}_{V}$ A formal analogue of the metamathematical language LST. Every formula of LST is represented in an explicit way as a set. Every set $x$ (in $V$) has an associated constant symbol $\mathring{x}$. **Notation+Lemma** There are $\Sigma_{0}$ formulas in LST which express the notions on the rhs: - $\mathrm{Vbl}(x)$ : $x$ is a variable - $\mathrm{Const}(x)$ : $x$ is a constant symbol - $\mathrm{PFml}(x)$ : $x$ is a primitive formula - $\mathrm{Finseq}(x)$ : $x$ is a finite sequence - $\mathrm{Build}(x,f)$ : $f$ is a construction sequence (in the sense of formulas) ending in $x$ There are $\Sigma_{1}$ formulas, which are in fact $\Delta_{1}^{\mathrm{BS}}$ ($\mathrm{BS}$ is [[Basic Set Theory]]), as follows: - $\mathrm{Fml}(x)$ : $x$ is a formula of $\mathcal{L}_{V}$ - The above can be relativized to allow only constants from some set $u$ (adding another variable to the formulas, e.g. $\mathrm{Fml}(\varphi,u)$ ) to obtain the language $\mathcal{L}_{u}$. $\mathcal{L}=\mathcal{L}_{\varnothing}$ - $\mathrm{Fr}(z,x)$ : $x$ is the set of free variables in the formula $z$. - $\mathrm{Sub}(z',z,v,t)$ : $z'$ is the result of substituting $t$ instead of $v$ in $z$. - $\mathrm{Sat}(u, \varphi)$ : $\varphi$ is a sentence of $\mathscr{L}_u$ which is true in the structure $\langle u, \epsilon\rangle$ under the canonical interpretation (i.e. with $x$ interpreting $\mathring{x}$ for each $x\in u$ ). - $\mathrm{Sat}(u,\varphi)$ is also denoted by $\vDash_{u}\varphi$. The content of $\mathrm{Sat}(u,\varphi)$ is as follows: There are finite sequences $f,g$ with the same domain (say $d$), such that: - For every $i<d$, $f(i)$ contains all formulas in $u$ with construction sequence of length $i+1$ (i.e. $f(0)$ is all primitive formulas, $f(i+1)$ contains all formulas constructed from formulas in $f(i)$). - $\varphi \in g(d-1)$. - For every $i<d$, $g(i)$ contains all formulas in $f(i)$ which are true in $\left< u,\in \right>$, using a recursive definition, i.e. a conjunction of the following: - $\psi \in g(0) \leftrightarrow \exists x,y\in u [\psi \approx \mathring{x}=\mathring{x} \lor (x\in y \land \psi \approx \mathring{x}\in \mathring {y})]$ - $\psi \in g(i+1)$ iff one of the following hold - $\psi \in g(i)$ or - $\exists \theta,\theta' \in g(i) [\psi \approx \theta \land \theta']$ - $\exists \theta \in f(i) [\theta \notin g(i) \land \psi \approx \neg \theta ]$ - $\exists \theta \in f(i) \exists v \exists x\in u \exists \theta' \in g(i) [\mathrm{Vbl}(v) \land \psi \approx \exists v \theta \land \mathrm{Sub}(\theta',\theta,v,\mathring{x})]$ where e.g. $\psi \approx \neg \theta$ is shorthand for a formula $F_{\neg}(\psi,\theta)$ explicitly expressing this notion. **Lemma 9.11.** Let $\Phi\left(v_0, \ldots, v_n\right)$ be any formula of LST, and let $\varphi\left(v_0, \ldots, v_n\right)$ be its counterpart in $\mathscr{L}$ (in the sense described above). Then $ \mathrm{ZF} \vdash \forall u\left(\forall x_0 \in u\right) \ldots\left(\forall x_n \in u\right)\left[\Phi^u\left(x_0, \ldots, x_n\right) \leftrightarrow \operatorname{Sat}\left(u, \varphi\left(\mathring{x}_0, \ldots, \mathring{x}_n\right)\right]\right. $ **Lemma**. Let $\Phi(\vec{x})$ be a $\Sigma_0$ formula of LST, and let $\varphi(\vec{x})$ be its counterpart in $\mathscr{L}$. Then ZF $\vdash$ "For any transitive set $M,(\forall \vec{x} \in M)\left[\Phi(\vec{x}) \leftrightarrow \vDash_M \varphi(\vec{x})\right]$ ". ### Adding predicates (pg 43) Let $k$ be some natural number and let $A_1 \subseteq u^{n(1)}, \ldots, A_k \subseteq u^{n(k)}$. The language $\mathscr{L}_u(\mathring{A}_1, \ldots, \mathring{A}_k)$ has the same structure as $\mathscr{L}_u$ except that among the primitive formulas there are the $k$ extra predicate letters $\mathring{A}_1, \ldots, \mathring{A}_k$, where $\mathring{A}_i$ is $n(i)$-ary for each $i$. For transitive $u$ all the above results generalise to this language. ## 10. Definability >[!note] Definition >Let $\mathbf{M}=\left\langle M, \epsilon, A_1, \ldots, A_k\right\rangle$ and $N \subseteq M$. >A set $R \subseteq M^m$ is said to be $\Sigma_n^M(N)$ iff there is a $\Sigma_n$ formula $\varphi\left(v_0, \ldots, v_{m-1}\right)$ of the M-language, whose constants are all members of the set $\{\grave{a} \mid a \in N\}$, such that > $ > \left(\forall x_0, \ldots, x_{m-1} \in M\right)\left[\left(x_0, \ldots, x_{m-1}\right) \in R \leftrightarrow \vDash_{M} \varphi\left(\mathring{x}_0, \ldots, \mathring{x}_{m-1}\right)\right] . > $ > Similary for $\Pi_n^{\mathrm{M}}(N)$. A set $R \subseteq M^m$ is $\Delta_n^{\mathrm{M}}(N)$ iff it is both $\Sigma_n^{\mathrm{M}}(N)$ and $\Pi_n^{\mathrm{M}}(N)$. We write $\Sigma_n^{\mathcal{M}}$ instead of $\Sigma_n^{\mathcal{M}}(\emptyset)$ and $\Sigma_n(\mathbf{M})$ instead of $\Sigma_n^{\mathcal{M}}(M)$. Similarly for $\Pi$ and $\Delta$. > A set $R \subseteq M^m$ is said to be *$\mathbf{M}$-definable* iff it is $\Sigma_n(\mathbf{M})$ for some $n$. > Let $A$ be some class of $m$-tuples, $\mathbf{M}$ a given structure. We say that the class $A$ is $\Sigma_n^{\mathrm{M}}(N)$ iff $A \cap M^m$ is $\Sigma_n^M(N)$, etc. > Let $\mathscr{F}$ be a class of structures of the form $\mathbf{M}=\left\langle M, \epsilon, A_1, \ldots, A_k\right\rangle$, where $k$ is fixed and each $A_i$ is $n(i)$-ary, for fixed $n(i)$, $i=1, \ldots, k$. Let $A$ be a class of $m$-tuples. We say that $A$ is u*niformly $\Sigma_n^M$ for $\mathbf{M} \in \mathscr{F}$* iff there is a single $\Sigma_n$ formula $\varphi\left(v_0, \ldots, v_{m-1}\right)$ of $\mathscr{L}(\mathring{A}_1, \ldots, \mathring{A}_k)$ such that for each $\mathbf{M} \in \mathscr{F}$, > $ > A \cap M^m=\left\{\left(x_0, \ldots, x_{m-1}\right) \mid \vDash_{\mathbf{M}} \varphi\left(\mathring{x}_0, \ldots, \mathring{x}_{m-1}\right)\right\} . > $ > Similary for uniformly $\Pi_n^M$ and uniformly $\Delta_n^M$. >[!info] Definition >A set $M$ is said to be *amenable* iff it is transitive and satisfies the following conditions: > i) $(\forall x, y \in M)(\{x, y\} \in M)$; > ii) $(\forall x \in M)(\bigcup x \in M)$; > iii) $\omega \in M$; > iv) $(\forall x, y \in M)(x \times y \in M)$; > v) if $R \subseteq M$ is $\Sigma_0(M)$, then $(\forall x \in M)(R \cap x \in M)$. ^amenable ## 11. Kripke-Platek Set Theory. Admissible Sets [[Kripke-Platek]], [[Admissible set]]. # Chapter II. The Constructible universe ## 1. Definition of the Constructible Universe >[!info] Definition > Let $X$ be any set. By $\operatorname{Def}(X)$ we mean the set of all subsets of $X$ which are $X$-definable, i.e all sets, $a$, such that for some formula $\varphi\left(v_0\right)$ of $\mathscr{L}_X$, > $ > a=\left\{x \in X \mid \vDash_X \varphi(\mathring{x})\right\} . > $ > Note that $\mathrm{Def}$ is a well-defined set-theoretic function. > By recursion on $\alpha \in$ On we define > $ > L_0=\emptyset ; \quad L_{\alpha+1}=\operatorname{Def}\left(L_\alpha\right) ; \quad L_\lambda=\bigcup_{\alpha<\lambda} L_\alpha, \quad \text { if } \lim (\lambda) > $ > ( $L_\alpha \mid \alpha \in \mathrm{On}$ ) is the *constructible hierarchy*, and is clearly a well-defined function (in the class sense) of ZF set theory. > Hence $L$ , the *constructible universe*, is a welldefined class, where we set: > $ > L=\bigcup_{\alpha \in \text { On }} L_\alpha > $ >A set $x$ is said to be *constructible* iff $x \in L$. **1.1 Lemma.** (i) $\alpha \leqslant \beta$ implies $L_\alpha \subseteq L_\beta$. (ii) Each $L_\alpha$ is transitive. (Hence $L$ is transitive.) (iii) $L_\alpha \subseteq V_\alpha$ for all $\alpha$. (iv) $\alpha<\beta$ implies $\alpha, L_a \in L_\beta$. (Hence On $\subseteq L$.) (v) For all $\alpha, L \cap \alpha=L_\alpha \cap \mathrm{On}=\alpha$. (vi) For $\alpha \leqslant \omega, L_\alpha=V_\alpha$. (vii) For $\alpha \geqslant \omega,\left|L_\alpha\right|=|\alpha|$. **1.2 Theorem.** The class $L$ is an inner model of $\mathrm{ZF}$. More precisely, for every axiom $\Phi$ of $\mathrm{ZF}$, $ \mathrm{ZF} \vdash \Phi^L . $ ## 2. The Constructible Hierarchy. The Axiom of Constructibility **2.1 Lemma.** For each limit ordinal $\alpha>\omega, L_\alpha$ is [[Devlin - Constructibility#^amenable|amenable]]. %%%% %% **2.2-2.3 Lemma.** Let $\operatorname{Seq}(y, x)$ and $\operatorname{Pow}(y, x)$ be the LST formulas which say - that $y$ is the set of all finite sequence from $x$. - that $y$ is the set of all finite subsets $x$. (i) The $\operatorname{LST}$ formulas $\operatorname{Seq}(y, x)$ and $\operatorname{Pow}(y, x)$ are $\Delta_1^{\mathrm{KP}}$. (ii) The classes $\operatorname{Seq}$ and $\operatorname{Pow}$ are uniformly $\Delta_1^{L_\alpha}$ for limit $\alpha>\omega$. We shall now write down an LST formula $A(v, u)$ such that $ A(v, u) \leftrightarrow v=\operatorname{Def}(u) $ Namely: $ \begin{aligned} & (\forall x \in v)(\exists \varphi)\left[\operatorname{Fml}(\varphi, u) \wedge \operatorname{Fr}\left(\varphi,\left\{v_0\right\}\right) \wedge(x \subseteq u)\right. \\ & \left.\wedge(\forall z \in u)\left(z \in x \leftrightarrow \exists \psi\left(\operatorname{Sub}\left(\psi, \varphi, v_0, z\right) \wedge \operatorname{Sat}(u, \psi)\right)\right)\right] \\ & \wedge(\forall \varphi)\left[\left(\operatorname{Fml}(\varphi, u) \wedge \operatorname{Fr}\left(\varphi,\left\{v_0\right\}\right)\right)\right. \\ & \rightarrow(\exists x \in v)[(x \subseteq u) \wedge(\forall z \in u)(z \in x \\ & \left.\left.\left.\leftrightarrow \exists \psi\left(\operatorname{Sub}\left(\psi, \varphi, v_0, z\right) \wedge \operatorname{Sat}(u, \psi)\right)\right)\right]\right] . \end{aligned} $ **2.4 Lemma.** There is an $\mathrm{LST}$ formula $D(v,u)$ equivalent to $A(v,u)$ s.t. (i) The LST formula $D(v, u)$ is $\Sigma_1$ and $\Delta_1^{\mathrm{KP}}$. (ii) The class $D$ is uniformly $\Delta_1^{L_\alpha}$ for limit $\alpha>\omega$. **2.5 Corollary.** The function $\mathrm{Def}$ is uniformly $\Delta_1^{L_\alpha}$ for limit $\alpha>\omega$. %% **Lemmas 2.2-2.8.** The following notions are $\Delta_1^{\mathrm{KP}}$ and the corresponding classes are uniformly $\Delta_1^{L_\alpha}$ for limit $\alpha>\omega$: - $\operatorname{Seq}(y, x)$ : $y$ is the set of all finite sequence from $x$. - $\operatorname{Pow}(y, x)$ : $y$ is the set of all finite subsets $x$. - $D(v,u)$ : $v=\operatorname{Def}(u)$ - $G(f, \alpha)$ : $f=\left(L_\gamma \mid \gamma \leqslant \alpha\right)$ - $H(x,\alpha)$ : $x=L_{\alpha}$ **Lemmas 2.9-2.13.** 9. Let $M$ be an inner model of KP. For any $\alpha \in \mathrm{On}, L_\alpha \in M$ and $\left(L_\alpha\right)^M$ $=L_\alpha$. (This equality means that if $[H(x, \alpha)]^M$, then $x=L_\alpha$.) Hence $(L)^M=L$. 10. Let $M$ be an admissible set, and let $\lambda=\sup (M \cap$ On). For any $\alpha \in \lambda$, $\left(L_\alpha\right)^M=L_\alpha$. Hence $(L)^M=L_\lambda$. 11. For any $\alpha,\left(L_\alpha\right)^L=L_\alpha$. Hence $(L)^L=L$. 12. Let $\alpha>\omega$ be a limit ordinal. For all $\gamma<\alpha,\left(L_\gamma\right)^{L_\alpha}=L_\gamma$. Hence $(L)^{L_\alpha}=L_\alpha$. 13. The LST formula "$x$ is constructible" i.e. $x\in L$ or $\exists\alpha(x\in L_{\alpha})$ is $\Sigma_1^{\mathrm{KP}}$. >[!info] Definition >The *Axiom of Constructibility* is the assertion that all sets are constructible: >$ >\forall x(x \in L) . >$ > This is usually abbreviated as: > $ > V=L . >$ **2.14 Lemma.** The LST formula $V=L$ is $\Pi_2^{K P}$. **2.15 Theorem.** $\mathrm{ZF} \vdash(V=L)^L$. Hence $L$ is an inner model of the theory $\mathrm{ZF}+(V=L)$. ## 3. The Axiom of Choice in $L$ **3.1 Lemma.** Let $x \in L_{a+1}$. Then there is a formula $\varphi\left(v_0, \ldots, v_n\right)$ of $\mathscr{L}$ (so in particular $\varphi$ contains no individual constant symbols) and ordinals $\gamma_1, \ldots, \gamma_n<\alpha$ such that $ x=\left\{z \in L_\alpha \mid \ \vDash_{L_\alpha} \varphi\left(\mathring{z}, \mathring{L}_{\gamma_1}, \ldots, \mathring{L}_{\gamma_n}\right)\right\} $ Fix an effective well-ordering of the formulas $\prec$ and denote by lt;^{*}$ the lexicographic order on finite sequences of ordinals (shorter sequences come first). >[!info] Definition - The well ordering of $L$ >Let $x, y \in L$. We set *$x<_L y$* iff either: > (A) The least $\alpha$ such that $x \in L_{\alpha+1}$ is smaller than the least $\beta$ such that $y \in L_{\beta+1}$; or else > (B) there is an $\alpha$ such that $x$ and $y$ both lie in $L_{\alpha+1}-L_\alpha$ and either: >> (B1) the $\prec$-least formula $\varphi\left(v_0, \ldots, v_n\right)$ of $\mathscr{L}$ for which there are ordinals $\gamma_1, \ldots, \gamma_n<\alpha$ such that >> $x=\left\{z \in L_\alpha \mid \vDash_{L_\alpha} \varphi\left(\mathring{z}, \mathring{L}_{\gamma_1}, \ldots, \mathring{L}_{\gamma_n}\right)\right\}$ >> $\prec$-precedes the $\prec$-least formula $\psi\left(v_0, \ldots, v_m\right)$ of $\mathscr{L}$ for which there are ordinals $\delta_1, \ldots, \delta_m<\alpha$ such that >> $y=\left\{z \in L_\alpha \mid \vDash_{L_\alpha} \psi\left(\mathring{z}, \mathring{L}_{\delta_1}, \ldots, \mathring{L}_{\delta_n}\right)\right\} ;$ >> or else > (B2) the formulas $\varphi$ and $\psi$ in (B1) coincide, but the lt;^*$-least $n$-sequence $\left\langle\gamma_1, \ldots, \gamma_n\right\rangle$ of ordinals $\gamma_i<\alpha$ which defines $x$ as in (B1) lt;^{*}$-precedes the lt;^*$-least $n$-sequence $\left\langle\delta_1, \ldots, \delta_n\right\rangle$ of ordinals $\delta_i<\alpha$ which defines $y$. The definition above can be done using a simple formula: **3.2 Lemma.** There is a $\Sigma_{1}$ LST formula, denoted $\mathrm{WO}(x,y)$, such that (i) $\mathrm{WO}(x, y)$ is $\Delta_1^{\mathrm{KP}+(V=L)}$. (ii) $\operatorname{KP\vdash }quot;$\{(x, y) \mid \mathrm{WO}(x, y)\}$ is a well-ordering of $L$ ". **3.3 Lemma.** Let $wo(x, y)$ be the analogue of $\mathrm{WO}(x, y)$ in $\mathscr{L}$. Then: (i) If $x, y \in L_\alpha$, then $\mathrm{WO}(x, y) \leftrightarrow F_{L_\gamma}$ wo $(\dot{x}, \dot{y})$ where $\gamma=\max (\omega, \alpha+5)$. (ii) If $\alpha>\omega$ is a limit ordinal, then $ \left\{(x, y) \mid \ \vDash_{L_\alpha} \mathrm {wo}(\mathring{x}, \mathring{y})\right\} \quad \text { is a well-ordering of } L_\alpha \text {. } $ (iii) The relation $x<_L y$ is uniformly $\Delta_1^{L_\alpha}$ for limit $\alpha>\omega$. **3.6 Lemma.** There is a $\Sigma_1$ formula $\mathrm{Enum}(\alpha, x)$ of LST, absolute for $L$, such that $\operatorname{KP}\vdash$ "If $F=\{(x, \alpha) \mid \operatorname{Enum}(\alpha, x)\}$, then $F: \mathrm{On} \leftrightarrow L$ ". **3.7 Lemma**. $\mathrm{KP} \vdash \forall a(a \subseteq \mathrm{On} \rightarrow a \in L) \rightarrow(V=L)$. **3.8 Theorem.** $\mathrm{ZF} \vdash(\mathrm{AC})^L$. ## 4. Constructibility and Relative Consistency Results **4.2 Theorem.** If $\mathrm{ZF}$ is a consistent theory, so too is $\mathrm{ZFC}+(V=L)$. **4.4 Theorem (The Minimal Model Property for KP).** $L$ is the smallest inner model of KP. ## 5. The Condensation Lemma. The GCH in $L$