## Set theory seminar – Marion Scheepers: Coding strategies (II)

For the first talk, see here. The second talk took place on September 21.

We want to prove $(2.\Rightarrow1.)$ of Theorem 1, that if ${\rm cf}(\left< J\right>,\subset)\le|J|$, then II has a winning coding strategy in $RG(J)$.

The argument makes essential use of the following:

Coding Lemma. Let $({\mathbb P},<)$ be a poset such that for all $p\in{\mathbb P}$,

${}|\{q\in{\mathbb P}\mid q>p\}|=|{\mathbb P}|.$

Suppose that ${}|H|\le|{\mathbb P}|$. Then there is a map $\Phi:{\mathbb P}\to{}^{<\omega}H$ such that

$\forall p\in{\mathbb P}\,\forall\sigma\in H\,\exists q\in{\mathbb P}\,(q>p\mbox{ and }\Phi(q)=\sigma).$

Proof. Note that ${\mathbb P}$ is infinite. We may then identify it with some infinite cardinal $\kappa$. It suffices to show that for any partial ordering $\prec$ on $\kappa$ as in the hypothesis, there is a map $\Phi:\kappa\to\kappa$ such that for any $\alpha,\beta$, there is a $\gamma$ with $\alpha\prec\gamma$ such that $\Phi(\gamma)=\beta$.

Well-order $\kappa\times\kappa$ in type $\kappa$, and call $R$ this ordering. We define $\Phi$ by transfinite recursion through $R$. Given $(\alpha,\beta)$, let $A$ be the set of its $R$-predecessors,

$A=\{(\mu,\rho)\mid(\mu,\rho) R(\alpha,\beta)\}$.

Our inductive assumption is that for any pair $(\mu,\rho)\in A$, we have chosen some $\tau$ with $\mu\prec\tau$, and defined $\Phi(\tau)=\rho$.  Let us denote by $D_A$ the domain of the partial function we have defined so far. Note that ${}|D_A|<\kappa$. Since $\{\gamma\mid\alpha\prec\gamma\}$ has size $\kappa$, it must meet $\kappa\setminus D_A$. Take $\mu$ to be least in this intersection, and set $\Phi(\mu)=\beta$, thus completing the stage $(\alpha,\beta)$ of this recursion.

At the end, the resulting map can be extended to a map $\Phi$ with domain $\kappa$ in an arbitrary way, and this function clearly is as required. $\Box$

Back to the proof of $(2.\Rightarrow1.)$. Fix a perfect information winning strategy $\Psi$ for II in $RG(J)$, and a set $H$ cofinal in $\left< J\right>$ of least possible size. Pick a $f:\left< J \right>\to H$ such that for all $A\in \left< J\right>$ we have $A\subseteq f(A)$.

Given $X\in J$, let $J(X)=\{Y\in J\mid X\subseteq Y\}$. Now we consider two cases, depending on whether for some $X$ we have ${}|J(X)|<|J|$ or not.

Suppose first that $|J(X)|=|J|$ for all $X$. Then the Coding Lemma applies with $(J,\subset)$ in the role of ${\mathbb P}$, and $H$ as chosen. Let $\Phi$ be as in the lemma.

We define $F:J\times\left< J\right>\to J$ as follows:

1. Given $O\in\left< J\right>$, let $Y\supseteq\psi(f(O))$ be such that $\Phi(Y)=\left$, and set $F(\emptyset,O)=Y$.
2. Given $(T,O)\in J\times\left< J\right>$ with $T\ne\emptyset$, let $Y\supseteq \Psi(\Phi(T){}^\frown\left)$ be such that $\Phi(Y)=\Phi(T){}^\frown\left< f(O)\right>$, and set $F(T,O)=Y$.

Clearly, $F$ is winning: In any run of the game with II following $F$, player II’s moves cover their responses following $\Psi$, and we are done since $\Psi$ is winning.

The second case, when there is some $X\in J$ with $|J(X)|<|J|$, will be dealt with in the next talk.