Woodin’s proof of the second incompleteness theorem for set theory

November 4, 2010

As part of the University of Florida Special Year in Logic, I attended a conference at Gainesville on March 5–9, 2007, on Singular Cardinal Combinatorics and Inner Model Theory. Over lunch, Hugh Woodin mentioned a nice argument that quickly gives a proof of the second incompleteness theorem for set theory, and somewhat more. I present this argument here.

The proof is similar to that in Thomas Jech, On Gödel’s second incompleteness theorem, Proceedings of the American Mathematical Society 121 (1) (1994), 311-313. However, it is semantic in nature: Consistency is expressed in terms of the existence of models. In particular, we do not need to present a proof system to make sense of the result. Of course, thanks to the completeness theorem, if consistency is first introduced syntactically, we can still make use of the semantic approach.

Woodin’s proof follows.

Read the rest of this entry »

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

Luminy – Hugh Woodin: Ultimate L (III)

October 27, 2010

For the first lecture, see here.

For the second lecture, see here.

Read the rest of this entry »

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

Luminy – Hugh Woodin: Ultimate L (II)

October 21, 2010

For the first lecture, see here.

Read the rest of this entry »

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

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

580 -Partition calculus (5)

April 21, 2009

1. Larger cardinalities

We have seen that {\omega\rightarrow(\omega)^n_m} (Ramsey) and {\omega\rightarrow[\omega]^n_\omega} ({\mbox{Erd\H os}}-Rado) for any {n,m<\omega.} On the other hand, we also have that {2^\kappa\not\rightarrow(3)^2_\kappa} ({\mbox{Sierpi\'nski}}) and {2^\kappa\not\rightarrow(\kappa^+)^2} ({\mbox{Erd\H os}}-Kakutani) for any infinite {\kappa.}

Positive results can be obtained for larger cardinals than {\omega} if we relax the requirements in some of the colors. A different extension, the {\mbox{Erd\H os}}-Rado theorem, will be discussed later.

Theorem 1 ({\mbox{Erd\H os}}-Dushnik-Miller) For all infinite cardinals {\lambda,} {\lambda\rightarrow(\lambda,\omega)^2.}

This was originally shown by Dushnik and Miller in 1941 for {\lambda} regular, with {\mbox{Erd\H os}} providing the singular case. For {\lambda} regular one can in fact show something stronger:

Theorem 2 ({\mbox{Erd\H os}}-Rado) Suppose {\kappa} is regular and uncountable. Then

\displaystyle \kappa\rightarrow_{top}(\mbox{Stationary},\omega+1)^2,

which means: If {f:[\kappa]^2\rightarrow2} then either there is a stationary {H\subseteq\kappa} that is {0}-homogeneous for {f}, or else there is a closed subset of {\kappa} of order type {\omega+1} that is {1}-homogeneous for {f}.

(Above, top stands for “topological.”)

Read the rest of this entry »

4 Comments | 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

Set theory seminar -Richard Ketchersid: Quasiiterations I. Iteration trees

January 19, 2009

In October 24-November 14 of 2008, Richard Ketchersid gave a nice series of talks on quasiiterations at the Set Theory Seminar. The theme is to correctly identify `nice’ branches through iteration trees, and to see how difficult it is for a model to compute these branches. Richard presented a prototypical result in this area (due to Woodin) and a nice application (due to Jackson and Ketchersid). This post will be far from self-contained, and only present some of the definitions.

[Edit Sep. 25, 2010: My original intention was to follow this post with two more notes, on Woodin’s result and on the Jackson-Ketchersid theorem, but I never found the time to polish the presentation to a satisfactory level, so instead I will let the interested reader find my drafts at Lucien’s library.]

I’ll assume known the notions of extender and Woodin cardinal, and associated notions like the length or strength of an extender. A good reference for this post is Donald Martin, John Steel, Iteration trees, Journal of the American Mathematical Society 7 (1) 1994, 1-73. As usual, all inaccuracies below are mine. Some of the notions below are slightly simpler than the official definitions. These notions are all due to Donald Martin, John Steel, and Hugh Woodin.

In this post I present the main notions (iteration trees and iterability) and close with a quick result about the height of tree orders. The order I follow is close to Richard’s but it differs from his presentation at a few places.

Read the rest of this entry »

Leave a Comment » | Set theory seminar | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo