決定性公理

$\sigma$ を I の必勝戦略、$\tau$ を II の必勝戦略とすると、両者が従うプレイ $z=\sigma*\tau$ は一つに決まる。$z$ は II の手の列に対して I が $\sigma$ に従ったプレイだから $\sigma$ が必勝であることにより $z\in A$ であり、同時に I の手の列に対して II が $\tau$ に従ったプレイでもあるから $\tau$ が必勝であることにより $z\notin A$ である。これは矛盾である。$\square$

まず $A$ が開集合の場合を示す。局面（それまでの手の有限列）$p\in\omega^{<\omega}$ の集合 $W_\alpha$ を順序数 $\alpha$ についての超限再帰で次のように定める。

• $p\in W_0$ $:\iff$ $N_p\subseteq A$（この局面から先はどう打っても I の勝ち）。
• $\alpha>0$ のとき、$W_{<\alpha}:=\bigcup_{\beta<\alpha}W_\beta$ とおき、$p\in W_\alpha$ $:\iff$ $p\in W_{<\alpha}$、または「$p$ の長さが偶数（I の番）で、ある $n$ について $p^\frown n\in W_{<\alpha}$」、または「$p$ の長さが奇数（II の番）で、すべての $n$ について $p^\frown n\in W_{<\alpha}$」。

$W:=\{p : \text{ある }\alpha\text{ で } p\in W_\alpha\}$ とし、$p\in W$ に対して $p\in W_\alpha$ となる最小の $\alpha$ を $\operatorname{rk}(p)$ と書く。$W$ は次の二つの閉包性をもつ。(i) 長さが偶数の $p$ について、ある $n$ で $p^\frown n\in W$ なら $p\in W$（$p\in W_{\operatorname{rk}(p^\frown n)+1}$ となる）。(ii) 長さが奇数の $p$ について、すべての $n$ で $p^\frown n\in W$ なら $p\in W$（置換公理により $\alpha:=\sup_n(\operatorname{rk}(p^\frown n)+1)$ が存在し、$p\in W_\alpha$ となる）。

場合 1：空列 $\emptyset$ が $W$ に属する。 I の戦略 $\sigma$ を次のように定める。I の番の局面 $p$ が $W$ に属し $\operatorname{rk}(p)>0$ なら、$\operatorname{rk}(p^\frown n)<\operatorname{rk}(p)$ となる最小の $n$ を選ぶ。そのような $n$ は存在する。実際 $\alpha=\operatorname{rk}(p)$ とすると $p\in W_\alpha\setminus W_{<\alpha}$ であり、$W_\alpha$ の定義で残るのは「ある $n$ で $p^\frown n\in W_{<\alpha}$」だけである。それ以外の局面では $0$ を選ぶ。

II の番の局面 $p\in W$ で $\alpha=\operatorname{rk}(p)>0$ なら、同じ理由ですべての $n$ について $p^\frown n\in W_{<\alpha}$ である。したがって I が $\sigma$ に従う限り、局面が $W$ に属し階数が正である間は、どちらが指しても階数は真に減る。順序数の真に減少する列は有限で終わるから、あるプレイの先頭部分 $x\restriction k$ で $\operatorname{rk}(x\restriction k)=0$、すなわち $N_{x\restriction k}\subseteq A$ となる。よって $x\in A$ であり、$\sigma$ は I の必勝戦略である。

場合 2：$\emptyset\notin W$。 II の戦略 $\tau$ を次のように定める。II の番の局面 $p\notin W$ では、$p^\frown n\notin W$ となる最小の $n$ を選ぶ。閉包性 (ii) の対偶により、そのような $n$ は存在する。それ以外の局面では $0$ を選ぶ。

I の番の局面 $p\notin W$ では、閉包性 (i) の対偶により、I がどの $n$ を選んでも $p^\frown n\notin W$ である。したがって II が $\tau$ に従う限り、プレイ $x$ のすべての先頭部分 $x\restriction k$ は $W$ に属さず、特に $N_{x\restriction k}\not\subseteq A$ である。もし $x\in A$ なら、$A$ が開集合であることから、ある $k$ で $N_{x\restriction k}\subseteq A$ となるはずである。よって $x\notin A$ であり、$\tau$ は II の必勝戦略である。

$A$ が閉集合の場合は、II の勝利集合 $\omega^\omega\setminus A$ が開集合である。上の議論で I と II の役割（偶数と奇数）を入れ替え、$W_0:=\{p : N_p\cap A=\emptyset\}$ から始めれば、同じ二つの場合分けで、II が必勝戦略をもつか I が必勝戦略をもつかのどちらかになる。

