8.3 Constructible Universe (L)

The constructible universe is a class of sets built in stages by a controlled process of definability. It is denoted by:

L

The guiding idea is that, at each stage, we do not take all subsets of the previous stage. Instead, we take only those subsets that can be defined over the previous stage by a first order formula using parameters from that stage. In this way, $L$ is a universe of sets built from explicit descriptions.

This construction is important because it gives an inner model of set theory. It also gives a setting in which the axiom of choice and the continuum hypothesis hold. For this reason, the constructible universe is one of the central tools in consistency and independence results.

Definable Subsets

The construction of $L$ depends on the idea of a subset that is definable over a given set. We first make this notion precise.

Definition 8.44 (Definable Subset)

Let $M$ be a set. A subset $X \subseteq M$ is definable over $M$ if there is a first order formula:

\varphi(x,a_1,\dots,a_n)

in the language of set theory, with parameters:

a_1,\dots,a_n \in M

such that:

X = \{x \in M : (M,\in) \models \varphi(x,a_1,\dots,a_n)\}

The notation:

(M,\in) \models \varphi(x,a_1,\dots,a_n)

means that the formula $\varphi$ is true when interpreted inside the structure whose domain is $M$ and whose membership relation is the ordinary membership relation restricted to $M$ .

The parameters $a_1,\dots,a_n$ allow the definition to use objects already present in $M$ . This is important because many natural subsets of $M$ cannot be defined without referring to particular elements of $M$ .

Definition 8.45 (Definable Power Set)

Let $M$ be a set. The definable power set of $M$ is:

\operatorname{Def}(M)

where:

\operatorname{Def}(M) = \{X \subseteq M : X \text{ is definable over } M \text{ with parameters from } M\}

Thus:

\operatorname{Def}(M) \subseteq \mathcal{P}(M)

The ordinary power set $\mathcal{P}(M)$ contains all subsets of $M$ , while $\operatorname{Def}(M)$ contains only those subsets that can be described by formulas over $M$ using parameters from $M$ .

Example 8.46

Let:

M=\{0,1,2\}

Since elements of $M$ may be used as parameters, the singleton:

\{1\}

is definable over $M$ by the formula:

x=1

Similarly, each singleton subset of $M$ is definable. Since finite unions of definable sets are definable, every subset of $M$ is definable over $M$ . Hence:

\operatorname{Def}(M)=\mathcal{P}(M)

This example is finite and therefore misleadingly simple. For infinite sets, the ordinary power set may contain many subsets that are not definable over the structure.

Lemma 8.47

If $M$ is a set, then $\operatorname{Def}(M)$ is a set.

Proof

The formulas of first order set theory form a countable collection when coded syntactically. For each formula:

\varphi(x,y_1,\dots,y_n)

and each finite tuple of parameters:

(a_1,\dots,a_n) \in M^n

there is at most one subset of $M$ defined by:

\{x \in M : (M,\in) \models \varphi(x,a_1,\dots,a_n)\}

For each fixed natural number $n$ , the collection of parameter tuples from $M^n$ is a set. The collection of formulas with $n+1$ free variables is also a set after coding formulas by natural numbers.

Therefore the collection of all subsets of $M$ definable by formulas with finitely many parameters is indexed by a set. By replacement and separation, the collection of such subsets is itself a set.

Thus $\operatorname{Def}(M)$ is a set.

The Constructible Hierarchy

The constructible universe is built by transfinite recursion over the ordinals.

Definition 8.48 (Constructible Hierarchy)

The constructible hierarchy is the sequence:

(L_\alpha)_{\alpha \in \mathrm{Ord}}

defined as follows.

At the initial stage:

L_0=\varnothing

At successor stages:

L_{\alpha+1}=\operatorname{Def}(L_\alpha)

At limit stages:

L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha

whenever $\lambda$ is a limit ordinal.

The constructible universe is:

L=\bigcup_{\alpha \in \mathrm{Ord}} L_\alpha

