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

November 4, 2010

[Edit, Oct. 1, 2013: Robert Solovay has pointed out an inaccuracy in my presentation of Woodin’s argument: Rather than simply requiring that $P$ is a hereditary property of models, we must require that $\mathsf{ZFC}$ proves this. A corrected presentation of the argument will be posted shortly.]

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.

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.

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.

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.

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.”]

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.

502 – Cancellation laws

October 28, 2009

Two homework problems. The first one is easier, so you can consider the second one to be extra credit. A proof of these results can be found in different places, for example, the paper Division by three, by Conway and Doyle. (Please don’t look at the paper while working on the homework, of course.) Unfortunately, the paper could use a serious trimming and editing, so I cannot really recommend it, but the proof is carefully written there.

1. Without using the axiom of choice, show that if $A$ and $B$ are sets, and $|A\times 2|=|B\times 2|,$ then $|A|=|B|.$
2. Same as 1., but now with $3$ instead of $2.$

502 – More on tilings

October 16, 2009

In class I mentioned without proof that there is a finite set of squares with which we can tile the plane, but not periodically. Hao Wang was the first to study the question of whether there are such tilings. He conjectured that the answer was not. In 1966, his student Robert Berger disproved the conjecture. He explained how tiles could be used to code the workings of a formalized computer (a Turing machine), in a way that one could solve recursively the Halting Problem if it were the case that any set that tiles can do so periodically. Since it is a well-known result from computability theory that the halting problem cannot be solved recursively, it follows that Wang’s conjecture is false.

Examining the tiling given by Berger, one finds that he requires 20426 tiles to do his coding. The number has been substantially reduced since. I believe the currently known smallest set of tiles that can only cover the plane aperiodically has size 13. It was exhibited by Karel Culik II in his paper An aperiodic set of 13 Wang tiles, Discrete Mathematics 160 (1996), 245-251. The Wikipedia entry on Wang tiles displays his example. Once again, the proof of aperiodicity uses the halting problem.

(I would be curious to know of improved bounds.)

502 – Ordinal exponentiation

October 16, 2009

The exercise I mentioned in class is the following: Let $\alpha^{\cdot\beta}$ denote ordinal exponentiation. For ordinals $\alpha,\beta$, define $F(\alpha,\beta)$ as the set consisting of those functions $f:\beta\to\alpha$ such that there are only finitely many $\xi$ such that $f(\xi)\ne0.$

(We haven’t formally defined “finite” yet, but we can take this to mean that the order type of the set $\{\xi\in\beta\mid f(\xi)\ne0\}$ is a natural number, using our formalized notion of natural number.)

For functions $f,g$ in $F(\alpha,\beta)$ set $f\triangleleft g$ iff $f(\xi) for $\xi$ largest such that $f(\xi)\ne g(\xi).$

Then $(F(\alpha,\beta),\triangleleft)$ is a well-ordered set, and its order type is precisely $\alpha^{\cdot\beta}.$