The constructible universe is traditionally denoted L. L is a subclass of V and is a proper class. Gödel proved three things about L:
- All the axioms of ZF hold in L, i.e., L is a model of ZF.
- V=L holds in L, i.e., L is a model of the axiom “All sets are constructible”. Cohen: “This is a small but subtle point. It says that a constructible set is constructible when the whole construction is relativized to L.”
- V=L→AC and V=L→GCH are both provable in ZF.
So we can’t prove not-GCH in ZF. If we could, it would have to hold in L, but GCH holds in L. Ditto for AC.
L is constructed according to the familiar transfinite scheme, using a function ℱ (discussed below):
| L0 | = ∅ |
| Lα+1 | = ℱ(Lα) |
| Lλ | = ⋃α<λLα |
| L | = ⋃α∈Ω Lα |
Let A be a set. ℱ(A) is a subset of 𝒫(A); it’s the set of all sets that are definable using elements of A.
Here’s the precise definition. For any set A, x⊆A is definable over A if there is a first-order formula φ(y,ū) and elements ā∈A such that
z∈x ↔ z∈A ∧ φA(z,ā)
where φA is φ relativized to A, i.e., all quantifiers in φ range only over A. (Logic Notes §5 treats relativisation.) As we said before, ℱ(A) is the set of all subsets of A that are definable over A.
So ℱ(A) is something like 𝒫(A), except we include only those sets where we can explicitly describe their criterion for membership. Cohen discusses how this notion arose from, but did not resolve, concerns about so-called impredicative definitions. (We talked about this in post 3 on the paradoxes, and in post 5 on Zermelo’s proof of the well-ordering theorem.)
Some examples. The singleton {x}, the unordered pair {x,y}, the ordered pair 〈x,y〉={{x},{x,y}}, and the power set 𝒫(x) are all definable from x or from x and y:
| z∈{x} | ↔ z=x |
| z∈{x,y} | ↔ z=x ∨ z=y |
| z∈〈x,y〉 | ↔ z={x} ∨ z={x,y} |
| z∈𝒫(x) | ↔ ∀u[u∈z → u∈x] |
Each right-hand side is a first-order formula characterizing the elements of a set. As usual, imagine the vernacular expanded. For example, instead of z={x}, we have ∀t(t∈z↔t=x). The left-hand sides are abbreviations for the right-hand sides, so (for example) in the formal definition of 〈x,y〉, “z={x}’’ and “z={x,y}’’ have been expanded.
The prime examples of sets not obviously definable are choice functions. For example, it’s easy to say what we desire of a choice function c for 𝒫(ℝ), where ℝ=𝒫(ω):
(∀s⊆ℝ) (s≠∅→c(s)∈s)
But this doesn’t characterize c. (We’ve already seen how to express formally “c is a function with domain 𝒫(ℝ)∖{∅}’’, and “c(s)∈s’’.)
Gödel’s L is an example of an inner model. The method of inner models proves relative consistency results: If a theory 𝒯 is consistent, then so is 𝒯+φ, where φ is a formula φ in ℒ(𝒯). To apply this method, you have find a formula α(x) in ℒ(𝒯), and show two things:
| for all ψ∈𝒯, | 𝒯⊢ψα |
| and also | 𝒯⊢φα |
where ψα is ψ relativized to α.
You can approach this method syntactically or semantically. First, semantics: Let’s say T is a model for 𝒯. Consider the substructure selected by α(x), call it A. It’s a model of 𝒯+φ, because each formula ψ∈𝒯, when interpreted as speaking about A, is equivalent to ψα interpreted in T:
A⊧ψ if and only if T⊧ψα
Likewise for φ. We’ve found a model of 𝒯+φ sitting inside a model of 𝒯.
Syntactically, say we had a proof of a contradiction in 𝒯+φ. Go through and relativize everything with α. Now we have a proof of a contradiction in 𝒯: all the relativized axioms of 𝒯+φ can be proved in 𝒯, and it turns out that relativization preserves the logical axioms and rules of inference. (Picky point: we need ∃xα(x) to hold too.)
Gödel’s treatment emphasized the syntactic aspect, Cohen’s the semantic.
Of course the hard part is proving the relativizations:
| for all ψ∈ZF, | ZF⊢ψL |
| and also | ZF⊢(V=L)L |
So Con(ZF) → Con(ZF+V=L). People write ZFL for ZF+V=L, “All sets are constructible.” Gödel also showed that ZFL⊢AC and ZFL⊢GCH, giving relative consistency for these too.
Here’s a trivial example of the method of inner models. Let Group be the first-order theory of groups, and let abelian be the axiom x·y=y·x. Any model of Group (i.e., any group) has a model of Group+abelian sitting inside of it, namely its center. The formula
ζ(x) ↔∀y[x·y=y·x]
selects the center of the group. (Picky point: we can’t let the ∀y be implicit, since we need ζ(x) to define a unary relation.) Within Group, we can prove that the center of a group is an abelian group. It’s not totally trivial that the center of a group is even a group, i.e., that it’s closed under the group operation. Anyway, this argument shows the relative consistency result
Con(Group)→Con(Group+abelian)
admittedly a trivial result, but it illustrates the method.
Before Gödel’s L, the most prominent example of this method was von Neumann’s class of well-founded sets: V=⋃α∈ΩVα. This shows that if ZF minus Foundation is consistent, then ZF is too. The demonstration amounts to a much easier “dry run” for Gödel’s results.
Finally, let’s note an important feature of the inclusion L⊆V. Is it a proper inclusion, i.e., are there any non-constructible sets? Gödel thought so. So do most set-theorists who believe the question has meaning. For a formalist, the only question that has meaning is, what can you prove? Well, if we did have ZF⊢V≠L, that would mean that ZFL was inconsistent. By Gödel’s relative consistency result, that can happen only if ZF itself is inconsistent!
Cohen showed that ZF+V≠L is also consistent (if ZF is), so just like AC and GCH, whether V=L cannot be settled by the axioms of ZF. For a formalist, that’s the end of the story. For a platonist—some one who believes that the universe of set theory “really exists”—the question still has meaning. (Your platonism has to be at least moderately strong: you could believe that a multiverse of sets “really exists”, with V=L true in some universes and not in others.)
For what it’s worth, the consensus among set theorists of the platonist persuasion seems to be that AC is true, GCH is false, and V=L is also false.
Diagonal Argument 