Luminy – Hugh Woodin: Ultimate L (I)

October 19, 2010

The XI International Workshop on Set Theory took place October 4-8, 2010. It was hosted by the CIRM, in Luminy, France. I am very glad I was invited, since it was a great experience: The Workshop has a tradition of excellence, and this time was no exception, with several very nice talks. I had the chance to give a talk (available here) and to interact with the other participants. There were two mini-courses, one by Ben Miller and one by Hugh Woodin. Ben has made the slides of his series available at his website.

What follows are my notes on Hugh’s talks. Needless to say, any mistakes are mine. Hugh’s talks took place on October 6, 7, and 8. Though the title of his mini-course was “Long extenders, iteration hypotheses, and ultimate L”, I think that “Ultimate L” reflects most closely the content. The talks were based on a tiny portion of a manuscript Hugh has been writing during the last few years, originally titled “Suitable extender sequences” and more recently, “Suitable extender models” which, unfortunately, is not currently publicly available.

The general theme is that appropriate extender models for supercompactness should provably be an ultimate version of the constructible universe L. The results discussed during the talks aim at supporting this idea.

Read the rest of this entry »

8 Comments | Luminy | Tagged: , , , , , , , | Permalink
Posted by andrescaicedo

502 – Notes on compactness

October 1, 2009

The goal of this note is to present a proof of the following fundamental result. A theory {T} is said to be satisfiable iff there is a model of {T.}

Theorem 1 (Compactness) Let {T} be a first order theory. Suppose that any finite subtheory {T_0\subseteq T} is satisfiable. Then {T} itself is satisfiable.

 

As indicated on the set of notes on the completeness theorem, compactness is an immediate consequence of completeness. Here I want to explain a purely semantic proof, that does not rely on the notion of proof.

The argument I present uses the notion of ultraproducts. Although their origin is in model theory, ultraproducts have become an essential tool in modern set theory, so it seems a good idea to present them here. We will require the axiom of choice, in the form of Zorn’s lemma.

The notion of ultraproduct is a bit difficult to absorb the first time one encounters it. I recommend working out through some examples in order to understand it well. Here I confine myself to the minimum necessary to make sense of the argument.

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: , , , , | Permalink
Posted by andrescaicedo

580 -Cardinal arithmetic (11)

March 12, 2009

4. Strongly compact cardinals and {{\sf SCH}}

 

Definition 1 A cardinal {\kappa} is strongly compact iff it is uncountable, and any {\kappa}-complete filter (over any set {I}) can be extended to a {\kappa}-complete ultrafilter over {I.}

 

The notion of strong compactness has its origin in infinitary logic, and was formulated by Tarski as a natural generalization of the compactness of first order logic. Many distinct characterizations have been found.

Read the rest of this entry »

1 Comment | 580: Topics in set theory | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Cardinal arithmetic (10)

March 9, 2009

Let me begin with a couple of comments that may help clarify some of the results from last lecture.

First, I want to show a different proof of Lemma 21.2, that I think is cleaner than the argument I gave before. (The argument from last lecture, however, will be useful below, in the proof of Kunen’s theorem.)

Lemma 1 If {\kappa} is measurable, {{\mathcal U}} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa,} and {j_{\mathcal U}:V\rightarrow M} is the corresponding ultrapower embedding, then {{}^\kappa M\subset M.}

 

Proof: Recall that if {\pi} is Mostowski’s collapsing function and {[\cdot]} denotes classes in {V^\kappa/{\mathcal U},} then {M=\{\pi([f]):f\in{}^\kappa V\}.} To ease notation, write {\langle f\rangle} for {\pi([f]).}

Let {h:\kappa\rightarrow M.} Pick {f:\kappa\rightarrow V} such that for all {\alpha<\kappa,} {h(\alpha)=\langle f(\alpha)\rangle.}

Lemma 2 With notation as above, {\langle f\rangle=j_{\mathcal U}(f)(\langle{\rm id}\rangle)} for any {f:\kappa\rightarrow V.}

 

