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 Banach-Tarski paradox

December 17, 2009

1. Non-measurable sets

In these notes I want to present a proof of the Banach-Tarski paradox, a consequence of the axiom of choice that shows us that a naive understanding of the concept of volume can lead to contradictions. A good reference for this topic is the very nice book The Banach-Tarski paradox by Stan Wagon.

Read the rest of this entry »

502 – Exponentiation

December 9, 2009

This is the last homework assignment of the term: Assume {\sf CH}. Evaluate the cardinal number \aleph_3^{\aleph_0}, the size of the set of all  functions f:\omega\to\omega_3.

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 »

502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in {{\sf ZF}:}


  1. The axiom of choice: Every set can be well-ordered.
  2. Every collection of nonempty set admits a choice function, i.e., if {x\ne\emptyset} for all {x\in I,} then there is {f:I\rightarrow\bigcup I} such that {f(x)\in x} for all {x\in I.}
  3. Zorn’s lemma: If {(P,\le)} is a partially ordered set with the property that every chain has an upper bound, then {P} has maximal elements.
  4. Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set {S} such that {|S\cap x|=1} for all {x} in the family.
  5. Any set is a well-ordered union of finite sets of bounded size, i.e., for every set {x} there is a natural {m,} an ordinal {\alpha,} and a function {f:\alpha\rightarrow{\mathcal P}(x)} such that {|f(\beta)|\le m} for all {\beta<\alpha,} and {\bigcup_{\beta<\alpha}f(\beta)=x.}
  6. Tychonoff’s theorem: The topological product of compact spaces is compact.
  7. Every vector space (over any field) admits a basis.

Read the rest of this entry »

502 – Cantor-Bendixson derivatives

November 8, 2009

Given a topological space X and a set B\subseteq X, let B' be the set of accumulation points of B, i.e., those points p of X such that any open neighborhood of p meets B in an infinite set.

Suppose that B is closed. Then B'\subseteq B. Define B^\alpha for B closed compact by recursion: B^0=B, B^{\alpha+1}=(B^\alpha)', and B^\lambda=\bigcap_{\alpha<\lambda}B^\alpha for \lambda limit. Note that this is a decreasing sequence, so that if we set B^\infty=\bigcap_{\alpha\in{\sf ORD}}B^\alpha, there must be an \alpha such that B^\infty=B^\beta for all \beta\ge\alpha. 

[The sets B^\alpha are the Cantor-Bendixson derivatives of B. In general, a derivative operation is a way of associating to sets B some kind of “boundary.”]

Read the rest of this entry »

502 – The Löwenheim-Skølem theorem

November 8, 2009

In this note I sketch the proof of the Löwenheim-Skølem (or Löwenheim-Skølem-Tarski) theorem for first order theories. This basic result of model theory is really a consequence of a set theoretic combinatorial lemma, as the proof will demonstrate.

Let {{\mathcal L}} be a first order language, understood as a set of constant, function, and relation symbols. Let

\displaystyle  \kappa_{\mathcal L}=|{\mathcal L}|+\aleph_0,

so {\kappa_{\mathcal L}} is {|{\mathcal L}|,} unless {{\mathcal L}} is finite, in which case we take {\kappa_{\mathcal L}=\omega.} Talking about {\kappa_{\mathcal L}} rather than {|{\mathcal L}|} simplifies the presentation slightly.

The Löwenheim-Skølem theorem is concerned with the possible infinite sizes of models of first order theories. Of course, a theory {T} could only have finite models; the result does not say anything about {T} if that is the case.

Theorem 1 If {T} is a first order theory in a language {{\mathcal L},} and there is at least one infinite model of {T,} then there are models of {T} of size {\lambda,} for all {\lambda\ge\kappa_{\mathcal L}.}

We will prove a more precise statement. Before stating it, note that it is possible to have a theory {T} in some uncountable language {{\mathcal L}} such that {T} has models of certain infinite sizes, but not all. Theorem 1 does not say anything about infinite models of {T} of size {<\kappa_{\mathcal L}.} What cardinals in this range are the possible sizes of models of {T} is actually a rather difficult problem, and we will not address it.

Read the rest of this entry »