The Easiest Proof of Analytic Determinacy

A tree $T$ on $\omega\times\alpha$ is homogeneous if there is a system of measures $\langle\mu_s\mid s\in\omega^{<\omega}\rangle$ so that

$(1)$ $\mu_s$ concentrates on $T_s=\{u\in \alpha^{\mathrm{len}(s)}\mid (s, u)\in T\}$,

$(2)$ if $s\subseteq t$ and $A\in \mu_s$ then $\{v\in T_t\mid v\upharpoonright \mathrm{len}(s)\in A\}\in\mu_t$ and

$(3)$ if $x\in p[T]:=\{y\in\omega^\omega\mid\exists z\in\alpha^\omega\forall n<\omega (y\upharpoonright n, z\upharpoonright n)\in T\}$ then the natural direct limit along $\mathrm{Ult}(V, \mu_{x\upharpoonright n})$ for $n<\omega$ is wellfounded.

An uncountable cardinal $\kappa$ is Ramsey if for any coloring $c\colon [\kappa]^{<\omega}\rightarrow\omega$ there is a $c$-homogeneous set of size $\kappa$, i.e. there is $H\in[\kappa]^\kappa$ so that for all $s, t\in [H]^{<\omega}$, $\mathrm{len}(s)=\mathrm{len}(t)$ implies $c(s)=c(t)$.

A tree $T$ on $\omega\times\alpha$ is Ramsey if for every coloring $c\colon T\rightarrow \omega$ there is a subtree $S\subseteq T$ so that

$(1)$ $S$ is homogeneous for $c$, i.e. for $(s, u),(t,v)\in S$, $s=t$ implies $c(s, u)=c(t, v)$ and

$(2)$ $p[S]=p[T]$.

Every homogeneous tree is Ramsey.

Let $\langle \mu_s\mid s\in\omega^{<\omega}\rangle$ witness a tree $T$ to be homogeneous and let $c\colon T\rightarrow \omega$ be a coloring. For every $s\in\omega^{<\omega}$ there is a set $A_s\in\mu_s$ so that $c$ is constant on $A_s$. Let $S$ be the tree of all $(s, u)\in T$ so that for all $(t, v)\leq_T(s, u)$, we have $v\in A_t$. Clearly, $S$ is homogeneous for $c$, so it remains to show that $p[S]=p[T]$. For $x\in p[T]$, the natural direct limit along $\mu_{x\upharpoonright n}$ is wellfounded, which is equivalent to $$\forall (B_n)_{n<\omega}\in\prod_{n<\omega}\mu_{x\upharpoonright n}\ \exists y\in\mathrm{Ord}^\omega\forall n<\omega\ y\upharpoonright n\in B_n.$$ Applying this with $B_n=A_{x\upharpoonright n}$, we find that $x\in p[S]$.

Suppose $T$ is a Ramsey tree. Then the game $G$ on $\omega$ with winning set $p[T]$ is determined.

Consider the auxiliary game $G_{\mathrm{aux}}$ in which player $I$ is addionally asked to play a "proof" that the resulting play is in $p[T]$. That is in round $2k$, $I$ plays $n_{2k}<\omega$ and $\xi_k\in\mathrm{Ord}$ while in round $2k+1$, $II$ only plays a natural number $n_{2k+1}$. Player $I$ wins iff $(n_k, \xi_k)_{k<\omega}$ constitutes a cofinal branch through $T$. Note that this is a closed game since if player $I$ loses, the game is already lost after only finitely many rounds. By open determinacy, the game $G_{\mathrm{aux}}$ is determined so that one of the players has a winning strategy. We aim to show that the same player has a winning strategy in the game $G$. This is easy if $I$ wins in $G_{\mathrm{aux}}$: we let player $I$ play the game $G$ while imagining a run of the game $G_{\mathrm{aux}}$ and hide the additional moves $\xi_k$.

So let us assume that $\sigma$ is a winning strategy for player $II$ in $G_{\mathrm{aux}}$. The argument from before does not work anymore as in a run of the game $G$, player $I$ does not play the additional moves $\xi_k$ that would be required to apply $\sigma$. Instead, we basically make up the $\xi_k$ ourselves and use the Ramseyness of $T$ to do so coherently.

Let the coloring $c\colon T\rightarrow\omega$ be defined by $$c(n_0^\frown\dots^\frown n_{2k}, \xi_0^\frown\dots^\frown\xi_{2k})=m$$ where $m$ is the next play by $\sigma$ in the run of $G_{\mathrm{aux}}$ where $(n_0, \xi_0), n_1,\dots, (n_{2k}, \xi_k)$ was played so far. We define $c$ arbitrarily on the even levels.

As $T$ is Ramsey, let $S$ be a $c$-homogeneous subtree with $p[S]=p[T]$. We can now define the strategy $\sigma_\ast$ for player $II$ in the game $G$ as follows. If $s=n_0,\dots, n_{2k}$ was played so far, $\sigma_\ast$ responds with $c(s, t)$ where $t$ is any sequence such that $(s, t)\in S$ (if no such $t$ exists, $\sigma_\ast$ plays $0$). The point is that this does not depend on the choice of $t$ by homogeneity of $S$ .

Let us verify that this is a winning strategy. If not, there is a run $x=n_0^\frown n_1^\frown\dots$ of the game $G$ in which player $II$ followed $\sigma_\ast$ and has lost, i.e. $x\in p[T]$. As $p[T]=p[S]$ there is an $\omega$-sequence $y=\xi_0^\frown \xi_1^\frown\dots$ so that $(x, y)$ is a cofinal branch through $S$. But then $(n_0, \xi_0), n_1, (n_2,\xi_1), n_3, (n_4, \xi_2), n_4,\dots$ is a run in the game $G_{\mathrm{aux}}$ in which player $II$ follows $\sigma$ and loses, contradiction!

Suppose there is a Ramsey cardinal. Then every coanalytic set is the projection of a Ramsey tree.

Let $A$ be coanalytic as witnessed by $s\mapsto \leq_s$ as above. For any set $X$ of ordinals, let $T_X$ be the tree consisting of $(s, t)\in \omega^{<\omega}\times X^{<\omega}$ so that $s, t$ are of the same length (say $k$) and $m\mapsto \xi_m$ is an order embedding of $(k, \leq_s)$ into $(X, \in)$ where $t=\xi_0^\frown\dots^\frown\xi_{k-1}$.

As any wellorder on $\omega$ has countable ordertype, $p[T_X]=A$ for all uncountable sets of ordinals $X$.

Let $\kappa$ be a Ramsey cardinal. We will see that $T_\kappa$ is Ramsey. So suppose that $c\colon T_\kappa\rightarrow \omega$ is some coloring. Let $\langle s_n\mid n<\omega\rangle$ be an enumeration of $\omega^{<\omega}$ so that $k_n\coloneqq \mathrm{len}(s_n)\leq n$. Define a coloring $d\colon [\kappa]^{<\omega}\rightarrow \omega$ via $d(\{\xi_0,\dots,\xi_{n-1}\})=c(s_n, u_n)$ where $u_n$ is the unique enumeration of $\{\xi_0,\dots, \xi_{k_{n}-1}\}$ $(s_n, u_n)\in T_\kappa$. As $\kappa$ is Ramsey, there is some $d$-homogeneous set $H\subseteq\kappa$ of size $\kappa$. Chasing definitions, we find that $T_H$ is a $c$-homogeneous subtree of $T_\kappa$ with $p[T_H]=A$.

If there is a Ramsey cardinal then all coanalytic sets, and hence all analytic sets, are determined.

A tree $T$ on $\omega\times\alpha$ is Ramsey over $L$ if for any coloring $c\colon T\rightarrow\omega$ with $c\in L[T]$, there is a subtree $S$ of $T$ which is homogeneous for $c$ with $p[S]=p[T]$.

Suppose $T$ is Ramsey over $L$. Then $p[T]$ is determined.

