作成者: @fujidig, 作成日: 2021/10/26
Moschovakisの"Descriptive Set Theory" (2009)の6A節のExercisesの解答です．
(AC) $A \subseteq {}^\omega 2$であって決定的でないものが存在することを示せ。
$\seq{\sigma_\xi : \xi \lt 2^{\aleph_0}}$をプレイヤーIの戦略全体の枚挙、$\seq{\tau_\xi : \xi \lt 2^{\aleph_0}}$をプレイヤーIIの戦略全体の枚挙とする。 帰納的に${}^\omega 2$の部分集合の列$\seq{A_\xi : \xi \lt 2^{\aleph_0}}$, $\seq{B_\xi : \xi \lt 2^{\aleph_0}}$を以下を満たすように取る。
このような列がとれることを確認しよう。 $\xi$未満まで構成されたとする。 $A_\xi' = \bigcup_{\zeta \lt \xi} A_\zeta, B_\xi' = \bigcup_{\zeta \lt \xi} B_\zeta$とおく。 すると$\abs{A_\xi'}, \abs{B_\xi'} \le \abs{\xi}$である。 $\tau \mapsto \sigma_\xi \ast \tau$は単射なので、$A_\xi'$に$\sigma_\xi \ast \tau$が入らないような$\tau$がとれる。 その$\tau$を選び、$B_\xi = B_\xi' \cup \{\sigma_\xi \ast \tau\}$とおく。 同じく、$B_\xi$に$\sigma \ast \tau_\xi$が入らないような$\sigma$がとれるので、$A_\xi = A_\xi' \cup \{ \sigma \ast \tau_\xi \}$とおく。 これで列の構成ができた。
さて、$A = \bigcup_{\xi \lt 2^{\aleph_0}} A_\xi$とおく。 これが決定的でないことを言おう。 Player Iの戦略を任意にとると、それはある$\xi$について$\sigma_\xi$と書ける。 すると条件4より$\tau$があって、$\sigma \ast \tau_\xi \in B_\xi \subseteq B$である。$A$と$B$はdisjointなので、$\sigma \ast \tau_\xi \not \in A$である。 よってPlayer Iは必勝戦略を持たない。
Player IIの戦略を任意にとると、それはある$\xi$について$\tau_\xi$と書ける。 すると条件5より$\sigma$があって、$\sigma_\xi \ast \tau \in A_\xi \subseteq A$である。 よってPlayer IIは必勝戦略を持たない。
以上より、$A$は決定的でない。