From Determinacy to a Woodin I

In my previous posts I provided a sketch of how a measurable above a limit of Woodins implies that \textsf{AD} holds in L(\mathbb R). The “converse”, saying that \textsf{AD} implies that there is a model with infinitely many Woodin cardinals, is a lot more complicated. I will try to simplify a lot of these complications here, to give an idea of what is going on. I will only focus on showing the existence of a single Woodin (for now), where the Woodin in question will be \Theta^{L(\mathbb R)} inside of \text{HOD}^{L(\mathbb R)}. As always, I will be very sketchy in this blog post, but provide more details in my note.

The theorem of interest is the following.

Theorem 1 (Woodin). Assume \textsf{ZF+DC+AD}. Then

\text{HOD}^{L(\mathbb R)}\models\Theta^{L(\mathbb R)} is a Woodin cardinal.

The assumption of \textsf{DC} is not really needed, but it makes the proof a bit more smooth. The proof of this theorem is very related to the following theorem, due to Solovay.

Theorem 2 (Solovay). Assume \textsf{ZF+AD}. Then

L(\mathbb R)\models\omega_1^V is measurable.

To define the given measure on \omega_1^V we first need to introduce some terminology. For x\in{^\omega\omega} define the binary relation

E_x:=\{(m,n)\in\omega\times\omega\mid x(\langle m,n\rangle)=0\},

where \langle\cdot,\cdot\rangle:\omega\times\omega\to\omega is a recursive bijection. Then the key set is

\text{WO}:=\{x\in{^\omega\omega}\mid E_x\text{ is a wellordering}\}.

Also, setting \alpha_x to be the order-type of E_x, set \text{WO}_\alpha:=\{x\in\text{WO}\mid\alpha_x=\alpha\} and define \text{WO}_{<\alpha}, \text{WO}_{\leq\alpha} and \text{WO}_{[\alpha,\beta]} and so on in the obvious fashion. Then define the game \mathcal G(S) associated to a subset S\in\mathcal P^{L(\mathbb R)}(\omega_1^V) as

\begin{array}{lllllllll} \text{I} & x_0 && x_1 && x_2 && \cdots\\ \text{II} && y_0 && y_1 && y_2 && \cdots\end{array},

with x_i,y_i<\omega and the rules of the game requiring that (x)_i,(y)_i\in\text{WO} for every i<\omega and \alpha_{(x)_0}<\alpha_{(y)_0}<\alpha_{(x)_1}<\alpha_{(y)_1}<\cdots. Player I wins iff \text{sup}_i\alpha_{(x)_i}\in S. We can then define our measure \mu on \omega_1^V as

\mu(S)=1 iff Player I wins \mathcal G(S).

Then \mu is clearly non-principal, upwards closed and \textsf{AD} ensures that it has the ultra property. It thus only remains to show that it’s normal. Assuming it’s not and letting f:\omega_1\to\omega_1 be a regressive function witnessing the failure of normality, \textsf{AD} implies that

S_\alpha:=\{\xi<\omega_1\mid f(\xi)\neq\alpha\}\in\mu

for every \alpha<\omega_1. It then turns out that we can define

  • An increasing sequence \langle\eta_i\mid i<\omega\rangle of countable ordinals;
  • A sequence of sets of strategies \langle X_i\mid i<\omega\rangle where X_i consists of winning strategies for player I in \mathcal G(S_\alpha) for all \alpha\in[\eta_{i-1},\eta_i) (where we set \eta_{-1}:=0 for convenience);
  • A sequence \langle y_i\mid i<\omega\rangle of reals such that y_i is legal for player II against any \sigma\in X_i and \text{sup}_j\alpha_{(y_i)_j}=\text{sup}_i\eta_i.

These y_i‘s will then witness that f(\eta)\neq\alpha for any \alpha<\eta, by definition of the games \mathcal G(S_\alpha) as well as the definition of the S_\alpha‘s. But this then contradicts that f is regressive!

The actual construction of the above sequences requires some tools that relies on the nature of the set \text{WO}. We won’t supply the proofs of neither these tools nor how they entail the existence of the above sequences – if you’re interested you can have a look at my note. The two tools that we need is a boundedness result and a coding result.


Tool 1 (\bf\Sigma^1_1-boundedness; Luzin-Sierpinski). Assume \textsf{ZF+AD}. Then whenever X\subset\text{WO} is \bf\Sigma^1_1 there is some \alpha<\omega_1 such that X\subset\text{WO}_{<\alpha}.

Tool 2 (Basic coding; Solovay). Assume \textsf{ZF+AD} and let Z\subset\text{WO}\times{^\omega\omega}. Then there is a \bf\Sigma^1_2 subset Z^*\subset Z such that Z^* is a selector for Z, i.e. that for every \alpha<\omega_1 it holds that

Z^*\cap(\text{WO}_\alpha\times{^\omega\omega})\neq\emptyset\Leftrightarrow Z\cap(\text{WO}_\alpha\times{^\omega\omega})\neq\emptyset.


Tool 2 is used to construct a specific choice of X_i‘s such that Tool 1 can be used to construct the y_i‘s. This finishes the (very rough) sketch of Solovay’s Theorem 2. The same ideas can be used to show that (\bf\delta^2_1)^{L(\mathbb R)} is also measurable in L(\mathbb R). Here’s the analogy:

\begin{array}{c | c} \hline {\bf\delta^1_1} & {\bf\delta^2_1} \\\hline \text{WO} & \mathcal U\\ {\bf\delta^1_1}\text{-many }\alpha_x's & {\bf\delta^2_1}\text{-many }\delta_x's\\ {\bf\Sigma^1_1}\text{-boundedness} & {\bf\Delta^2_1}\text{-boundedness}\\ {\bf\Sigma^1_2}\text{-coding} & {\bf\Sigma^2_1}\text{-coding}\\\hline \end{array}

Here \mathcal U is a universal \Sigma^2_1 set, and just as the \alpha_x‘s partitioned \text{WO} into \bf\delta^1_1-many pieces, the \delta_x‘s are defined in such a way that they also partition \mathcal U into \bf\delta^2_1-many pieces. We get analogous boundedness and coding tools which are due to Moschovakis, and by using these we can simply copy the proof of Solovay’s theorem to get the following.

Theorem 3 (Moschovakis). Assume \textsf{ZF+DC+AD}. Then

L(\mathbb R)\models{\bf\delta^2_1} is measurable.

The use of \textsf{DC} can be avoided, but it is required if we simply want to reuse Solovay’s proof. When we want to not only show measurability, but show Woodinness, we have to suddenly construct extenders rather than measures to get the desired strength. These will use similar ideas, but a new reflection tool will be needed. More about that next time!