502 – The constructible universe

December 9, 2009

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.

Read the rest of this entry »

580 -Cardinal arithmetic (9)

March 7, 2009

2. The ultrapower construction

The study of ultrapowers originates in model theory, although it has found applications both in algebra and in analysis. However, it is accurate to say that it is mainly exploited in set theory. Here I present the basic idea, showing its close connection to the study of measurable cardinals, defined last lecture.

Suppose first that {{\mathcal U}} is an ultrafilter over a set {X.} We want to define the ultrapower of the universe {V} of sets by {{\mathcal U}.} The basic idea is to consider the product of {X} many copies of the structure {(V,\in).} We want to “amalgamate” them somehow into a new structure {(\tilde V,\tilde\in).} For this, we look for the “typical” properties of the elements {\{f(x): x\in X\}} of each “thread” {f:X\rightarrow V,} and add an element {\tilde f} to {\tilde V} whose properties in {(\tilde V,\tilde\in)} are precisely these typical properties. We use {{\mathcal U}} to make this precise, by saying that a property {\varphi} is typical of the range of {f} iff {\{x\in X:\varphi(f(x))\}\in{\mathcal U}.} This leads us to the following definition, due to Dana Scott, that adapts the ultrapower construction to the context of proper classes:

Definition 1 Let {{\mathcal U}} be an ultrafilter over a nonempty set {X.} We define the ultrapower {(V^X/{\mathcal U},\hat\in)} of {V} by {{\mathcal U}} as follows:

For {f,g:X\rightarrow V,} say that

\displaystyle f=_{\mathcal U} g \mbox{ iff } \{x \in X: f(x)=g(x)\} \in{\mathcal U}.

This is easily seen to be an equivalence relation. We would like to make the elements of {V^X/{\mathcal U}} to be the equivalence classes of this relation. Unfortunately, these are all proper classes except for the trivial case when {X} is a singleton, so we cannot within the context of our formal theory form the collection of all equivalence classes.

Scott’s trick solves this problem by replacing the class of {f} with

\displaystyle [f]:= \{g : X\rightarrow V : g=_{\mathcal U}f \mbox{ and } {\rm rk}(g)\mbox{ is least possible}\}.

Here, as usual, {{\rm rk}(g) = {\rm min}\{\alpha : g\in V_{\alpha+1}\} = \sup\{ {\rm rk}(x) +1 : x\in g\}.} All the “classes” {[f]} are now sets, and we set {V^X/{\mathcal U} = \{[f] :  f:X\rightarrow V\}.}

We define {\hat\in} by saying that for {f,g:X\rightarrow V} we have

\displaystyle [f]\hat\in[g] \mbox{ iff } \{x \in X : f(x)\in g(x)\} \in {\mathcal U}.

(It is easy to see that {\hat\in} is indeed well defined, i.e., if {f=_{\mathcal U}f'} and {g=_{\mathcal U}g'} then {\{x\in X : f(x)\in g(x)\} \in {\mathcal U}} iff {\{x\in X : f'(x)\in g'(x)\} \in {\mathcal U}.})

(The ultrapower construction is more general than as just defined; what I have presented is the particular case of interest to us.) The remarkable observation, due to \mbox{\L o\'s,} is that this definition indeed captures the typical properties of each thread in the sense described above:

Read the rest of this entry »