Proof: For a set {X} let {c_X:\kappa\rightarrow V} denote the function constantly equal to {X.} Since {\pi} is an isomorphism, {\mbox{\L o\'s}}‘s lemma gives us that the required equality holds iff

\displaystyle \{\alpha<\kappa : f(\alpha)=((c_f)(\alpha))({\rm id}(\alpha))\}\in{\mathcal U},

but this last set is just {\{\alpha<\kappa:f(\alpha)=f(\alpha)\}=\kappa.} \Box

From the nice representation just showed, we conclude that {\langle f(\alpha)\rangle=j_{\mathcal U}(f(\alpha))(\langle{\rm id}\rangle)} for all {\alpha<\kappa.} But for any such {\alpha,} {j_{\mathcal U}(f(\alpha))=j_{\mathcal U}(f)(\alpha)} because {{\rm cp}(j_{\mathcal U})=\kappa} by Lemma 21 from last lecture. Hence, {h=(j_{\mathcal U}(f)(\alpha)(\langle{\rm id}\rangle):\alpha<\kappa),} which is obviously in {M,} being definable from {j_{\mathcal U}(f),} {\langle{\rm id}\rangle,} and {\kappa.} \Box

The following was shown in the proof of Lemma 20, but it deserves to be isolated.

Lemma 3 If {{\mathcal U}} is a normal nonprincipal {\kappa}-complete ultrafilter over the measurable cardinal {\kappa,} then {{\mathcal U}=\{X\subseteq\kappa:\kappa\in i_{\mathcal U}(X)\},} i.e., we get back {{\mathcal U}} when we compute the normal measure derived from the embedding induced by {{\mathcal U}.} {\Box}

 

Finally, the construction in Lemma 10 and preceeding remarks is a particular case of a much more general result.

Definition 4 Given {f:I\rightarrow J} and an ultrafilter {{\mathcal D}} over {I,} the projection {f_*({\mathcal D})} of {{\mathcal D}} over {J} is the set of {X\subseteq J} such that {f^{-1}(X)\in{\mathcal D}.}

 

Clearly, {f_*({\mathcal D})} is an ultrafilter over {J.}

Notice that if {\kappa={\rm add}({\mathcal D}),} {(X_\alpha:\alpha<\kappa)} is a partition of {I} into sets not in {{\mathcal D},} and {f:I\rightarrow\kappa} is given by {f(x)=} the unique {\alpha} such that {x\in X_\alpha,} then {f_*({\mathcal D})} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa.} (Of course, {\kappa=\omega} is possible.)

For a different example, let {{\mathcal U}} be a {\kappa}-complete nonprincipal ultrafilter over the measurable cardinal {\kappa,} and let {f:\kappa\rightarrow\kappa} represent the identity in the ultrapower by {{\mathcal U},} {\langle f\rangle=\kappa.} Then {f_*({\mathcal U})} is the normal ultrafilter over {\kappa} derived from the embedding induced by {{\mathcal U}.}

Definition 5 Given ultrafilters {{\mathcal U}} and {{\mathcal V}} (not necessarily over the same set), say that {{\mathcal U}} is Rudin-Keisler below {{\mathcal V},} in symbols, {{\mathcal U}\le_{RK}{\mathcal V},} iff there are sets {S\in{\mathcal U},} {T\in{\mathcal V},} and a function {f:T\rightarrow S} such that {{\mathcal U}\upharpoonright S=f_*({\mathcal V}\upharpoonright T).}

 

Theorem 6 Let {{\mathcal U}} be an ultrafilter over a set {X} and {{\mathcal V}} an ultrafilter over a set {Y.} Suppose that {{\mathcal U}\le_{RK}{\mathcal V}.} Then there is an elementary embedding {j:V^X/{\mathcal U}\rightarrow V^Y/{\mathcal V}} such that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

 

Proof: Fix {T\in{\mathcal U}} and {S\in{\mathcal V}} for which there is a map {f:S\rightarrow T} such that {{\mathcal U}\upharpoonright T=f_*({\mathcal V}\upharpoonright S).} Clearly, {V^X/{\mathcal U}\cong V^T/({\mathcal U}\upharpoonright T)} as witnessed by the map {[f]_{\mathcal U}\mapsto[f\upharpoonright T]_{{\mathcal U}\upharpoonright T},} and similarly {V^Y/{\mathcal V}\cong V^S/({\mathcal V}\upharpoonright S),} so it suffices to assume that {S=Y} and {T=X.}

Given {h:X\rightarrow V,} let {h_*:Y\rightarrow V} be given by {h_*=h\circ f.} Then {j([h]_{\mathcal U})=[h_*]_{\mathcal V}} is well-defined, elementary, and {j\circ i_{\mathcal U}=i_{\mathcal V}.}

In effect, {h=_{\mathcal U}h'} iff {\{x\in X:h(x)=h'(x)\}\in{\mathcal U}} iff {\{y\in Y:h\circ f(y)=h'\circ f(y)\}\in{\mathcal V}} iff {h_*=_{\mathcal V}h'_*,} where the second equivalence holds by assumption, and it follows that {j} is well-defined.

If {c_B^A} denotes the function with domain {A} and constantly equal to {B,} then for any {x,} {j\circ i_{\mathcal U}(x)=j([c^X_x]_{\mathcal U})=[(c^X_x)_*]_{\mathcal V}=[c^Y_x]_{\mathcal V}=i_{\mathcal V}(x)} since {(c^X_x)_*=c^Y_x} by definition of the map {h\mapsto h_*.} This shows that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

Elementarity is a straightforward modification of the proof of Lemma 10 from last lecture. \Box

One can show that Theorem 6 “very nearly” characterizes the Rudin-Keisler ordering, see for example Proposition 0.3.2 in Jussi Ketonen, Strong compactness and other cardinal sins, Annals of Mathematical Logic 5 (1972), 47–76.

Read the rest of this entry »

3 Comments | 580: Topics in set theory | Tagged: , , , , , , , | Permalink
Posted by andrescaicedo

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 »

2 Comments | 580: Topics in set theory | Tagged: , , , , , , , , | Permalink
Posted by andrescaicedo