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 this book by Larson.

This post is part of a series on determinacy:

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:

$\textsf{PD}$ from infinitely many Woodins and a measurable above;
$\textsf{AD}^{L(\mathbb R)}$ from infinitely many Woodins and a measurable above;
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 by Martin and Steel. 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

$$ \cdots\in*\mu[f_2]\in*\mu[f_1]\in_\mu[f_0] $$

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 32.2 in Kanamori)

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.