決定性公理
決定性公理(けっていせいこうり、axiom of determinacy、AD と略される)とは、1962年にミシェルスキー、ユゴー・スタインハウスによって提案された集合論の公理である。もとの決定性公理はゲーム理論に言及し、可算無限の長さをもったある特定の二人位相的な完全情報ゲームについて(後述)、どちらかのプレイヤーは必ず必勝法を持つことを主張する。
決定性公理は公理的集合論の選択公理と矛盾する。決定性公理を仮定すると、実数の任意の部分集合について「ルベーグ可測である」「ベールの性質を持つ」「完全集合性を持つ」ことが従う。とくに実数の任意の部分集合が完全集合性を持つことは「実数の部分集合で非可算なものは実数と同じ濃度を持つ」という弱い形の連続体仮説が成り立つことに換言される。
選択公理からは「実数の部分集合でルベーグ可測でないものが存在する」ことが導かれるが、この事実からも決定性公理と選択公理が相容れないことが分かる。
スタインハウスとミシェルスキーが AD を考えた動機はその帰結の興味深さ、そして集合論の最小の自然なモデル L(R) において成り立ちうることにあった。これは選択公理 (AC) の弱い形のみを許容し、全ての実数と全ての順序数を含むものである。AD からのいくつかの帰結はステファン・バナフとスタニスワフ・マズールとモートン・デイビスによってそれまでに得られていた定理から従う。 ミシェルスキーとStanisław Świerczkowskiは次の事実の研究に貢献した: AD は実数からなる集合が全てルベーグ可測であることを導く。 続いて、ドナルド・A・マーティン などによって特に記述集合論において、さらなる重要な結論が得られている。1988年には、ジョン・R・スティール and ヒュー・ウッディン が長期研究の結果を報告している。彼らは \alef_0 と類似な性質をもつ不可算基数の存在を仮定して、ミシェルスキーとスタインハウスがもともと予想していた L(R) において AD が真になるということを示した。
決定性公理は次に示す特定の形のゲームについての公理である:
ベール空間 ωω (自然数の無限列全体) の部分集合 A を考える。二人のプレイヤー I と II は自然数を交互に選ぶ:n0, n1, n2, n3, ...
無限回の手番が終わったとき、列 (n_i)_{i \in \omega} が生成される。プレイヤー I がこのゲームに勝つのは、その列が A の元であるときかつそのときに限る。決定性公理はそのようなゲームが全て決定的 (A の選び方毎にどちらかのプレイヤーに必勝戦略があるということ) であるという主張である。
全てのゲームの決定性を示すために決定性公理が要るわけではない。A が閉かつ開な集合であるとき、このゲームは本質的に有限的なゲームになるので、決定的である。同様に、A が閉集合であるときも決定的である。1975年にはマーティンによって、winning set (勝利条件である集合 A のこと) がボレル集合であるゲームは決定的であることが示されている。また、十分大きな巨大基数があるとき、winning set が射影集合であるゲームは全て決定的であり (Projective determinacy を参照)、しかも L(R) において AD が成り立つことが示されている。
決定性公理は実数直線の任意の部分空間 X についてのバナッハ・マズール・ゲーム BM(X) が決定的である (つまり、実数からなる任意の集合がベールの性質をもつ) ことを導く。
選択公理の仮定のもとで、決定性公理の反例を構成することができる。証明を以下に記す。
まず、ω-game (長さ ω のゲーム) G において戦略とは、「構成されている有限列に対して次の手番で何を続けるか」という動きのルールのことである。戦略の概念自体は winning set が何であるかに関係なく、定義することができる。選択公理のもとで、戦略全体の集合は連続体濃度をもつ。
集合 S1 をプレイヤー I が採用しうる戦略全ての集合とし、S1 = {s1(α) : α < 2ω }と整列する。集合 S2 をプレイヤー II について同様に定義し、S2 = {s2(α) : α < 2ω }とする。
ここから超限再帰によって決定的でない集合 A = {A(α) : α < 2ω } を構成していく。つまり、A をプレイヤー I の winning set とするゲームを考えると必勝戦略が無いようにしようということである。同時に、A の構成の補助のために B = {B(α) : α < 2ω }を A と交わらないように構成していく。:
α < 2ω とし、{A(β) : β < α}と{B(β) : β < α}まで構成されているとする。
B(α)をプレイヤー I が s1(α) に従ってゲームで構成できうる列のうち、{A(β) : β < α}に属さないものとする。これは可能である。というのも、プレイヤー II の動きの選び方の濃度は連続体濃度であって、この時点までにできている A の濃度より大きいからである。
A(α)をプレイヤー II が s2(α) に従ってゲームで構成できうる列のうち、{B(β) : β \le α}に属さないものとする。これは可能である。というのも、プレイヤー I の動きの選び方の濃度は連続体濃度であって、この時点までにできている B の濃度より大きいからである。
以上のプロセスを S1 と S2 の全ての戦略に対して順に実行し終わったとする。このとき、 A と B のどちらにも入っていない自然数列が存在するなら、その全体による集合を C とする。これにより、B ∪ C は A の補集合となる。
A の構成が終わったところで、A をプレイヤー I の winning set とする ω-game G を改めて考える。プレイヤー I の戦略 s1 を任意に取ると、ある α < 2ω に対して s1 = s1(α) となり、A の構成によりプレイヤー I が s1(α) に従う限りプレイヤー II の選択により B(α) をゲームの結果として構成できて、これは A から逃れている。よって s1 は戦略として必勝戦略ではない。同様にして、プレイヤー II のいかなる戦略も必勝戦略ではないことが分かる。よって A を winning set と定めたこのゲームは両プレイヤーに必勝戦略が存在せず、決定的でない。よって、決定性公理と選択公理は共存できない。
無限論理のいくつものバージョンが20世紀の終わりに提案されている。決定性公理を信じる理由の一つは、それが無限論理によって次のように書けることである:
\forall G \subseteq Seq(S):
\forall a \in S: \exists a' \in S: \forall b \in S: \exists b' \in S: \forall c \in S: \exists c' \in S ... : (a,a',b,b',c,c'...) \in G  OR
\exists a \in S: \forall a' \in S: \exists b \in S: \forall b' \in S: \exists c \in S: \forall c' \in S ... :(a,a',b,b',c,c'...) \notin G
注意: Seq(S) は S の元の \omega-列全体である。S を ω で置き換えて、G が winning set と解釈すればよい。ここでの文は無限の長さを持っていて、可算無限個の量化子が "..." で省略されている部分に入っている。
決定性公理の無矛盾性は巨大基数公理の無矛盾性についての問題と密接に関係している。Woodin の定理によって、ZF に AD を加えた公理系の無矛盾性は ZFC に無限個のウッディン基数の存在性を加えた公理の無矛盾性と等価である。ウッディン基数は強到達不能基数でもあるので、AD が無矛盾なら無限個の強到達不能基数の存在も無矛盾であることになる。
その上、無限個のウッディン基数とその全てより大きい可測基数が存在するとき、L(R) において決定性公理が証明できる。このとき L(R) における実数からなる集合は全て決定的になり、ルベーグ測度の非常に強い理論が発生する。
モシュコヴァキスは順序数 \delta_n^1 を導入した。これは\boldsymbol\Delta_n^1-ノルムの長さの上限である。ここで、\boldsymbol\Delta_n^1 は射影階層のレベルである。AD を仮定すると、全ての \delta_n^1 は 始順序数 となり、\delta_{2n+2}^1=(\delta_{2n+1}^1)^+ となる。そして、n<\omega について 2n 番目のススリン基数は \delta_{2n-1}^1 に等しくなる。