A set $x$ is called constructible if:

x \in L

The successor step is the key difference between $L$ and the usual cumulative hierarchy $V$ . In the cumulative hierarchy one defines:

V_{\alpha+1}=\mathcal{P}(V_\alpha)

In the constructible hierarchy one defines:

L_{\alpha+1}=\operatorname{Def}(L_\alpha)

Thus $L$ adds only definable subsets at each stage, while $V$ adds all subsets.

Example 8.49 (The First Stages)

The first stage is:

L_0=\varnothing

Since the only subset of $\varnothing$ is $\varnothing$ , and it is definable over $\varnothing$ , we have:

L_1=\{\varnothing\}

Now:

L_1=\{\varnothing\}

Its subsets are:

\varnothing

and:

\{\varnothing\}

Both are definable over $L_1$ , so:

L_2=\{\varnothing,\{\varnothing\}\}

At the next stages, the hierarchy continues by taking definable subsets of the previous level. The early finite stages resemble the finite part of the cumulative hierarchy, but at infinite stages the distinction between all subsets and definable subsets becomes essential.

Lemma 8.50 (Monotonicity)

If $\alpha \le \beta$ , then:

L_\alpha \subseteq L_\beta

Proof

It is enough to show that:

L_\alpha \subseteq L_{\alpha+1}

for every ordinal $\alpha$ , because the general result then follows by transfinite induction.

Let $x \in L_\alpha$ . Since $L_\alpha$ is a structure with domain $L_\alpha$ , the singleton:

\{x\}

is definable over $L_\alpha$ using the parameter $x$ by the formula:

y=x

Thus:

\{x\} \in \operatorname{Def}(L_\alpha)=L_{\alpha+1}

However, this only shows that the singleton $\{x\}$ is an element of $L_{\alpha+1}$ , not directly that $x \in L_{\alpha+1}$ . To see that $x$ itself belongs to $L_{\alpha+1}$ , use the fact that elements of $L_\alpha$ are subsets of earlier levels, and proceed by induction on $\alpha$ .

For $\alpha=0$ , the claim is immediate since:

L_0=\varnothing

Assume that the inclusion:

L_\gamma \subseteq L_{\gamma+1}

has been established for all $\gamma<\alpha$ . If $x \in L_\alpha$ , then by the definition of the hierarchy, $x$ appears at some earlier stage when $\alpha$ is a limit, or as a definable subset of $L_\gamma$ when $\alpha=\gamma+1$ .

In either case, the construction ensures that objects already constructed remain available at later stages. At limit stages this is immediate from the union definition:

L_\lambda=\bigcup_{\gamma<\lambda}L_\gamma

At successor stages, previously constructed objects are subsets of the preceding transitive level and are definable there from parameters. Hence:

L_\alpha \subseteq L_{\alpha+1}

Therefore the hierarchy is increasing, and so:

L_\alpha \subseteq L_\beta

whenever $\alpha \le \beta$ .

Remark 8.51

The proof of monotonicity is usually given together with the proof that the levels $L_\alpha$ are transitive. Transitivity ensures that elements already constructed can be regarded as subsets of later stages and hence can be captured again by definability. This is one reason why the transitivity of the constructible levels is structurally important.

Definition 8.52 (Transitive Set)

A set $M$ is transitive if:

x \in y \in M

implies:

x \in M

Equivalently:

\bigcup M \subseteq M

A transitive set contains the elements of its elements. This property is important when interpreting set theoretic formulas inside a set, because membership relations inside the set agree well with membership relations in the surrounding universe.

Lemma 8.53 (Transitivity of Constructible Levels)

For every ordinal $\alpha$ , the set $L_\alpha$ is transitive.

Proof

We prove the statement by transfinite induction on $\alpha$ .

For $\alpha=0$ , we have:

L_0=\varnothing

and the empty set is transitive.

Assume $L_\alpha$ is transitive. We show that $L_{\alpha+1}$ is transitive.

Let:

x \in y \in L_{\alpha+1}