どちらの戦略も「条件を満たす最小の $n$」で定義したので、選択公理は使っていない。$\square$

$\omega^\omega$ の整列順序を一つ固定し、$\mathfrak c:=\lvert\omega^\omega\rvert$ に等しい濃度をもつ最小の順序数を $\kappa$ とする。$\alpha<\kappa$ なら $\lvert\alpha\rvert<\mathfrak c$ である。

戦略の数。 偶数の長さの有限列全体は可算無限集合なので、自然数と具体的に一対一に対応させられる。したがって I の戦略全体 $S_{\mathrm I}$ は $\omega^\omega$ と一対一に対応し、整列順序を移して $S_{\mathrm I}=\{\sigma_\alpha : \alpha<\kappa\}$ と並べられる。II の戦略も同様に $\{\tau_\alpha : \alpha<\kappa\}$ と並べる。

一つの戦略に従うプレイの数。 $y\mapsto\sigma*y$ は単射である。$y$ の各項は $\sigma*y$ の奇数番目にそのまま現れるからである。同様に $x'\mapsto x'*\tau$ も単射である。したがって $\{\sigma*y : y\in\omega^\omega\}$ と $\{x'*\tau : x'\in\omega^\omega\}$ はどちらも濃度 $\mathfrak c$ をもつ。

超限再帰。 $\alpha<\kappa$ について順に、プレイ $a_\alpha,b_\alpha$ を次のように選ぶ。

• $a_\alpha$：$\{\sigma_\alpha*y : y\in\omega^\omega\}\setminus\{b_\beta : \beta<\alpha\}$ の中で、固定した整列順序について最小の元。
• $b_\alpha$：$\{x'*\tau_\alpha : x'\in\omega^\omega\}\setminus\{a_\beta : \beta\leq\alpha\}$ の中で最小の元。

取り除く集合の濃度は $\lvert\alpha\rvert+1$ 以下で、これは $\mathfrak c$ より小さい。よって残りは空でなく、選択は毎回可能である。

$A:=\{b_\alpha : \alpha<\kappa\}$ とおく。

• どの $\alpha$ についても $a_\alpha\notin A$ である。$\beta<\alpha$ なら $a_\alpha\neq b_\beta$ は $a_\alpha$ の選び方による。$\beta\geq\alpha$ なら $b_\beta$ は $a_\alpha$ を除いて選んだ。したがって $\sigma_\alpha$ に従うプレイ $a_\alpha$ で I は負けており、$\sigma_\alpha$ は必勝戦略でない。
• どの $\alpha$ についても $b_\alpha\in A$ であり、$b_\alpha$ は II が $\tau_\alpha$ に従うプレイである。したがって $\tau_\alpha$ は II の必勝戦略でない。

すべての戦略がどこかの $\sigma_\alpha$ または $\tau_\alpha$ として現れるので、$G(A)$ は決定されない。$\square$

$\omega^\omega$ が整列可能なら thm-ad-nondetermined により決定されないゲームが存在し、$\mathsf{AD}$ に反する。選択公理のもとではすべての集合が整列可能である（整列可能定理）。$\mathbb R$ と $\omega^\omega$ の間には選択公理なしで全単射が作れるので、$\mathbb R$ についても同じ結論が成り立つ。$\square$

次のゲームを考える。I は初手 $x(0)=n$ で添字を指定し、以後の I の手は勝敗に関係しない。II の手の列を $y=(x(1),x(3),x(5),\dots)$ とし、$y\in A_{x(0)}$ なら II の勝ちとする。すなわち I の勝利集合は
$$ B:=\{x\in\omega^\omega : (x(1),x(3),x(5),\dots)\notin A_{x(0)}\} $$
である。

I は必勝戦略をもたない。実際、I の戦略 $\sigma$ が与えられたら $n:=\sigma(\emptyset)$ とおく。$A_n$ は空でないから、その元 $y$ を一つとれる（一つの集合から一つ選ぶだけなので選択公理は要らない）。II が I の手を無視して $y$ の項を順に指せば、II の手の列は $y\in A_n$ となり II が勝つ。

$\mathsf{AD}$ により、II が必勝戦略 $\tau$ をもつ。I が $n,0,0,0,\dots$ と指し II が $\tau$ に従うプレイの II の手の列を $f(n)$ とする。$\tau$ は必勝だから $f(n)\in A_n$ である。$f$ は $\tau$ から具体的に定まっているので、選択公理を使わずに存在する。$\square$