## 502 – The constructible universe

In this set of notes I want to sketch Gödel’s proof that ${{\sf CH}}$ is consistent with the other axioms of set theory. Gödel’s argument goes well beyond this result; his identification of the class ${L}$ of constructible sets eventually led to the development of inner model theory, one of the main areas of active research within set theory nowadays.

A good additional reference for the material in these notes is Constructibility by Keith Devlin.

1. Definability

The idea behind the constructible universe is to only allow those sets that one must necessarily include. In effect, we are trying to find the smallest possible transitive class model of set theory.

${L}$ is defined as

$\displaystyle L=\bigcup_{\alpha\in{\sf ORD}} L_\alpha,$

where ${L_0=\emptyset,}$ ${L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha}$ for ${\lambda}$ limit, and ${L_{\alpha+1}={\rm D{}ef}(L_\alpha),}$ where

$\displaystyle \begin{array}{rcl} {\rm D{}ef}(X)=\{a\subseteq X&\mid&\exists \varphi\,\exists\vec b\in X\\ && a=\{c\in X\mid(X,\in)\models\varphi(\vec b,c)\}\}. \end{array}$

The first question that comes to mind is whether this definition even makes sense. In order to formalize this, we need to begin by coding a bit of logic inside set theory. The recursive constructions that we did at the beginning of the term now prove useful.

I won’t provide full details, but I expect that what follows allows you to fill in the gaps without difficulties.We begin by coding formulas inside set theory. For this, we begin by coding variables. What I mean is, recall that our official list of variables is ${v_0,v_1,\dots}$ even though we usually write ${x,y,\dots}$We need to assign a set to each variable in a way that whenever we want to talk about the variable, we can instead talk about the set. Then we will do the same for all the logical symbols, and use this to code formulas.

One simple way of coding variables is letting the ordered pair ${(0,n)}$ code the variable ${v_n.}$ Clearly, there is a formula

$\displaystyle {\rm Vbl}(x)$

that holds of ${x}$ iff ${x}$ codes a variable, namely, ${{\rm Vbl}(x)}$ states that ${x}$ is an ordered pair, that its first coordinate is 0, and its second coordinate is a natural number.

(Later, we will code some symbols with natural numbers. It is in order to distinguish between these symbols and the variables, that we use ${(0,n)}$ rather than simply ${n}$ to code ${v_n.}$)

It will prove convenient to use constants, to represent sets. We have a constant ${c_a}$ for each set ${a}$. We want to code each constant by a set. One way could be to simply let the set ${a}$ act as the constant ${c_a.}$ Unfortunately, this would be ambiguous, as when we have coded a formula ${\phi}$ by a set ${x_\phi}$, we wouldn’t know whether ${x_\phi}$ is coding ${\phi}$ or the constant ${c_{x_\phi}}$, for example. There are other issues as well. For this reason, we choose to code the constant ${c_a}$ by the ordered pair ${(1,a).}$ As before, there is a formula

$\displaystyle {\rm Const}(x)$

which holds of ${x}$ iff ${x}$ codes a constant ${c_a}$ for some ${a.}$

Now that we have coded variables and constants, we can code formulas. We will represent the logical symbols as follows:

$\displaystyle \begin{array}{rcc} 2&\mbox{codes}&(\\ 3&\mbox{codes}&)\\ 4&\mbox{codes}&=\\ 5&\mbox{codes}&\in\\ 6&\mbox{codes}&\lnot\\ 7&\mbox{codes}&\rightarrow\\ 8&\mbox{codes}&\forall \end{array}$

and other symbols, ${\land,\lor,\exists,\dots}$ are treated as abbreviations.