Follow the previous determinacy proof. Note that the auxiliary game $G_{\mathrm{aux}}$ is in $L[T]$. It follows from absoluteness of wellfoundedness that $V$ and $L[T]$ agree about which players have winning strategies in the closed game $G_{\mathrm{aux}}$ and in fact for strategies in $L[T]$, the two models agree whether the strategy is winning. Hence in the difficult case where player $II$ wins $G_{\mathrm{aux}}$, we may assume that the winning strategy is in $L[T]$. But then the relevant coloring $c$ we construct from $\sigma$ is in $L[T]$ as well and the rest of the argument goes through.

Suppose $x^\sharp$ exists for every real $x$. Then every coanalytic set is the projection of a tree which is Ramsey over $L$.

We slightly modify the argument which assumed a Ramsey cardinal to exist and use the same notation. Let $A$ be coanalytic as witnessed by $s\mapsto \leq_s$. Now let $x$ be a real which codes $s\mapsto \leq_s$ and note that $T_{\omega_1^V}\in L[x]$. We will see that $T_{\omega_1^V}$ is Ramsey over $L$. Let $c\colon T\rightarrow\omega$ be any coloring in $L[T_{\omega_1^V}]\subseteq L[x]$. Then $c$ is definable over $L[x]$ from $x$-indiscernibles $\gamma_0<\dots<\gamma_n<\omega_1^V<\delta_0<\dots<\delta_m$. Let $I\subseteq\omega_1^V$ be the club of $x$-indiscernibles and let $X=I\setminus (\gamma_n+1)$. Then $T_X$ is homogeneous for $c$ and $p[T_X]=A$ as $X$ is uncountable.

Suppose $x^\sharp$ exists for every real $x$. Then every analytic set is determined.

Suppose $\kappa$ is a strong limit cardinal and $T$ is a $\kappa$-Ramsey tree. Then $p[T]$ is ${<}\kappa$-universally Baire.

Suppose $\kappa$ is an uncountable strong limit, $\lambda<\kappa$, $A\subseteq\omega^\omega$ is the projection of a $\kappa$-Ramsey tree and $f\colon\lambda^\omega\rightarrow\omega^\omega$ is continuous. Then $f^{-1}[A]$ is the projection of a $\kappa$-Ramsey tree.

For notational simplicity, let us assume that $f$ is Lipschitz, so $f$ is induced by a level- and inclusion-preserving map $g\colon \lambda^{<\omega}\rightarrow\omega^{<\omega}$. Let $T$ be a $\kappa$-Ramsey tree on $\omega\times\alpha$ with $p[T]=A$ and define $S$ as the natural tree on $\lambda\times\alpha$ so that a cofinal branch $(x, y)\in[S]$ induces a cofinal branch $(f(x), y)\in [T]$. More precisely, $(s, u)\in S$ iff $(g(s), u)\in T$. Clearly, $p[S]=f^{-1}[A]$, so it suffices to prove that $S$ is $\kappa$-Ramsey. So let $c\colon S\rightarrow \gamma$ be a coloring with $\gamma<\kappa$. This induces a coloring $d$ from $T$ into partial maps $\lambda^{<\omega}\rightarrow\gamma$ by setting $$d(s, u)\colon g^{-1}(s)\rightarrow \gamma,\ d(s, u)(t)=c(t, u).$$ As $\omega\cdot\gamma^\lambda<\kappa$, there is a subtree $T_\ast\subseteq T$ which is homogeneous for $d$ with $p[T_\ast]=p[T]$. Now define $S_\ast$ from $T_\ast$ in the same way we defined $S$ from $T$. It is not hard to verify that $S_\ast$ is homogeneous for $c$ and $p[S_\ast]=p[S]$.

Suppose $\lambda\geq\omega$ and $A\subseteq\lambda^\omega$ is the projection of a Ramsey tree. Then $A$ has the property of Baire in $\lambda^\omega$.