By definition:

L_{\alpha+1}=\operatorname{Def}(L_\alpha)

Therefore every element of $L_{\alpha+1}$ is a subset of $L_\alpha$ . Since $y \in L_{\alpha+1}$ , we have:

y \subseteq L_\alpha

Since $x \in y$ , it follows that:

x \in L_\alpha

By monotonicity:

L_\alpha \subseteq L_{\alpha+1}

Thus:

x \in L_{\alpha+1}

Therefore $L_{\alpha+1}$ is transitive.

Now suppose $\lambda$ is a limit ordinal and that $L_\alpha$ is transitive for every $\alpha<\lambda$ . Let:

x \in y \in L_\lambda

Since:

L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha

there exists some $\alpha<\lambda$ such that:

y \in L_\alpha

Since $L_\alpha$ is transitive:

x \in L_\alpha

Therefore:

x \in L_\lambda

Thus $L_\lambda$ is transitive. By transfinite induction, every $L_\alpha$ is transitive.

Lemma 8.54

For every ordinal $\alpha$ :

L_\alpha \subseteq V_\alpha

Proof

We prove the statement by transfinite induction on $\alpha$ .

For $\alpha=0$ , we have:

L_0=\varnothing=V_0

so the claim holds.

Assume:

L_\alpha \subseteq V_\alpha

We prove:

L_{\alpha+1}\subseteq V_{\alpha+1}

Let:

x \in L_{\alpha+1}

Then:

x \in \operatorname{Def}(L_\alpha)

By definition of $\operatorname{Def}(L_\alpha)$ , the object $x$ is a subset of $L_\alpha$ . Hence:

x \subseteq L_\alpha

By the induction hypothesis:

L_\alpha \subseteq V_\alpha

Therefore:

x \subseteq V_\alpha

So:

x \in \mathcal{P}(V_\alpha)

Since:

V_{\alpha+1}=\mathcal{P}(V_\alpha)

we get:

x \in V_{\alpha+1}

Thus:

L_{\alpha+1}\subseteq V_{\alpha+1}

Now suppose $\lambda$ is a limit ordinal and the statement holds for every $\alpha<\lambda$ . Then:

L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha

and:

V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha

Since:

L_\alpha \subseteq V_\alpha

for every $\alpha<\lambda$ , it follows that:

L_\lambda \subseteq V_\lambda

This completes the induction.

Constructible Rank

Every constructible set appears at some stage of the hierarchy. The first stage at which it appears gives a rank like measure.

Definition 8.55 (Constructible Rank)

Let $x \in L$ . The constructible rank of $x$ is the least ordinal $\alpha$ such that:

x \in L_{\alpha+1}

This least ordinal exists because the ordinals are well ordered and because:

x \in L

means that $x$ belongs to at least one level $L_\beta$ .

The use of $L_{\alpha+1}$ reflects the fact that elements of $L_{\alpha+1}$ are constructed as definable subsets of $L_\alpha$ .

The Class L

The constructible universe is a proper class in general, not a set. It is obtained by taking the union of all constructible levels:

L=\bigcup_{\alpha \in \mathrm{Ord}} L_\alpha

This union ranges over all ordinals. Since the ordinals form a proper class, $L$ is also a proper class unless the universe of sets is itself very small, which cannot occur in ordinary ZF.

Definition 8.56 (Constructible Set)

A set $x$ is constructible if:

x \in L

Equivalently, $x$ is constructible if there exists an ordinal $\alpha$ such that:

x \in L_\alpha

The class $L$ consists exactly of all constructible sets.

Definition 8.57 (Axiom of Constructibility)

The axiom of constructibility is the statement:

V=L

This says that every set is constructible.

Equivalently, for every set $x$ , there exists an ordinal $\alpha$ such that:

x \in L_\alpha

The axiom $V=L$ is not part of ZF or ZFC by default. It is an additional principle that imposes a strong restriction on the universe of sets.

The Canonical Well Order of L