We begin by coding atomic formulas. Remember that these are formulas of the form ${(a\in b)}$ or ${(a=b)}$ where ${a,b}$ are either constants or variables. We simply code them by a finite sequence and, in general, we will use finite sequences to represent formulas. The sequence coding ${(a*b),}$ where ${*}$ is either ${=}$ or ${\in,}$ would be ${s_0s_1s_2s_3s_4}$ where ${s_0}$ codes ${(}$, ${s_1}$ codes ${a}$, ${s_2}$ codes ${*}$, etc. Formally, we see that there is a formula

$\displaystyle {\rm Atom}(x)$

That holds iff ${x}$ codes an atomic formula: ${{\rm Atom}(x)}$ says that ${x}$ is a function with domain ${5,}$ that ${x(0)=2,}$ ${x(4)=3,}$ ${x(2)\in\{4,5\}}$ and, for ${i=1,3,}$ ${{\rm Var}(x(i))\lor{\rm Const}(x(i)).}$

To code arbitrary formulas, remember that to each ${\phi}$ we can associate a parsing sequence ${\phi_0,\dots,\phi_n}$ consisting of the subformulas of ${\phi}$ listed in such a way that whenever a formula ${\psi}$ is listed, all its subformulas have been listed before, and that if ${\phi}$ appears in a parsing sequence, then it is indeed a formula. We can then define

$\displaystyle {\rm Form}(x)$

by saying that there is a function ${f}$ with domain some natural number ${k+1}$ and such that ${f(k)=x}$ and, for all ${i\le k,}$ we have that

$\displaystyle {\rm Atom}(f(i))$

or there is a ${j such that

$\displaystyle f(i)\rm{\ codes\ }\lnot(\psi_j),$

where ${\psi_j}$ is the formula coded by ${f(j)}$ (which we can take simply to mean that ${f(i)}$ is a sequence of length ${4,}$ that ${f(i)(0)=6,}$ ${f(i)(1)=2,}$ ${f(i)(2)=f(j),}$ and ${f(i)(3)=3}$), or there are ${j,n such that

$\displaystyle f(i)\rm{\ codes\ }(\psi_j\rightarrow\psi_n),$

where ${\psi_j,\psi_n}$ are the formulas coded by ${f(j),f(n)}$ (meaning, ${f(i)}$ is a sequence of length 5, ${f(i)(0)=2,}$ ${f(i)(1)=f(j),}$ ${f(i)(2)=7,}$ ${f(i)(3)=f(n),}$ and ${f(i)(4)=3}$), or there is ${j, and a variable ${v_n,}$ such that

$\displaystyle f(i)\mbox{\ codes\ }\forall v_n\,\psi_j,$

where ${\psi_j}$ is the formula coded by ${f(j)}$ (meaning, ${f(i)}$ is a sequence of length 3, ${f(i)(0)=8,}$ ${{\rm Var}(f(i)(1)),}$ and ${f(i)(2)=f(j)}$). Any function ${f}$ witnessing ${{\rm Form}(x)}$ we can call a parsing witness for ${x.}$ We can then define a class function

$\displaystyle {\rm Free}$

that, whenever ${{\rm Form}(x)}$ holds, assigns to ${x}$ the set of free variables of the formula ${\psi}$ coded by ${x.}$ Remember that this means that ${{\rm Free}(x,y)}$ is a formula of two free variables, that for every ${x}$ there is a unique ${y}$ such that ${{\rm Free}(x,y)}$ holds, and that if ${{\rm Form}(x)}$, then ${y}$ is as stated and, as usual, we write ${y={\rm Free}(x)}$ rather than ${{\rm Free}(x,y).}$ The definition of ${{\rm Free}}$ is by recursion, using a parsing witness for ${x}$. More carefully, we define ${{\rm Free}(x)}$ by recursion, so that if ${{\rm Form}(x)}$ fails, then ${{\rm Free}(x)=\emptyset.}$ Otherwise,

• If ${x}$ codes ${(a=b)}$ then ${{\rm Free}(x)}$ is ${\{(0,n)\}}$ if exactly one of ${a,b}$ is a variable, and that variable is ${v_n,}$ or ${\{(0,n),(0,m)\}}$ if ${a=v_n}$ and ${b=v_m,}$ or ${\emptyset}$ otherwise.
• If ${x}$ codes ${\lnot(\psi)}$ and ${y}$ codes ${\psi,}$ then ${{\rm Free}(x)={\rm Free}(y).}$ I.e., if ${x=6{}^\frown2{}^\frown (y){}^\frown 3,}$ and ${y}$ is a formula, then ${{\rm Free}(x)={\rm Free}(y).}$
• If ${x}$ codes ${(\psi\rightarrow\rho)}$ and ${y,z}$ code ${\psi,\rho,}$ then ${{\rm Free}(x)={\rm Free}(y)\cup{\rm Free}(z).}$
• If ${x}$ codes ${\forall v_n\,\psi}$ and ${y}$ codes ${\psi,}$ then ${{\rm Free}(x)={\rm Free}(y)\setminus\{(0,n)\}.}$

In order to do this, we use a parsing witness ${f}$ for ${x.}$ One checks that, no matter what parsing witness is used, ${{\rm Free}(x)}$ is always computed the same way.

We can then define a formula describing satisfiability. This is a formula

$\displaystyle \Phi_{Sat}(a,b,c,d)$

which holds iff ${b}$ codes a formula in the language of set theory ${\phi(x_1,\dots,x_k,x)}$ (i.e., ${\in}$ is the only non-logical symbol in ${\phi}$, and the free variables of ${\phi}$ are exactly as shown), ${c=(t_1,\dots,t_k)}$ is a tuple of elements of ${a}$, ${d\in a}$ and, letting ${\psi(x)}$ be the formula resulting from substituting in ${\phi}$ each free occurrence of ${x_i}$ by ${c_{t_i},}$ ${i=1,\dots,k,}$ we have

$\displaystyle (a,\in)\models\psi(d).$

(We may also write ${(a,\in)\models\phi(t_1,\dots,t_k,d)}$ or even the admittedly ambguous ${(a,\in)\models \phi(c_{t_1},\dots,c_{t_k},d)}$ for ${(a,\in)\models\psi(d).}$)

This definition is by recursion on the complexity of ${\phi,}$ of course. More precisely, the definition refers to a parsing witness for ${b,}$ and implements the inductive clauses of Tarski’s definition of truth in models. As before, there ends up being no difference, no matter what parsing witness is used. I omit additional details, but it should be routine at this point to write down in detail both the formula ${{\rm Free}}$ and the formula ${\Phi_{Sat}.}$

The point of all this is that, now that we have a single formula ${\Phi_{Sat}}$ which captures the notion of satisfiability, then we can define ${{\rm D{}ef}(X),}$ by

$\displaystyle {\rm D{}ef}(X)=\{a\subseteq X\mid\exists b,c\,(a=\{d\in X\mid\Phi_{Sat}(X,b,c,d)\})\}.$

Note that now that we have a formula describing ${{\rm D{}ef},}$ it follows that “${x\in L}$” is also expressible by a formula, i.e., ${L}$ is indeed a class. Clearly, then, if ${A}$ is a set, then so is ${A\cap L,}$ as

$\displaystyle A\cap L=\{a\in A\mid a\in L\}$

and this is a set, by comprehension.

Remark 1 We have taken advantage in this section of the fact that in set theory, we can directly use functions. Gödel’s incompleteness theorem for Peano Arithmetic begins in very much the same form, by coding logic inside number theory. But Gödel has the additional problem that, in number theory, we do not have functions but only numbers, and so he first needs to device a way of coding finite sequences by numbers.

Once this is done, there is still the problem that there does not seem to be a reasonable way of coding arbitrary models by numbers, so instead Gödel works not with satisfiability but with provability. The possibility of using models directly is another advantage of working within set theory.

Remark 2 On the other hand, although we have a formula ${\Phi_{Sat}}$ that we can use to code all statements of the form ${X\models\psi}$ for ${X}$ a set and ${\psi}$ a formula, we do not have a formula ${\Phi_{Sat}^L}$ that holds of ${x}$ iff ${x}$ codes a formula that is true in ${L.}$ This is a somewhat subtle point related to both a theorem of Tarski usually called “undefinability of truth” and to Gödel’s incompleteness theorem.

Although I won’t prove this fact, informally, the issue is that expanding the definition of ${L\models\varphi}$ for a formula ${\varphi}$ with ${k}$ alternations of quantifiers requires itself ${k}$ alternations, so there is no formula that (provably in ${{\sf ZFC}}$) works for all ${\varphi.}$ And this is, ultimately, because ${L}$ is a proper class rather than a set.

2. Basic properties of ${L}$

In this section we present some basic properties of ${L}$ and of the constructible hierarchy ${(L_\alpha\mid\alpha\in{\sf ORD})}$ that we will require in the proof that ${L\models{\sf GCH}:}$ The basic facts listed in the theorem below, and the fact that ${L}$ is a model of ${{\sf ZFC}}$.

Theorem 1

1. For all ${\alpha\le\beta,}$ we have ${L_\alpha\subseteq L_\beta.}$
2. For all ${\alpha,}$ ${L_\alpha}$ is transitive. Therefore, ${L}$ is transitive.
3. For all ${\alpha,}$ ${L_\alpha\subseteq V_\alpha.}$ If ${\alpha\le\omega,}$ then ${L_\alpha=V_\alpha.}$ On the other hand, if ${\alpha}$ is infinite, ${|L_\alpha|=|\alpha|.}$
4. Whenever ${\alpha<\beta,}$ then ${\alpha,L_\alpha\in L_\beta.}$
5. For all ${\alpha,}$ ${L\cap\alpha=L_\alpha\cap{\sf ORD}=\alpha.}$ In particular, ${L}$ contains all the ordinals.

Proof: We begin by arguing simultaneously by induction that, for all ${\alpha,}$ ${L_\alpha}$ is transitive and ${L_\gamma\subseteq L_\alpha}$ for all ${\gamma<\alpha.}$

This is clear from the definition if ${\alpha}$ is ${0,}$ and from the definition and induction, if ${\alpha}$ is a limit ordinal. Suppose now the result for ${\alpha,}$ and argue for ${\alpha+1:}$ For this, note that (by induction) it suffices to show that ${L_\alpha\subseteq L_{\alpha+1}}$ and that ${L_{\alpha+1}}$ is transitive.

Let ${x\in L_\alpha.}$ Then ${x\subseteq L_\alpha,}$ since ${L_\alpha}$ is transitive. But then

$\displaystyle x=\{y\in L_\alpha\mid(L_\alpha,\in)\models y\in c_x\}\in {\rm D{}ef}(L_\alpha)=L_{\alpha+1}.$

This proves that ${L_\alpha\subseteq L_{\alpha+1}.}$

Now, if ${y\in x\in L_{\alpha+1},}$ then ${x\subseteq L_\alpha,}$ so ${y\in L_\alpha}$ and, therefore, ${y\in L_{\alpha+1}.}$ This shows that ${L_{\alpha+1}}$ is transitive.

Now we show that ${L_\alpha\subseteq V_\alpha}$ for all ${\alpha,}$ by induction. Again, this is immediate from the definitions if ${\alpha}$ is 0 or a limit ordinal. At successor ordinals, we have

$\displaystyle L_{\alpha+1}={\rm D{}ef}(L_\alpha)\subseteq{\mathcal P}(L_\alpha)\subseteq{\mathcal P}(V_\alpha)=V_{\alpha+1}.$

We argue by induction that ${L_n=V_n}$ if ${n<\omega.}$ This immediately gives as well that ${L_\omega=V_\omega.}$ Suppose, then, that ${L_n=V_n}$ (this clearly holds for ${n=0}$). Let ${x\in V_{n+1}.}$ Then ${x\subseteq V_n,}$ say

$\displaystyle x=\{a_1,\dots,a_k\},$

a finite set, since ${V_n}$ itself is finite. But then

$\displaystyle x=\{a\in L_n\mid (L_n,\in)\models a=c_{a_1}\lor\dots\lor a=c_{a_k}\}\in L_{n+1}.$

This shows that ${V_{n+1}\subseteq L_{n+1},}$ and we already have the other containment.

On the other hand, if ${|L_\alpha|\le|\alpha|}$ for ${\alpha}$ infinite, then

$\displaystyle |L_{\alpha+1}|\le|L_\alpha^{<\omega}||\omega|\le|\alpha|=|\alpha+1|,$

where the first equality follows from noting that each element of ${L_{\alpha+1}}$ is determined by a formula in the language of set theory (and there are only countably many of them) and a finite tuple of elements of ${L_\alpha.}$

At limit stages ${\lambda>\omega,}$ we have that

$\displaystyle |L_\lambda|=\left|\bigcup_{\omega\le\alpha<\lambda}L_\alpha\right|\le\sum_{\omega\le\alpha<\lambda}|\alpha|\le|\lambda|,$

where the sum indicates the size of a (possibly infinite) disjoint union.

We still need to check that ${|L_\alpha|=|\alpha|}$ for ${\alpha}$ infinite. This is a consequence of the next item, that ${\alpha,L_\alpha\in L_\beta}$ if ${\alpha<\beta.}$ This is because, in particular, it follows that ${\alpha\subseteq L_\alpha,}$ and then of course ${|\alpha|\le |L_\alpha|.}$

To prove the result, we only need to argue that ${\alpha,L_{\alpha}\in L_{\alpha+1}.}$ The rest follows by induction. But

$\displaystyle L_\alpha=\{x\in L_\alpha\mid L_\alpha\models x=x\}\in L_{\alpha+1}.$

By induction, we have ${\alpha\subseteq L_\alpha}$ and a further inductive argument (looking for the least counterexample) gives that, in fact, ${L_\alpha\cap{\sf ORD}=\alpha.}$ But then

$\displaystyle \alpha=\{x\in L_\alpha\mid L_\alpha\models x\mbox{\ is an ordinal}\}\in L_{\alpha+1}.$

That ${L\cap\alpha=\alpha}$ follows immediately, and this completes the proof. $\Box$

Before we prove that ${L\models{\sf ZFC}}$ we need a particular case of the reflection theorem:

Lemma 2 Suppose that ${\varphi(\vec x)}$ is a formula. Then there are arbitrarily large ordinals ${\alpha}$ such that

$\displaystyle L\models\varphi(\vec a)\Leftrightarrow L_\alpha\models\varphi(\vec a)$

for all tuples ${\vec a\in L_\alpha.}$

In the situation of the lemma, we say that ${\varphi(\cdot)}$ is reflected down from ${L}$ to ${L_\alpha}$.

Proof: This can be established by an argument very similar to the one we used in the notes on the Löwenheim-Sk\o lem theorem. Namely, for ${\varphi}$ and each of its subformulas ${\psi}$ consider Sk\o lem functions ${f_\psi}$ from ${L.}$ Let ${S}$ be the set of these Sk\o lem functions. Recall that if ${X}$ is closed under ${S,}$ then for any ${\vec b\in X}$ we have that ${X\models\varphi(\vec b)}$ iff ${L\models\varphi(\vec b).}$

Now, given any ${\alpha=\alpha_0,}$ we describe an iterative procedure: Let ${B_0}$ be the closure of ${L_\alpha}$ under ${S.}$ Let ${\alpha_1}$ be least such that ${L_{\alpha_1}\supseteq B_0.}$ In general, given ${L_{\alpha_n},}$ consider its closure ${B_n}$ under ${S,}$ and let ${\alpha_{n+1}}$ be least such that ${L_{\alpha_{n+1}}\supseteq B_n.}$ Now note that if ${\beta=\sup_n\alpha_n,}$ then

$\displaystyle L_\beta=\bigcup_n L_{\alpha_n}=\bigcup_n B_n$

is closed under ${S}$ and therefore ${\beta\ge\alpha}$ has the required property. Since ${\alpha}$ was arbitrary, we are done. $\Box$

We are now ready for the main result of this section:

Theorem 3 (Gödel) ${L\models{\sf ZFC}.}$

Proof: Extensionality: This follows from transitivity of ${L}$ and extensionality in ${V.}$

Pairing: If ${x,y\in L,}$ then they belong to some ${L_\alpha.}$ Then ${\{x,y\}\in L_{\alpha+1}.}$

Union: If ${x\in L,}$ let ${\alpha}$ be such that ${x\in L_\alpha,}$ Then ${\bigcup x\subseteq L_\alpha}$ is definable in ${L_\alpha.}$

Infinity: ${\omega\in L.}$

Foundation: This follows from transitivity of ${L}$ and foundation in ${V:}$ Given ${\emptyset\ne x\in L,}$ there is in ${V}$ a ${y\in x}$ with ${y\cap x=\emptyset.}$ Since ${L}$ is transitive, ${y\in L.}$

Power set: Given ${x\in L,}$ we can let

$\displaystyle A=\{\beta\mid\exists y\in L_{\beta+1}\setminus L_\beta\,(y\subseteq x)\}.$

Note that ${A}$ is a set, as it is the range of a function ${f:{\mathcal P}(x)\cap L\rightarrow{\sf ORD}.}$ Let ${\alpha=\sup(A)}$ and

$\displaystyle B=\{y\in L_{\alpha+1}\mid L_{\alpha+1}\models y\subseteq c_x\}.$

Then ${B\in L}$ and ${B={\mathcal P}(x)^L,}$ i.e.,

$\displaystyle L\models\forall y\,(y\subseteq x\leftrightarrow y\in B).$

Note there is no reason to suspect that ${B}$ is actually the true ${{\mathcal P}(x).}$

Comprehension: Let ${x\in L,}$ let ${\varphi(\vec y,z,v)}$ be a formula, and let ${\vec t}$ be a tuple of elements of ${L.}$ Write ${\vec c_t}$ for the tuple of constants ${c_i}$ for ${i}$ in ${\vec t.}$ Let

$\displaystyle y=\{a\in x\mid L\models\varphi(\vec t,x,a)\}.$

We need to show that ${y\in L.}$ It is here that Lemma 2 is useful: Pick ${\alpha}$ large enough so ${x,\vec t\in L_\alpha,}$ and for any ${a\in L_\alpha,}$

$\displaystyle L_\alpha\models c_a\in c_x\land\varphi(\vec c_t,c_x,c_a)$

iff

$\displaystyle L\models c_a\in c_x\land\varphi(\vec c_t,c_x,c_a).$

Then

$\displaystyle y=\{a\in L_\alpha\mid L_\alpha\models a\in c_x\land\varphi(\vec c_t,c_x,a)\}\in L_{\alpha+1}.$

Replacement: Let ${\varphi(x,y,\vec z)}$ be a formula and let ${\vec d}$ be a tuple of sets in ${L}$ such that

$\displaystyle L\models\forall x\,\exists! y\,\varphi(x,y,\vec d).$

Let ${a\in L.}$ We need to find a ${b\in L}$ such that

$\displaystyle L\models\forall x\in a\,\exists y\in b\,\varphi(x,y,\vec d),$

since replacement for ${\varphi}$ then follows by comprehension. Using replacement in ${V}$, let ${\alpha=\sup\{\gamma\mid\exists x\in a\,(}$ the unique ${y\in L}$ such that ${L\models\varphi(x,y,\vec d)}$ first appears in ${L_{\gamma})\}.}$ Then

$\displaystyle L\models\forall x\in a\,\exists y\in L_\alpha\,\varphi(x,y,\vec d),$

and we are done.

Choice: Note that since ${L}$ is a model of ${{\sf ZF},}$ the formalization of logic inside set theory can be carried out in ${L.}$ It then makes sense to talk, for any ${\alpha,}$ of ${L_\alpha^L,}$ i.e., the set that in ${L}$ satisfies the definition of ${L_\alpha.}$ One can easily verify by induction the following two claims:

1. For all ${\alpha,}$ ${L_\alpha^L=L_\alpha.}$
2. For all ${\alpha,}$ ${(L_\beta\mid\beta<\alpha)\in L.}$

To prove that choice holds in ${L,}$ begin by fixing some sufficiently definable enumeration ${(\varphi_n\mid n<\omega)}$ of all (codes for) formulas without constant symbols (so the enumeration is in ${L}$). Given ${x\in L,}$ let:

• ${\alpha_x}$ be the least ${\alpha}$ such that ${x\in L_{\alpha+1}.}$
• ${n_x}$ be the least natural ${n}$ such that ${x}$ is definable over ${L_{\alpha_x}}$ using ${\varphi_n}$ and some parameters.

We now define ${(<_\alpha\mid\alpha\in{\sf ORD})}$ with the properties that ${<_\alpha}$ is a well-ordering of ${L_\alpha}$ for all ${\alpha,}$ and the orders end-extend each other, i.e, ${<_{\alpha+1}\upharpoonright L_\alpha=<_\alpha}$ and if ${a\in L_{\alpha+1}\setminus L_\alpha}$ and ${b\in L_\alpha,}$ then ${b<_{\alpha+1}a.}$ The construction is carried out inside ${L.}$

Once this is done, we can then define a global well-ordering ${<_L}$ of all of ${L,}$ by setting, for ${x,y\in L,}$

$\displaystyle x<_L y$

iff either ${\alpha_x<\alpha_y,}$ or else ${\alpha_x=\alpha_y=\alpha,}$ say, and ${x<_{\alpha+1}y.}$

The definition of the orderings ${<_\alpha}$ is carried out by recursion in ${\alpha:}$ ${<_0=\emptyset,}$ and if ${\alpha}$ is limit, ${<_\alpha=\bigcup_{\beta<\alpha}<_\beta.}$ Finally, given ${(<_\beta\mid\beta\le\alpha),}$ we define ${<_{\alpha+1}}$ as follows: Given ${x,y\in L_{\alpha+1},}$ set

$\displaystyle x<_{\alpha+1}y$

iff

• Either ${\alpha_x<\alpha_y,}$ or else
• ${\alpha_x=\alpha_y}$ but ${n_x or
• ${\alpha_x=\alpha_y}$ and ${n_x=n_y,}$ but the tuple of parameters in ${L_{\alpha_x}}$ used to define ${x}$ by means of the formula ${\varphi_{n_x}}$ precedes the corresponding tuple for ${y,}$ in the lexicographic ordering of tuples induced by ${<_{\alpha_x}.}$

It is straightforward to check that the orderings so defined are indeed well-orderings, and we are done. $\Box$

Remark 3 One can organize the proof of Comprehension in ${L}$ somewhat more carefully, to avoid the appeal to the axiom of choice implicit in the use of Sk\o lem functions in the proof of Lemma 2. Note that the argument above can then be formalized in ${{\sf ZF},}$ since the proof that choice itself holds in ${L}$ does not use the axiom of choice in ${V.}$ This establishes Gödel’s result that, if ${{\sf ZF}}$ is consistent, then so is ${{\sf ZFC}.}$

3. The condensation lemma

In this section we sketch the fundamental condensation lemma, the last preliminary result needed in the proof of ${{\sf GCH}}$ in ${L.}$ The condensation lemma is in turn a consequence of the following basic result:

Lemma 4 (Mostowski collapsing lemma) If ${X}$ is a set and ${(X,\in)}$ satisfies the axiom of extensionality, then there is a unique transitive set ${M}$ and a unique map ${\pi:X\rightarrow M}$ that is an isomorphism between ${(X,\in)}$ and ${(M,\in).}$ Moreover, ${\pi}$ is the identity on any transitive subset of ${X.}$

Proof: Suppose that ${\pi:X\rightarrow M}$ is as wanted. Then, for any ${a,b\in X}$ with ${a\in b,}$ we have ${\pi(a)\in\pi(b).}$ Also, if ${c\in\pi(b)}$ then there must be some ${d}$ such that ${c=\pi(d),}$ and we have ${d\in b.}$ This means that

$\displaystyle \pi(b)=\{\pi(a)\mid a\in b\land a\in X\}.$

By induction on the rank of ${b,}$ it follows that there is a unique map ${\pi}$ defined by recursion by means of the equation above. Letting ${M}$ be the range of ${\pi,}$ it also follows that ${M}$ is unique.

By extensionality, it is routine to check that ${\pi}$ so defined is injective, and therefore a bijection between ${X}$ and ${M.}$ In effect, suppose ${x\in X}$ is of least rank such that there is some ${y\in X}$ distinct from ${x}$ and such that ${\pi(x)=\pi(y).}$

If there is some ${z\in x\setminus y}$ then, by definition of ${\pi,}$ we have ${\pi(z)\in\pi(x)=\pi(y),}$ so (by definition of ${\pi}$ again) we must have ${w\in y\cap X}$ with ${\pi(w)=\pi(z).}$ Since ${w\in y,}$ we have ${w\ne z.}$ But then ${z}$ contradicts the minimality of the rank of ${x.}$ A similar contradiction is obtained if ${z\in y\setminus x.}$

By definition of ${M}$ as the range of ${\pi,}$ we have that ${M}$ is indeed transitive. It remains to verify that ${\pi}$ is an ${\in}$-isomorphism. By definition, ${x\in y}$ for ${x,y\in X,}$ implies ${\pi(x)\in \pi(y).}$ Suppose now that ${x,y\in X}$ and ${\pi(x)\in\pi(y).}$ Since ${\pi}$ is injective, it follows that ${x\in y,}$ and we are done.

That ${\pi\upharpoonright Y}$ is the identity for any ${Y\subseteq X}$ that is already transitive is now immediate. $\Box$

${\pi}$ is usually called the collapsing map, and ${M}$ is the collapse of ${X.}$

The condensation lemma extends the above when ${X}$ is an elementary substructure of an initial segment of ${L,}$ by concluding that the transitive set ${M}$ it collapses to, is also an initial segment of ${L.}$

Theorem 5 (Condensation lemma) Suppose ${\alpha}$ is a limit ordinal, and ${X\preceq L_\alpha,}$ i.e., ${(X,\in)}$ is an elementary substructure of ${(L_\alpha,\in).}$ Then there is a unique ${\beta\le\alpha}$ and a unique map ${\pi}$ such that ${\pi:X\rightarrow L_\beta}$ is an isomorphism.

Proof: Begin by checking that ${L_\omega\subseteq X.}$ To do this, argue by induction on ${n}$ that ${L_n\subseteq X}$ for all ${n<\omega,}$ since every element of ${L_n}$ is definable. In particular, if ${\alpha=\omega}$ there is nothing to prove. Now suppose ${\alpha>\omega.}$

Note that ${L_\alpha}$ satisfies the axiom of extensionality, and therefore so does ${X.}$ The existence and uniqueness of ${\pi}$ now follows from Mostowski’s collapsing lemma. Let ${\pi:X\rightarrow M}$ be the collapsing map.

We want to show that ${M=L_\beta}$ for some ${\beta\le\alpha.}$ But this follows from checking that the construction of ${L}$ can be carried out inside ${L_\alpha,}$ with ${L_\alpha}$ being the output. Hence, ${L_\alpha\models V=L,}$ i.e., ${L_\alpha=\bigcup_{\beta<\alpha}L_\beta^{L_\alpha}.}$

Then ${M=\bigcup_{\beta\in{\sf ORD}^M}L_\beta^M,}$ and one checks that ${L_\beta^M=L_\beta}$ for all ${\beta\in{\sf ORD}^M.}$ It follows that ${M=L_{{\sf ORD}^M}.}$ Since each ordinal of ${M}$ is ${\pi(\gamma)}$ for some ordinal ${\gamma\in X,}$ it is clear that ${{\sf ORD}^M={\rm ot}({\sf ORD}\cap X)\le\alpha.}$ $\Box$

4. ${{\sf GCH}}$ holds in ${L}$

We conclude the course by showing:

Theorem 6 (Gödel) ${L\models{\sf GCH}.}$

Proof: We argue inside ${L}$ (or, if you wish, within the theory ${{\sf ZFC}+V=L}$). Let ${\kappa}$ be a cardinal, and let ${A}$ be a subset of ${\kappa.}$ There is some ${\alpha}$ such that ${A\in L_\alpha,}$ and it suffices to show that the least such ${\alpha}$ is strictly smaller than ${\kappa^+.}$ Because then ${{\mathcal P}(\kappa)\subseteq L_{\kappa^+},}$ and this set has size ${\kappa^+,}$ by Theorem 1.

To see this, let ${\alpha}$ be large enough and a limit ordinal, so that ${A\in L_\alpha.}$ Let ${X\preceq L_\alpha}$ be an elementary substructure of ${L_\alpha}$ of size ${\kappa}$ and such that ${\kappa\cup\{A\}\subseteq X.}$ Let ${L_\beta}$ be the transitive collapse of ${X,}$ and let ${\pi}$ be the collapsing map. Note that ${\pi(A)=A}$ as ${\pi(A)=\pi[A]}$ and ${\pi}$ is the identity on ${\kappa\supseteq A}$ since ${\kappa}$ is transitive and ${\kappa\subseteq X.}$ Since ${X}$ has size ${\kappa,}$ so does ${L_\beta,}$ so ${\beta}$ has size ${\kappa.}$ Since ${A\in L_\beta,}$ we are done. $\Box$

We have thus established that, if ${{\sf ZF}}$ is consistent, then so is ${{\sf ZFC}+{\sf GCH}.}$ In particular, this shows that one cannot refute ${{\sf CH}}$ in ${{\sf ZFC}.}$ On the other hand, in 1963, Paul Cohen devised a very powerful method, known as forcing that, in particular, can be used to show that if ${{\sf ZF}}$ is consistent, then so are ${{\sf ZF}+\lnot{\sf AC}}$ and ${{\sf ZFC}+\lnot{\sf CH}.}$ This provides a concrete example of a natural mathematical statement (namely, ${{\sf CH}}$) verifying the incompleteness theorem for set theory.

Typeset using LaTeX2WP. Here is a printable version of this post.

### 2 Responses to 502 – The constructible universe

1. [Edited Dec. 11]

Here I sketch two suggestions for how to avoid appealing to Choice in the proof of the reflection argument:

1. Prove choice in $L$ first. This require a bit of care, checking that (without appealing to replacement or comprehension) inside $L$ we can organize the proof I presented here. Once this is done, we can define in $L$ the Skølem functions we need for the reflection argument. This is fine but it is technically somewhat demanding.

Or we could do as follows, which is easier and feels like the natural approach:

2. Check that one can prove the reflection theorem without appealing to choice. Previously, given a structure $M$ and a formula $\varphi(x,y),$ we defined the Skølem function $f_\varphi$ by saying that $f_\varphi(x)$ is the least $y\in M$ such that $\varphi(x,y)$ holds in $M,$ if there is some such $y,$ and as a previously fixed element of $M$ otherwise. (Where “least” is with respect to a fixed well-ordering of $M.$) In $L,$ we can eliminate the use of choice by being somewhat less careful: Now let $F_\varphi(x)$ be the set of $y\in L_\alpha$ such that $\varphi(x,y)$ holds in $L,$ where $\alpha$ is least such that, if there is some $y$ such that $L\models \varphi(x,y),$ then there is some such $y$ in $L_\alpha.$ The difference is that rather than picking a single witness $y,$ we are now potentially picking a very large set of witnesses. Of course, if $X$ is closed under $F_\varphi,$ then if $x\in X$ and $L\models \exists y\,\varphi(x,y),$ then there is a $y\in X$ such that $L\models \varphi(x,y).$ With this definition, we can now proceed as before.

The (new) notion of being closed is the natural one: $X$ is closed under $F_\varphi$ iff for any $x\in X$ we have $F_\varphi(x)\subseteq X.$

2. Dan says:

[Comment migrated to the other site.]