Recall the usual proof of Baire property from determinacy. For any $s\in\lambda^{<\omega}$, consider the game $G_s$ in which players $I$ and $II$ alternate in playing non-trivial finite sequences $s_{2n}, s_{2n+1}\in\lambda^{<\omega}$ and player $I$ wins iff $s^\frown s_0^\frown s_1^\frown\dots\in A$. We have that $A$ has the property of Baire iff $G_s$ is determined for all $s\in\lambda^{<\omega}$. We show the latter. Let $\lambda^{\geq 1}$ be the set of non-trivial finite sequences in $\lambda$ and let $f\colon (\lambda^{\geq 1})^\omega\rightarrow\lambda^\omega$ be the concatenation map and let $g_s\colon\lambda^\omega\rightarrow\lambda^\omega$ be the map which prepends the finite sequence $s$. As $g_s\circ f$ is continuous, $B\coloneqq (g_s\circ f)^{-1}[A]$ is the projection of a Ramsey tree (we identify $\lambda^{\geq 1}$ with $\lambda$) and hence the game on $\lambda^{\geq 1}$ with winning-set $B$ is determined. This is exactly the game $G_s$.

Suppose there is a proper class of Woodin cardinals and $A\subseteq\omega^\omega$. The following are equivalent.

$(1)$ For every $\kappa$, $A$ is the projection of a $\kappa$-homogeneous tree.

$(2)$ For every $\kappa$, $A$ is the projection of a $\kappa$-Ramsey tree.

$(3)$ For every $\kappa$, $A$ is $\kappa$-universally Baire.

We have shown $(1)\Rightarrow (2)\Rightarrow (3)$. The direction $(3)\Rightarrow (1)$ is due to Woodin and Martin-Steel.

Suppose $\kappa$ is an uncountable strong limit cardinal and $T$ is a $\kappa$-Ramsey tree. Then there is a tree $S$ so that $T$ and $S$ project to complements in all forcing extensions by a forcing of size ${<}\kappa$.

Suppose $\kappa$ is an uncountable cardinal, $T$ is a $\kappa$-Ramsey tree, $\lambda<\kappa$ and $S$ is a tree on $\omega\times\lambda$ with $p[S]\subseteq p[T]$. Then there is a order-preserving map $f\colon S\rightarrow T$ which is the identity on the first coordinate.

Consider the following game: as the play proceeds, player $I$ plays an increasing sequence of $(s_n, u_n)\in S_n$ and player $II$ plays an increasing sequence of $(t_n, v_n)\in T_n$. Player $II$ wins iff $s_n=t_n$ for all $n<\omega$.

We have already shown that $p[T]$ is ${<}\kappa$-universally Baire by verifying the original definition. Thus for $\lambda<\kappa$, there are trees $(T_\lambda', S_\lambda)$ with $p[T_\lambda']=p[T]$ which project to complements in all forcings extensions by forcings of size $\leq\lambda$. We may assume that $\vert T_\lambda'\vert\leq 2^\lambda<\kappa$. By the previous lemma, there is a continuous translation $f\colon T_\lambda'\rightarrow T$ of cofinal branches. It follows that $p[T_\lambda']\subseteq p[T]$ holds in any(!) outer model of $V$, in particular in a forcing extension $V[G]$ by a forcing of size $\leq\lambda$. Now, as $T$ and $S_\lambda$ have disjoint projection in $V$, this remains true in $V[G]$ (this follows by absoluteness of wellfoundedness, consider the tree looking for cofinal branches in both trees with the same first coordinate). Thus we must have $$V[G]\models p[T_\lambda']=p[T].$$ Hence in fact $T$ and $S_\lambda$ project to complements in small forcing extensions. By taking the sum $S=\bigoplus_{\lambda<\kappa} S_\lambda$, we find that $T$ and $S$ project to complements in all forcing extensions by a forcing of size ${<}\kappa$.

Suppose every coanalytic set is the projection of a Ramsey tree. Is there an inaccessible cardinal? Is there a $\omega_1$-Erdős cardinal?

Suppose $\kappa$ is an uncountable strong limit and $T$ is a $\kappa$-Ramsey tree. Is there a natural construction of a tree $S$ so that $T$ and $S$ project to complements in all forcing extensions by forcings of size ${<}\kappa$?