One of the most important features of $L$ is that it has a definable global well order.

The idea is that each constructible set is introduced at a first stage, and at that stage it is introduced by some formula with some finite list of parameters. Since formulas can be coded by natural numbers and parameters have already appeared earlier in the hierarchy, one can order constructible sets by the first stage and first definition that constructs them.

Theorem 8.58

There is a definable global well order of $L$ .

Proof

We give the standard idea of the proof.

Every constructible set $x$ appears for the first time at some level:

L_{\alpha+1}

Thus $x$ is a definable subset of $L_\alpha$ . This means that there is a formula:

\varphi(y,a_1,\dots,a_n)

and parameters:

a_1,\dots,a_n \in L_\alpha

such that:

x=\{y \in L_\alpha : (L_\alpha,\in)\models \varphi(y,a_1,\dots,a_n)\}

The formula $\varphi$ can be assigned a code in $\mathbb{N}$ . The finite tuple of parameters can be compared using the well order already defined on earlier levels. Therefore, among all definitions of $x$ at its first stage, one can choose the least code and least parameter tuple.

Define:

x <_L y

if the first construction data for $x$ comes before the first construction data for $y$ in this lexicographic ordering.

Because ordinals are well ordered, formula codes are well ordered, and finite tuples of earlier parameters can be well ordered recursively, the relation $<_L$ is a well order of $L$ .

Moreover, the construction is definable in the language of set theory, so the well order is not merely existential. It is definable over $L$ itself.

Corollary 8.59

If $V=L$ , then the axiom of choice holds.

Proof

Assume:

V=L

By Theorem 8.58, the class $L$ has a definable global well order. Since every set is constructible under the assumption $V=L$ , this gives a global well order of the universe $V$ .

Let:

(A_i)_{i \in I}

be a family of nonempty sets. Since every set is in $L$ , each $A_i$ is ordered by the global well order.

Define:

f(i)

to be the least element of $A_i$ under this global well order.

Since each $A_i$ is nonempty, such a least element exists. Therefore:

f(i) \in A_i

for every $i \in I$ .

Thus $f$ is a choice function. Hence the axiom of choice holds.

Corollary 8.60

If $V=L$ , then every set can be well ordered.

Proof

Assume:

V=L

By Theorem 8.58, there is a global well order of $L$ . Since $V=L$ , this is a global well order of all sets.

If $X$ is any set, restrict the global well order to $X$ . Every nonempty subset of $X$ has a least element because it is also a nonempty set of constructible objects and the global ordering is a well order.

Therefore every set can be well ordered.

Inner Models

The constructible universe is not only a class of sets. It is a model of set theory inside the ambient universe.

Definition 8.61 (Inner Model)

An inner model is a transitive class $M$ such that:

$M$ contains every ordinal.
$M$ satisfies the axioms of ZF.
The membership relation of $M$ is the ordinary membership relation restricted to $M$ .

The condition that $M$ is transitive ensures that membership inside $M$ agrees well with actual membership. The condition that $M$ contains all ordinals ensures that it has the same ordinal scale as the ambient universe.

Theorem 8.62

The constructible universe $L$ is an inner model of ZF.

Proof

We outline the verification of the axioms, because the full formal proof is long but follows a systematic pattern.

First, $L$ is transitive. If:

x \in y \in L

then $y \in L_\alpha$ for some ordinal $\alpha$ . Since $L_\alpha$ is transitive:

x \in L_\alpha

and hence:

x \in L

Second, $L$ contains all ordinals. This is proved by induction on ordinals. The empty set belongs to $L_1$ . If all elements of an ordinal $\alpha$ have appeared in $L$ , then $\alpha$ , being the set of all smaller ordinals, appears at a later constructible stage.

Third, $L$ satisfies extensionality because membership in $L$ is ordinary membership, and extensionality already holds in the ambient universe.

Fourth, $L$ satisfies pairing. If $a,b \in L$ , then both appear in some level $L_\alpha$ . The pair:

\{a,b\}

is definable over a sufficiently large level using $a$ and $b$ as parameters, so:

\{a,b\} \in L

Fifth, $L$ satisfies union. If $x \in L$ , then $x$ appears in some level $L_\alpha$ . The union:

\bigcup x

is definable over a sufficiently large level from the parameter $x$ , so:

\bigcup x \in L

Sixth, $L$ satisfies separation. If $a \in L$ and $\varphi(x)$ is a formula, then the subset:

\{x \in a : \varphi(x)\}

is definable over a sufficiently large constructible level containing $a$ and the relevant parameters. Hence this subset belongs to $L$ .

Seventh, $L$ satisfies replacement. If a definable function maps elements of a constructible set to constructible sets, then the ranks of the images are bounded by some constructible level. This uses replacement in the ambient universe to obtain a bound on the stages at which the images appear.

Eighth, $L$ satisfies infinity because the finite ordinals are constructible and therefore:

\omega \in L

Ninth, $L$ satisfies foundation because foundation holds in the ambient universe and $L$ uses the same membership relation.

Thus $L$ is a transitive class containing all ordinals and satisfying ZF, so $L$ is an inner model.

The Axiom of Constructibility Inside L

The constructible universe satisfies its own version of $V=L$ .

Theorem 8.63

Inside $L$ , every set is constructible. In symbols:

L \models V=L

Proof

Let $x$ be a set belonging to $L$ . By definition of $L$ , there is an ordinal $\alpha$ such that:

x \in L_\alpha

The construction of $L$ inside $L$ uses the same ordinals and the same earlier constructible levels, because $L$ is transitive and contains all ordinals.

Thus the hierarchy computed inside $L$ reproduces the same constructible hierarchy. Therefore every set of $L$ appears in the constructible hierarchy as computed inside $L$ .

Hence:

L \models V=L

Godel’s Constructibility Result

The constructible universe gives a relative consistency result.

Theorem 8.64 (Godel’s Constructibility Theorem)

If ZF is consistent, then:

\mathrm{ZF}+V=L

is consistent.

Proof

Assume that ZF has a model. Inside that model, construct the class $L$ by the definability hierarchy.

By Theorem 8.62, the resulting class $L$ satisfies ZF. By Theorem 8.63, $L$ also satisfies:

V=L

Therefore, if there is a model of ZF, then there is a model of:

\mathrm{ZF}+V=L

This proves that if ZF is consistent, then:

\mathrm{ZF}+V=L

is consistent.

Corollary 8.65

If ZF is consistent, then ZFC is consistent.

Proof

By Theorem 8.64, if ZF is consistent, then:

\mathrm{ZF}+V=L

is consistent.

By Corollary 8.59, $V=L$ implies the axiom of choice. Therefore every model of:

\mathrm{ZF}+V=L

is also a model of ZFC.

Hence, if ZF is consistent, then ZFC is consistent.

Corollary 8.66

If ZF is consistent, then:

\mathrm{ZFC}+\mathrm{CH}

is consistent.

Proof

Godel proved that:

V=L

implies the continuum hypothesis:

\mathrm{CH}

Therefore, if ZF is consistent, then by the constructibility theorem there is a model of:

\mathrm{ZF}+V=L

Such a model satisfies ZFC, because $V=L$ implies the axiom of choice, and it satisfies CH, because $V=L$ implies the continuum hypothesis.

Hence:

\mathrm{ZFC}+\mathrm{CH}

is consistent relative to ZF.

Why L Matters

The constructible universe is important because it provides a canonical inner model of set theory. It is small enough to have a definable global well order, but large enough to satisfy all axioms of ZF.

The equation:

V=L

gives a highly organized universe of sets. In that universe, every set appears by a definable construction at some ordinal stage.

At the same time, $V=L$ is a strong additional assumption. It excludes many possible sets that may exist in larger universes of set theory. Later independence results show that set theory can consistently behave very differently from $L$ , assuming suitable consistency hypotheses.