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 »

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 -Some choiceless results (3)

January 27, 2009

[Updated December 3. The previous proof that there is a canonical bijection \alpha\sim\alpha\times\alpha for all infinite ordinals \alpha was seriously flawed. Thanks to Lorenzo Traldi for pointing out the problem.]

5. Specker’s lemma.

This result comes from Ernst Specker, Verallgemeinerte Kontinuumshypothese und Auswahlaxiom, Archiv der Mathematik 5 (1954), 332-337. I follow Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413-426 in the presentation of this and the following result. The Kanamori-Pincus paper, to which we will return next lecture, has several interesting problems, results, and historical remarks, and I recommend it. It can be found here.

Read the rest of this entry »