Determinacy from Woodins I

I’m amazed by the history of determinacy. As soon as classical descriptive set theorists found the impact the determinacy of games has on regularity properties of sets of reals, a sophisticated program began the goal of which was to characterise the strength of determinacy. The fact that \bf\Delta^1_2-determinacy seemed like an unreachable statement at the time is incredible, until it culminated with Woodin’s 1979 result that \textsf{AD}^{L(\mathbb R)} follows from the incredibly strong hypothesis \bf I_0, after which he isolated the Woodin cardinal as a variant of a Shelah cardinal and proved the well-known equiconsistency result between \textsf{AD} and infinitely many Woodins. For a more detailed historical exposition I can highly recommend [Larson2010].

I’m dedicating a few blog posts to giving an idea of how some of these later results are proven. As some of the proofs are incredibly long and technical, my goal is to give the main ideas and strategies of the proofs, intended to the set theorist who might be interested in what key ideas the determinacy crowd are using. My plan is to accompany most proofs with pdf notes in which I’m writing out the proofs with all the technical details. A tentative plan is to cover:

  1. \textsf{PD} from infinitely many Woodins and a measurable above;
  2. \textsf{AD}^{L(\mathbb R)} from infinitely many Woodins and a measurable above;
  3. The equiconsistency of \textsf{AD} with infinitely many Woodins.

The first result is due to Martin-Steel and the last two are due to Woodin. We’ll start by focusing on the first result.

We thus aim to sketch the proof of the following theorem.

Theorem (Martin-Steel, 1989). Assume there exists infinitely many Woodins and a measurable above. Then Projective Determinacy holds.

This theorem was proven in [MS1989]. The key property that is used is the notion of a homogeneously Suslin set, so this first post is going to focus on those. The first step is to define a tower of measures, which is analogous to an extender in that it’s a sequence of measures that collectively can form a single ultrapower. Here we only focus on countably complete measures over finite sequences of a fixed set X.

Say k\leq n,\mu_k is some measure over ^k X and \mu_n a measure over ^n X. We then say that these two measures are compatible if it holds that given any set A\subset{^k X}, A\in\mu_k iff \{s\in{^n\omega}\mid s\upharpoonright k\in A\}\in\mu_n. I.e. that the two measures “line up”.

We then say that an \omega-sequence \langle\mu_n\mid n<\omega\rangle is a tower of measures if there is some set X such that \mu_n is a measure over ^n X and all the measures are pairwise compatible. Such a tower is countably complete if given any sequence \vec A\in\Pi_{k<\omega}\mu_k there is some function f:\omega\to X such that f\upharpoonright n\in A_n for every n<\omega. Countably completeness ensures that the resulting ultrapower is wellfounded, because say there is an infinite descending chain


in the ultrapower. Say for simplicity that the set A_k witnessing that [f_k]\in_\mu[f_{k-1}] is in \mu_k for every k\geq 1. Then letting A_k:=\{u\in{^k X}\mid f_k(u)\in f_{k-1}(u\upharpoonright k-1)\}\in\mu_k\} witness this, the countably completeness gives us an f:\omega\to X such that

\cdots\in f_2(f\upharpoonright 2)\in f_1(f\upharpoonright 1)\in f_0(f\upharpoonright 0),

contradicting foundation.

Now let \kappa be a cardinal and X any set. A tree T on \omega\times X is then called \kappa-homogeneous if we can find a partial function \pi taking finite sequences of \omega to measures on {^{<\omega}}\kappa such that \pi(s) is a \kappa-complete measure with T_s\in\pi(s), for every s\in\text{dom}\pi, and given any x\in{^\omega\omega} we have that x\in p[T] iff \langle\pi(x\upharpoonright n)\mid n<\omega\rangle is a countably complete tower. In other words, we get a correspondence between reals in p[T] and countably complete towers.

Say now that a set of reals A is \kappa-homogeneously Suslin if A=p[T] for a \kappa-homogeneous tree, and A is homogeneously Suslin if it’s \kappa-homogeneously Suslin for some \kappa. So, given a homogeneously Suslin set, we can now associate to each element a corresponding countably complete tower. This turns out to give sufficient structure to ensure determinacy:

Theorem. Every homogeneously Suslin set A is determined.

Say T is homogeneous tree over \omega\times X with p[T]=A. The idea of the proof is to define the auxiliary game G^*:

\begin{array} {ccccccccc}\text{I} & \langle x_0,g_0 \rangle && \langle x_2,g_1 \rangle && \langle x_4,g_2 \rangle && \cdots\\ \text{II} && x_1 && x_3 && x_5 && \cdots \end{array}

Here x_i\in\omega and g_i\in X, and I wins iff \langle x,g \rangle\in[T]. Since [T] is closed, G^* is determined. If I has a winning strategy in G^* then he also has one in G_\omega(A) by just ignoring the g_i‘s. It turns out that the homogeneity of T ensures that II cannot have a winning strategy in G^*, thus making A determined (see [Kanamori, 32.2])

Our task has thus been reduced to showing that every projective set is homogeneously Suslin, assuming the existence of infinitely many Woodins and a measurable above. We will do this in an inductive fashion, starting by showing that \bf\Pi^1_1 sets are homogeneously Suslin and then going from \bf\Pi^1_n sets to \bf\Pi^1_{n+1} sets. But this is all happening in my next post.



  • [Larson2010] Larson, Paul B.: “A Brief History of Determinacy” in The Cabal Seminar Volume IV, 2010
  • [MS1989] Martin, Donald A. and Steel, John R.: “A Proof of Projective Determinacy” in the Journal of the American Mathematical Society, Volume 2, Number 1, 1989.
  • [Kanamori] Kanamori, Akihiro: “The Higher Infinite”, second edition, 2009.