射影決定性(projective determinacy)とは、二人が自然数を交互に選ぶ長さ $\omega$ の完全情報ゲームで、勝利集合が射影集合であるものはすべて一方に必勝戦略をもつ、という主張である。ZFC が無矛盾なら ZFC からは証明できないが、無限個の Woodin 基数があれば成り立つ(Martin–Steel)。射影階層の一つの段のゲームがすべて決定されれば、その段の集合は完全集合性質と Baire の性質をもち、$\sigma$-有限な Borel 測度について可測になるので、射影決定性のもとで射影集合はすべてこれらの正則性をもち、非可算な射影集合の濃度は $2^{\aleph_0}$ になる。さらに一様化の性質が $\boldsymbol\Pi^1_{2n+1}$ と $\boldsymbol\Sigma^1_{2n+2}$ でくり返し成り立つ。
射影決定性(projective determinacy)とは、二人が自然数を交互に選ぶ長さ $\omega$ の完全情報ゲームで、勝利集合が 射影階層 に属する集合(射影集合)であるものは、すべて一方に必勝戦略がある、という主張である。決定性公理 は同じことをすべての集合について要求するので選択公理と両立しないが、射影決定性は選択公理を含む ZFC に付け加える公理として考えられる。
射影決定性は ZFC からは証明できない(ZFC が無矛盾なら)。一方、無限個の Woodin基数 があれば成り立つ(Martin–Steel)。射影決定性を仮定すると、射影集合はすべて完全集合性質と Baire の性質をもち、Lebesgue 可測になる。さらに、ZFC では $\boldsymbol\Pi^1_1$ と $\boldsymbol\Sigma^1_2$ についてしか分からない構造(一様化の性質など)が、$\boldsymbol\Pi^1_3,\boldsymbol\Sigma^1_4,\ldots$ と 2 段ごとにくり返し成り立つ。
この記事では、射影階層の一つの段 $\Gamma$ のゲームがすべて決定されれば、$\Gamma$ の集合は完全集合性質と Baire の性質をもつことを、補助のゲームを使って証明する。測度・一様化・Woodin 基数との関係は、主張と帰属を述べる。
$\mathcal N:=\omega^\omega$ を Baire 空間とし、有限列 $s\in\omega^{<\omega}$ について $N_s:=\{x\in\mathcal N\mid s\text{ は }x\text{ の始まりの部分}\}$ と書く。$N_s$ は開かつ閉で、全体が開基をなす。有限列 $s,t$ が 両立する とは、一方が他方の始まりの部分であることをいう。
$A\subseteq\mathcal N$ のゲーム $G(A)$、戦略、必勝戦略、ゲームが決定されることは、決定性公理 の定義「無限ゲームと戦略」「決定性と決定性公理」のとおりとする(I と II が交互に自然数を選び、できた列 $x$ が $A$ に属すれば I の勝ち)。
$\mathcal N$ の部分集合のクラス $\Gamma$ について、$\Gamma$ に属するすべての $A\subseteq\mathcal N$ で $G(A)$ が決定されることを $\mathrm{Det}(\Gamma)$ と書く。射影集合全体について $\mathrm{Det}$ が成り立つという主張を 射影決定性 という。すなわち、すべての $n\ge1$ で $\mathrm{Det}(\boldsymbol\Sigma^1_n)$ が成り立つことである。
射影階層 の命題「各段の包含関係」により $\boldsymbol\Pi^1_n\subseteq\boldsymbol\Sigma^1_{n+1}$、$\boldsymbol\Sigma^1_n\subseteq\boldsymbol\Pi^1_{n+1}$ なので、射影決定性は「すべての $n$ で $\mathrm{Det}(\boldsymbol\Pi^1_n)$」と言っても同じである(Mos09 6B の冒頭、p. 229 の定義は「すべての射影集合 $A\subseteq\mathcal N$ が決定される」)。
以下、$\Gamma$ は $\boldsymbol\Sigma^1_n$ または $\boldsymbol\Pi^1_n$($n\ge1$)のどれかとする。補助のゲームを $G(\cdot)$ の形に直すときに、次の閉包性を使う。
$A\in\Gamma$、$C\subseteq\mathcal N$ を閉集合、$\Phi\colon\mathcal N\to\mathcal N$ を連続写像とすると、$C\cap\Phi^{-1}(A)\in\Gamma$ である。
射影階層 の命題「射影階層の閉包性」により、$\Gamma$ は連続写像による逆像と可算個の共通部分で閉じている。同じ命題により閉集合は $\boldsymbol\Sigma^1_1$ であり、開集合も $\boldsymbol\Sigma^1_1$ なので閉集合は $\boldsymbol\Pi^1_1$ でもある。命題「各段の包含関係」により $\boldsymbol\Sigma^1_1\cup\boldsymbol\Pi^1_1\subseteq\boldsymbol\Sigma^1_n\cap\boldsymbol\Pi^1_n$ なので、$C\in\Gamma$ である。よって $C\cap\Phi^{-1}(A)\in\Gamma$ である。$\square$
$A\subseteq\mathcal N$ が 完全集合性質 をもつとは、$A$ が高々可算であるか、空でない完全集合(孤立点のない閉集合)を含むことをいう(完全集合性質 の定義)。これをゲームで捉えるために、Davis の型の次のゲームを使う。
$A\subseteq\mathcal N$ とする。$u_{-1}:=\emptyset$(空列)とおき、$k=0,1,2,\ldots$ の順に次をくり返す。
$A\subseteq\mathcal N$ とする。
$\mathrm{Det}(\Gamma)$ が成り立てば、$\Gamma$ に属する $A\subseteq\mathcal N$ はすべて完全集合性質をもつ。
$A\in\Gamma$ とし、$G^*(A)$ を自然数のゲームに書き直す。$\omega$ から有限列の対の全体への全単射 $e$ を固定する。$z\in\mathcal N$ を $G(\cdot)$ のプレイとみて、I の手 $z(2k)$ を対 $e(z(2k))$、II の手 $z(2k+1)$ を $i_k:=\min(z(2k+1),1)$ と読み、$u_k$ を def-pd-star のとおり順に定める。ただし第 $k$ 回の対が正しい手でない(両立するか、$u_{k-1}$ を始まりにもたない)ときは、それを $(u_{k-1}{}^\frown(0),\,u_{k-1}{}^\frown(1))$ に置き換えて読む。こうして $\Phi(z):=\bigcup_ku_k$ とおくと、$\Phi(z)$ の第 $m$ 項は $z(0),\dots,z(2m+1)$ で決まるので $\Phi$ は連続である。I の手がすべて正しい $z$ の全体を $C$ とすると、正しくない手があることは有限個の項で判定できるので $C$ の補集合は開集合であり、$C$ は閉集合である。$A^*:=C\cap\Phi^{-1}(A)$ は lem-pd-closure により $\Gamma$ に属し、仮定から $G(A^*)$ は決定される。
I が $G(A^*)$ の必勝戦略 $\sigma^*$ をもつとする。$\sigma^*$ は、II のどんな手に対しても正しくない手を出さない(出せばそのプレイは $C$ に属さず I が負ける)。そこで $G^*(A)$ の I は、それまでの対と II の答えを自然数に直して $\sigma^*$ に入れ、返る数 $a$ の対 $e(a)$ を出す。II が $y\in2^\omega$ と答えるとき、対応する $G(A^*)$ のプレイ $z$ は $\sigma^*$ に従うので $z\in A^*$、すなわち $\Phi(z)\in A$ であり、$\Phi(z)$ は $G^*(A)$ の結果に等しい。よって I は $G^*(A)$ で勝ち、lem-pd-davis の 1 により $A$ は空でない完全集合を含む。
II が $G(A^*)$ の必勝戦略 $\tau^*$ をもつとする。$G^*(A)$ の II は、I の対 $(t_0,t_1)$ を数 $e^{-1}(t_0,t_1)$ に直して $\tau^*$ に入れ、返る数 $b$ から $\min(b,1)$ を答える。I が正しい手だけを出す進行は、$C$ に属するプレイ $z$ で $\tau^*$ に従うものに対応するので $z\notin A^*$、すなわち結果 $\Phi(z)\notin A$ であり、II が勝つ。lem-pd-davis の 2 により $A$ は高々可算である。$\square$
痩せた集合(第 1 類集合)と Baire の性質は Baireの性質 の定義による。$\mathcal N$ は完備距離空間なので、Baireのカテゴリー定理 により空でない開集合は痩せていない。次のゲームを使う。
$A\subseteq\mathcal N$ とする。I と II が交互に空でない有限列 $w_0,w_1,w_2,\ldots$ を選び(I が $w_{2k}$、II が $w_{2k+1}$)、それらをつないだ列 $x:=w_0{}^\frown w_1{}^\frown w_2{}^\frown\cdots$ が $A$ に属すれば I の勝ちとする。
これは、開集合を交互に縮めていく Banach–Mazurゲーム を、開基 $N_s$ だけで遊ぶものである。
$G^{**}(A)$ が決定されるなら、$A$ は痩せているか、ある空でない開集合 $U$ について $U\setminus A$ が痩せている。
$\omega^{<\omega}$ の番号づけを 1 つ固定する。空でない開集合 $V$ と有限列 $c$ で $V\subseteq N_c$ となるものについて、$c$ より真に長い $c'$ で $N_{c'}\subseteq V$ となるもの($V$ はある $N_{d}$ を含み、$N_d\subseteq N_c$ なら $d$ は $c$ と両立し、$d$ を延ばせば $c$ より長くできる)のうち番号の最小のものを $c'(V,c)$ と書く。
I が $G^{**}(A)$ の必勝戦略 $\sigma$ をもつとする。Banach–Mazurゲーム $\mathrm{BM}(A)$ で I は、$G^{**}(A)$ の仮想の進行を頭の中で進めながら、つないだ列 $c$ について $N_c$ を出す。最初は $w_0:=\sigma(\emptyset)$、$U_0:=N_{w_0}$ とする。II が $V_n\subseteq U_n=N_c$ を出したら、$c':=c'(V_n,c)$ とし、仮想の II の手を $c'$ から $c$ を除いた残り(空でない)とみて、$\sigma$ の答え $w$ をとり、$U_{n+1}:=N_{c'{}^\frown w}\subseteq V_n$ を出す。つないだ列は真に長くなるので、$\bigcap_nU_n$ は仮想の進行の結果 $x$ だけからなり、$\sigma$ が必勝なので $x\in A$ である。よって I は $\mathrm{BM}(A)$ で勝つ。Banach–Mazurゲーム の定理「プレイヤー I の必勝戦略」の 1($\mathcal N$ は距離化可能)により、ある空でない開集合 $U$ で $U\setminus A$ は痩せている。
II が $G^{**}(A)$ の必勝戦略 $\tau$ をもつとする。$\mathrm{BM}(A)$ で I が $U_n$ を出したら、II はそれまでのつないだ列 $c$(最初は空列)について $c':=c'(U_n,c)$ とし、仮想の I の手を $c'$ から $c$ を除いた残りとみて $\tau$ の答え $w$ をとり、$V_n:=N_{c'{}^\frown w}\subseteq U_n$ を出す。同じく $\bigcap_nV_n$ は仮想の進行の結果 $x$ だけからなり、$x\notin A$ なので II が勝つ。Banach–Mazurゲーム の定理「Oxtoby の定理」により $A$ は痩せている。$\square$
$\mathrm{Det}(\Gamma)$ が成り立てば、$\Gamma$ に属する $A\subseteq\mathcal N$ はすべて Baire の性質をもつ。
空でない有限列の全体から $\omega$ への全単射 $e'$ を固定し、$\Phi'(z):=e'^{-1}(z(0)){}^\frown e'^{-1}(z(1)){}^\frown\cdots$ とおく。$\Phi'$ は連続で、$B\in\Gamma$ なら $\Phi'^{-1}(B)\in\Gamma$(lem-pd-closure で $C=\mathcal N$)である。手の対応は全単射なので、$G(\Phi'^{-1}(B))$ の必勝戦略はそのまま $G^{**}(B)$ の必勝戦略に読み替えられる。よって $\Gamma$ に属するすべての $B$ について $G^{**}(B)$ は決定される。
$A\in\Gamma$ とし、$W:=\bigcup\{N_s\mid N_s\setminus A\text{ は痩せている}\}$ とおく。$W$ は開集合で、$W\setminus A$ は可算個の痩せた集合 $N_s\setminus A$ の和なので痩せている。
$A\setminus W$ も痩せていることを示す。$A\setminus W=A\cap(\mathcal N\setminus W)$ は閉集合との共通部分なので $\Gamma$ に属し、$G^{**}(A\setminus W)$ は決定される。痩せていないとすると、lem-pd-bm によりある空でない開集合で、したがってある $N_s$ で、$N_s\setminus(A\setminus W)$ が痩せている。$N_s\setminus A\subseteq N_s\setminus(A\setminus W)$ も痩せているので、$W$ の定義から $N_s\subseteq W$ であり、$N_s\setminus(A\setminus W)=N_s$ となる。空でない開集合 $N_s$ が痩せることになり、Baireのカテゴリー定理 に反する。
よって $A\mathbin\triangle W=(A\setminus W)\cup(W\setminus A)$ は痩せており、$A$ は Baire の性質をもつ。$\square$
測度についても、Harrington による被覆のゲームを使って同じ形の結果が成り立つ:$\mathrm{Det}(\Gamma)$ のもとで、$\Gamma$ の集合は $\sigma$-有限な Borel 測度について可測である(Mycielski–Świerczkowski、Mos09 6A.17・6A.18、pp. 228–229。この記事では証明しない)。
射影決定性のもとで、$\mathcal N$ の射影集合はすべて完全集合性質と Baire の性質をもつ。特に、非可算な射影集合の濃度は $2^{\aleph_0}$ である。
射影集合はある $\boldsymbol\Sigma^1_n$ に属するので、thm-pd-psp と thm-pd-bp を $\Gamma=\boldsymbol\Sigma^1_n$ に使う。濃度の主張は 完全集合性質 の命題「完全集合性質と連続体仮説」の 2 による。$\square$
この系は射影決定性の全体を使っているわけではない。証明が示すとおり、$\boldsymbol\Sigma^1_n$ 集合の正則性には $\mathrm{Det}(\boldsymbol\Sigma^1_n)$ だけで足りる。
ZFC からは証明できない。 すべての実数が構成可能宇宙 $L$ に属するなら、$\mathcal N$ には非可算で空でない完全集合を含まない $\boldsymbol\Pi^1_1$ 集合と、Baire の性質をもたない $\boldsymbol\Delta^1_2$ 集合がある(Gödel、Addison。Mos09 5A.8、p. 212)。thm-pd-psp によりそのとき $\mathrm{Det}(\boldsymbol\Pi^1_1)$ は成り立たない。すべての実数が構成可能であることは ZFC と無矛盾なので(Mos09 第 5 章の冒頭)、ZFC が無矛盾なら $\mathrm{Det}(\boldsymbol\Pi^1_1)$、まして射影決定性は ZFC からは証明できない。
大きな基数から従う。 Borel 集合のゲームは ZFC で決定される(Martin。Borel決定性)。その一段上の $\boldsymbol\Pi^1_1$ 集合のゲームは、可測基数 があれば決定される(Martin。Nee07 の導入 p. 7 と第 4 節)。さらに次が成り立つ。
$n$ 個の Woodin基数 とそれらより大きい可測基数があれば、$\boldsymbol\Pi^1_{n+1}$ 集合 $A\subseteq\mathcal N$ について $G(A)$ は決定される。したがって無限個の Woodin 基数があれば射影決定性が成り立つ。
Martin と Steel による(MS89)。この記事では前半を証明しない。前半の主張は Nee07 系 5.31(p. 50)による。後半:Woodin 基数 $\delta_1< \delta_2< \cdots$ があるとき、Woodin基数 の定理「可測基数は定常的に現れる」により $\delta_{n+1}$ より下に可測基数が非有界にあるので、$\delta_n$ と $\delta_{n+1}$ の間に可測基数がある。前半を $\delta_1,\dots,\delta_n$ とその可測基数に使えば $\mathrm{Det}(\boldsymbol\Pi^1_{n+1})$ が従い、$n$ は任意である。
射影決定性のもとでは、ZFC で $\boldsymbol\Pi^1_1$ と $\boldsymbol\Sigma^1_2$ について知られていた構造が、射影階層を 2 段ずつ上がってくり返される。代表として一様化を述べる。
$P\subseteq\mathcal N\times\mathcal N$ とする。$P^*\subseteq P$ が $P$ を 一様化する とは、$(x,y)\in P$ となる $y$ がある各 $x$ について、$(x,y)\in P^*$ となる $y$ がちょうど 1 つあることをいう。クラス $\Gamma$ が 一様化の性質 をもつとは、$\Gamma$ に属するどの $P$ も $\Gamma$ に属するある $P^*$ で一様化されることをいう。
一様化する $P^*$ は、関係 $P$ から「$x$ ごとに 1 つの $y$ を選ぶ関数」のグラフを取り出したものである。選択公理によれば $P^*$ はいつでもあるが、一様化の性質は $P^*$ を $P$ と同じ複雑さで選べることを要求する。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $\mathrm{Det}(\Gamma)$(thm-pd-psp、$\Gamma=\boldsymbol\Pi^1_1$) | 実数がすべて構成可能なときの、非可算で空でない完全集合を含まない $\boldsymbol\Pi^1_1$ 集合 | 完全集合性質 |
| I の対が両立しない(lem-pd-davis の 1) | $A=\{x_0\}$ で、I が $x_0$ の始まりの部分を 2 つ出す | I が必勝なら空でない完全集合を含む |
| 対を出して II が一方を選ぶ(lem-pd-davis の 2) | 通常のゲーム $G(A)$、$A=\{x\mid x(1)=0\}$ | II が必勝なら高々可算 |
1 行目:Mos09 5A.8(p. 212)の集合で、$\boldsymbol\Pi^1_1$ に属し非可算なのに完全集合性質をもたない。thm-pd-psp の仮定のうち $\mathrm{Det}(\boldsymbol\Pi^1_1)$ だけが成り立たない。
2 行目:両立する対も許すと、I は第 $k$ 回に $(x_0|(2k+1),\,x_0|(2k+2))$($x_0|m$ は $x_0$ の長さ $m$ の始まりの部分)を出せる。どちらも直前の $u_{k-1}$(長さ $2k$ 以下の $x_0$ の始まりの部分)を延ばし、II がどちらを選んでも結果は $x_0\in A$ なので I が勝つ。しかし $A$ は 1 点で、空でない完全集合を含まない。
3 行目:$G(A)$ で II は最初の手で $x(1)=1$ と選べば勝つので必勝戦略をもつが、$A$ は $N_{(0,0)}$ を含み非可算である。$G^*(A)$ では I が勝つ(I は最初に $((0,0,0),(0,0,1))$ を出し、以後は任意の正しい手を出せば、結果は $(0,0)$ で始まり $A$ に属する)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する