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

September 27, 2010

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<f(O\right>, 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<f(O)\right>) 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.