決定性

決定性は、数学の一分野である集合論のサブフィールドであり、ゲームのどちらかのプレイヤーが勝利戦略を持つ条件と、そのような戦略の存在の結果を検討します。あるいは同様に、「決定性」は、そのような戦略が存在するゲームの特性です。決定性は、1950年にゲイルとスチュワートによって「決定性」という名前で導入されました。^[1]

集合論で研究されるゲームは通常、ゲール・スチュワート ゲーム、つまり、プレイヤーが無限のシーケンスの動きを行い、引き分けがない、完全情報の 2 人用ゲームです。ゲーム理論の分野では、三目並べ、チェス、無限チェスなどの引き分けのあるゲームや、ポーカーなどの不完全情報ゲームなど、より一般的な種類のゲームを研究します。

最初に検討するゲームは、長さωの完全情報を持つ2人用ゲームで、プレイヤーは自然数を扱う。これらのゲームはしばしばゲイル・スチュワートゲームと呼ばれる。^[2]

この種のゲームでは、2 人のプレーヤー (多くの場合IとIIと呼ばれます) が交代で自然数をプレイし、Iが先攻になります。プレーヤーは「永遠に」プレイします。つまり、プレーヤーのプレイは自然数でインデックス付けされます。プレーヤーが終了すると、事前に決められた条件によってどちらのプレーヤーが勝ったかが決定されます。この条件は、定義可能なルールで指定する必要はなく、特定のプレイ シーケンスで誰が勝ったかを示す任意の (無限に長い) 参照テーブルでかまいません。

より正式には、ベール空間の部分集合Aを考えます。ベール空間は自然数の ω 列すべてから構成されることを思い出してください。ゲーム G _Aでは、 I が自然数a ₀をプレイし、II が₁をプレイし、I が₂をプレイする、というように続きます。Iがゲームに勝つには、次の条件を満たす必要があります。

${\displaystyle \langle a_{0},a_{1},a_{2},\ldots \rangle \in A}$

そうでなければIIが勝ちます。A _はG Aのペイオフセットと呼ばれます。

各プレイヤーは自分の動きの前に行われるすべての動きを見ることができ、勝利条件も知っているものと想定されます。

非公式には、プレーヤーの戦略とは、そのプレーヤーのプレイが前述のプレイによって完全に決定されるプレイ方法です。また、このような「方法」は、説明可能な「ルール」によって捕捉可能である必要はなく、単に参照テーブルである可能性があります。

より正式には、プレイヤーIの戦略(前のサブセクションの意味でゲームの場合) は、偶数の長さの任意の有限の自然数列を引数として受け取り、自然数を返す関数です。σ がそのような戦略であり、<a 0 ,...,a 2n-1 > がプレイのシーケンスである場合、 Iが戦略σに従っている場合、σ ( <a 0 ,...,a 2n-1 > _{) は}私が行う次のプレイです。II の戦略は、「偶数」を「奇数」に置き換えただけです。

これまでのところ、戦略が何らかの点で優れているかどうかについては何も述べていないことに注意してください。戦略は、プレイヤーに積極的に悪い動きをするように指示するかもしれませんが、それでもそれは戦略です。実際、ゲームにどのような戦略が存在するかを知るために、ゲームの勝利条件を知る必要さえありません。

ある戦略が勝っているとは、その戦略に従うプレイヤーが、対戦相手が何をプレイしても必ず勝てるということを意味する。例えば、σ がIの戦略である場合、ゲーム G _AにおいてσがIの勝利戦略であるとは、 IIがプレイする任意の自然数列、たとえば<a 1 ,a 3 ,a 5 ,...>_{に対して、} II が次のようにプレイしたときにσによって生成されるプレイの列、すなわち

${\displaystyle \langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle }$

はAの要素です。

ゲーム（のクラス）は、ゲームのすべてのインスタンスにおいて、プレイヤーの 1 人が勝利する戦略がある場合に決定されます（各インスタンスで同じプレイヤーである必要はありません）。 ^{[3]同じゲームで}両方のプレイヤーが勝利する戦略はあり得ません。なぜなら、もしあったとしたら、2 つの戦略を互いに対戦させることができるからです。その結果、仮説によれば、両方のプレイヤーが勝利することになりますが、これは不可能です。^[4]

引き分けが発生しない完全情報の有限ゲームがすべて決定されます。

三目並べ、チェス、無限チェスなど、現実世界の完全情報ゲームは、常に有限回数の手で終了します（無限チェスゲームでは、50手ルールが適用されると想定されます）。そのようなゲームが、引き分けと呼ばれるような状況でも特定のプレーヤーが勝つように変更された場合、そのゲームは常に決定されます。^{[4]有限回数の手でゲームが常に終了するという条件（つまり、有限位置のすべての可能な拡張が同じプレーヤーの勝利につながる）は、G} _Aの勝利条件を与える集合Aがベール空間の位相で閉開であるという位相条件に対応します。

例えば、チェスのルールを変更して、引き分けは黒の勝ちになるようにすると、チェスは決着のついたゲームになります。^[5]偶然にも、チェスには有限の数の局面と繰り返し引き分けのルールがあるため、これらの変更されたルールでは、白が勝つことなくゲームが十分長く続くと、黒は最終的に勝利を強制することができます（引き分け = 黒の勝利に変更されるため）。

このようなゲームが決定的であることの証明は、かなり簡単です。プレイヤーI は単に負けないようにプレイします。つまり、プレイヤーI は、自分の移動後にプレイヤーII が勝利戦略を持たないようにプレイします。プレイヤーI がこれを実行できない場合は、プレイヤーIIが最初から勝利戦略を持っていたことを意味します。一方、プレイヤーI がこのようにプレイできる場合は、有限回数の移動後にゲームが終了し、その時点でプレイヤーIが負けることはないため、私が勝つ必要があります。

この証明は、実際にはゲームが常に有限回数の手で終わることを要求しているわけではなく、II が勝つときは常に有限回数の手で終わることだけを要求しています。その条件は、位相的には、集合Aが閉じていることです。この事実、つまりすべての閉じたゲームは決定されているという事実は、ゲイル・スチュワートの定理と呼ばれます。対称性により、すべてのオープンゲームも決定されていることに注意してください。(有限回数の手で勝つことによってのみ勝つことができる 場合、ゲームはオープンです。)

デビッド・ゲイルと FM スチュワートは、オープン ゲームとクローズド ゲームが決定的であることを証明しました。ボレル階層ゲームの第 2 レベルの決定性は、1955 年にウルフによって示されました。その後 20 年間にわたって、さらに複雑な議論を用いた追加の研究により、ボレル階層の第 3 レベルと第 4 レベルが決定的であることが確立されました。^[指定]

1975年、ドナルド・A・マーティンはすべてのボレルゲームが決定的であることを証明した。 ^[6]つまり、Aがベール空間のボレル部分集合であれば、G _Aは決定される。この結果はボレル決定性と呼ばれ、ZFCで証明可能な最良の決定性結果である。つまり、次に高いワッジ類の決定性はZFCでは証明できない ということである。

1971年、マーティンが証明を得る前に、ハーヴェイ・フリードマンは、ボレルの決定性の証明は、冪集合公理を超限的に何度も反復するために、本質的には置換公理を使用しなければならないことを示した。フリードマンの研究は、ボレル階層の各レベルで決定性を保証するために冪集合公理を何回反復する必要があるかを詳細に示すレベルごとの結果を示している。

ZFC\P は、任意の整数nに対して、集合の差分階層のn番目のレベルで決定性を証明しますが、任意の整数 n に対して、集合の差分階層のn番目のレベルが決定されていることを証明しません。決定性と2 次算術のサブシステム間のその他の関係については、逆数学を参照してください。 ${\displaystyle \mathbf {\Pi } _{3}^{0}}$ ${\displaystyle \Pi _{3}^{0}}$

決定性と大基数の間には密接な関係があります。一般に、より強い大基数の公理は、ワッジ階層のより高い、より大きな点クラスの決定性を証明し、そのような点クラスの決定性は、最初に点クラスの決定性を証明するために使用されるものよりもわずかに弱い大基数の公理の内部 モデルの存在を証明します。

測定可能な基数の存在から、すべての解析ゲーム ( Σ ¹ ₁ゲームとも呼ばれる) は決定的であること、または同等に、すべての共解析ゲーム (またはΠ ¹ ₁ ) は決定的であることがわかります。(定義については射影階層を参照してください。)

実際には、測定可能な基数は十分すぎるほどです。より弱い原理、つまり0 ^#の存在は、共解析的決定性を証明するのに十分であり、さらにもう少し証明する必要があります。正確な結果は、 0 ^{#の存在が、 ω 2}レベルより下の差分階層のすべてのレベルの決定性、つまりすべてのω·n- Π ¹ ₁決定性と同等であるということです。 ${\displaystyle n}$

^{測定可能な基数から、これを ω 2} - Π ¹ _{1 の}決定性にわずかに改善することができます。より多くの測定可能な基数の存在から、 Π ¹ ₁上の差分階層のより多くのレベルの決定性を証明できます。

すべての実数rについて、決定性はr ^#の存在と同等です。大きな基数がどのように決定性につながるかを示すために、 r ^#の存在を前提とした決定性の証明を示します。 ${\displaystyle \Sigma _{1}^{1}(r)}$${\displaystyle \Sigma _{1}^{1}(r)}$

A をベール空間のサブセット とします。(ω, ω) 上の何らかの木T ( rから構成可能)に対してA = p[ T ] です。(つまり、 x∈A であるためには、何らかのyからT を通るパスである必要があります。) ${\displaystyle \Sigma _{1}^{1}(r)}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...)}$

部分プレイsが与えられたとき、をsと矛盾せず、max(y ₀ ,y ₁ ,...,y _{len(s)-1 )<len(s) を満たす}Tのサブツリーとします。追加条件により、 が有限であることが保証されます。一貫性とは、 を通るすべてのパスが の形式であり、 がsの初期セグメントであることを意味します。 ${\displaystyle T_{s}}$${\displaystyle T_{s}}$${\displaystyle T_{s}}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))}$${\displaystyle (x_{0},x_{1},...,x_{i})}$

Aが決定されていることを証明するために、補助ゲームを次のように定義する。通常の動きに加えて、プレイヤー2は、十分に大きい順序数κ
以下の順序数へ のマッピングを行う必要がある。 ${\displaystyle T_{s}}$

• それぞれの新しい動きは以前のマッピングを拡張し、
• 順序数の順序は上のクリーネ・ブラウワー順序と一致する。${\displaystyle T_{s}}$

Kleene–Brouwer 順序は辞書式順序に似ていますが、s がt を適切に拡張する場合はs < t となる点が異なります。これは、木が整列している場合に限り、整列順序です。

補助ゲームはオープンです。 証明:プレイヤー 2 が有限段階で負けない場合、すべての和集合(プレイに対応するツリー) は整基礎であるため、補助ゲーム以外のプレイの結果は A に含まれません。 ${\displaystyle T_{s}}$

こうして、補助ゲームが決定されます。証明:超限帰納法によって、各順序数 α に対して、プレーヤー 1 が α ステップで勝利を強制できるポジションの集合を計算します。ここで、プレーヤー 2 が動くポジションが (プレーヤー 2 にとって) α ステップで負けとなるのは、すべての動きに対して、結果として生じるポジションが α ステップ未満で負けとなる場合に限られます。プレーヤー 1 の戦略の 1 つは、ポジションごとに α を減らすこと (つまり、最小の α を選び、同点の場合は最小の動きを選ぶ) であり、プレーヤー 2 の戦略の 1 つは、α が割り当てられたポジションにつながらない最小の動き (実際にはどの動きでもかまいません) を選ぶことです。L ( r ) には、上記の勝利戦略だけでなく、勝利ポジションの集合も含まれること に注意してください。

元のゲームでのプレイヤー 2 の勝利戦略は、補助ゲームでの勝利戦略につながります。勝利戦略に対応する T のサブツリーは整基礎であるため、プレイヤー 2 はツリーの Kleene–Brouwer 順序に基づいて順序数を選択できます。また、当然のことながら、補助ゲームでのプレイヤー 2 の勝利戦略は、元のゲームでのプレイヤー 2 の勝利戦略につながります。

残っているのは、 r ^{# を}使用して、補助ゲームでのプレイヤー 1 の上記の勝利戦略を、元のゲームでの勝利戦略に変換できることを示すことです。 r ^{# は}、 ( L ( r ),∈, r )の識別不可能な順序数の適切なクラスI を提供します。識別不可能性により、κと補助応答の順序数がIに含まれる場合、プレイヤー 1 の動きは補助的な動き (またはκ ) に依存せず、そのため、戦略を元のゲームの戦略に変換できます (プレイヤー 2 は、任意の有限数のステップで識別不可能な状態で持ちこたえることができるため)。 プレイヤー 1 が元のゲームで負けたと仮定します。その場合、プレイに対応するツリーは整基礎です。したがって、プレイヤー 2 は、識別不能なものに基づいて補助的な動きを使用して補助ゲームに勝つことができます (識別不能なものの順序タイプがツリーの Kleene-Brouwer 順序を超えているため)。これは、プレイヤー 1 が補助ゲームに勝つことと矛盾します。

Woodin 基数とその上に測定可能な基数がある場合、Π ¹ _{2決定性が成り立ちます。より一般的には、} n 個のWoodin 基数とその上に測定可能な基数がある場合、 Π ¹ _n+1 決定性が成り立ちます。Π 1 n+1 決定性から、_n個^のWoodin 基数を含む推移的な内部モデルが存在することがわかります。

${\displaystyle \Delta _{2}^{1}}$(lightface) 決定性は Woodin 基数と等価です。決定性が成り立つ場合、 xのチューリング円錐(つまり、十分に高いチューリング次数を持つすべての実数xに対して) に対して、L[ x ] は OD 決定性 (つまり、長さ ω の整数と順序数で定義可能なペイオフのゲームの決定性) を満たし、HOD では^{L[ x ]}は Woodin 基数です。 ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle \omega _{2}^{L[x]}}$

ウッディン基数が無限にある場合、射影決定性が成り立ちます。つまり、勝利条件が射影集合であるすべてのゲームが決定されます。射影決定性から、すべての自然数nに対して、 n 個のウッディン基数 があることを満たす推移的な内部モデルが存在することがわかります。

決定性公理、またはAD は、長さ ω の完全情報を持つ、プレイヤーがナチュラルをプレイするすべての2 人用ゲームは決定的であると主張します。

AD は ZFC から証明可能な誤りです。選択公理を使用すると、非決定ゲームの存在を証明できます。ただし、すべての上に測定可能なものを持つ Woodin 基数が無限に存在する場合、L(R) はAD を満たす ZFのモデルです。

Aがベール空間の部分集合で、Aに対するバナッハ-マズールゲームが決定されている場合、 II に勝利戦略があり、その場合A は貧弱であるか、I に勝利戦略があり、その場合Aはある開近傍^[1]上のコマージャーであるかのいずれかです。

これは、 A がBaire の性質を持つことを完全に意味するわけではありませんが、それに近いものです。議論を単純に修正すると、 Γ が適切な点クラスであり、 Γ 内のすべてのゲームが決定されている場合、 Γ 内のすべての実数集合は Baire の性質を持つことが示されます。

実際、この結果は最適ではありません。展開されたバナッハ-マズール ゲームを考慮すると、Γ の決定性 (十分な閉包特性を持つ Γ の場合) は、 Γ 内の集合の射影であるすべての実数集合が Baire 特性を持つことを意味することがわかります。したがって、たとえば、測定可能な基数の存在はΠ ¹ ₁決定性を意味し、これはすべてのΣ ¹ ₂実数集合が Baire 特性を持つことを意味します。

他のゲームを考慮すると、Π ¹ _{n の}決定性は、すべてのΣ ¹ _{n +1 個}の実数集合がベールの性質を持ち、ルベーグ測定可能（実際には普遍的に測定可能）であり、完全集合の性質を持つことを意味することがわかります。

• 第一周期性定理は、あらゆる自然数nに対して、Δ ¹ _{2 n +1}決定性が成り立つ場合、Π ¹ _{2 n +1}とΣ ¹ _{2 n +2は}前井戸順序付け特性を持つこと（そしてΣ ¹ _{2 n +1}とΠ ¹ _{2 n +2は前井戸順序付け特性を}持たず、むしろ分離特性を持つこと）を意味します。
• 第二周期性定理は、_任意の自然数nに対して、Δ12n+1の決定性が成り立つ場合、_{Π12n +} ¹_とΣ12nはスケール特性_を持つことを^意味します。^[7] 特に、射影的決定性が成り立つ場合、すべての射影関係には_射影^的均一化があり_ます。
• 3番目の周期性定理は、ゲームが定義可能な勝利戦略を持つための十分な条件を示します。

1969年、マイケル・O・ラビンは、 n個の後継者のモナドの2階理論（n = 2の場合S2S ）が決定可能であることを証明しました。^[8]証明の重要な要素は、ボレル階層の第3レベルにあるパリティゲームの決定性を示すことです。

ワッジ決定性とは、ベール空間の部分集合のすべてのペアA、Bに対して、ワッジゲームG( A、B ) が決定されるという主張です。同様に、点クラスΓ の場合、 Γ ワッジ決定性とは、 Γ 内のすべての集合A、Bに対して、ワッジゲーム G( A、B ) が決定されるという主張です。

ワッジ決定性は、ワッジ順序に対する半線形順序原理を意味します。ワッジ決定性のもう 1 つの結果は、完全集合の性質です。

一般に、Γ ワッジ決定性は、Γ 内の集合のブール結合の決定性の結果です。射影階層では、Π ¹ ₁ワッジ決定性は、Leo Harringtonによって証明されたように、 Π ¹ ₁決定性と同等です。この結果は Hjorth によって拡張され、Π ¹ _{2ワッジ決定性 (および実際には}Π ¹ ₂の半線形順序付け原理) がすでにΠ ¹ ₂決定性を意味することが証明されました。

順序数で定義可能な利得と長さ ω を持つ順序数上のゲームの決定性は、すべての正規基数κ >ω に対して、共終性 ω の順序数で構成されるκの順序数で定義可能な互いに素な定常部分集合が存在しないことを意味します。決定性仮説の一貫性の強さは不明ですが、非常に高いことが期待されます。

ω ₁ウッドイン基数の存在は、すべての可算順序数 α に対して、長さ α の整数と射影的利得に関するすべてのゲームが決定的であることを意味します。大まかに言えば、α ウッドイン基数は、長さ α の実数 (単純な利得集合を持つ) に関するゲームの決定性に対応します。o( κ )= κ ⁺⁺でウッドイン基数κの極限と、 κを超える ω ウッドイン基数を想定すると、ゲームの長さがプレイのラインに対して許容可能になるとすぐにゲームが終了する、可変の可算長さのゲームが決定され、射影的利得が実現されます。特定の反復可能性予想が証明可能であると想定すると、測定可能なウッドイン基数の存在は、長さ ω ₁のオープンゲームと射影的利得の決定性を意味します。(これらのゲームでは、最初のプレーヤーの勝利条件は可算な段階でトリガーされるため、利得は実数の集合としてコード化できます。)

ウッディン基数のウッディン限界とそれより上の測定可能値と関連して、長さ ω ₁の整数と順序定義可能なペイオフに関するすべてのゲームが決定されていることは矛盾しません。決定性仮説はウッディン基数のウッディン限界と等しく矛盾しないと推測されます。ω _{1 は、長さ ω 1} +ω の整数と順序定義可能なペイオフ に関する未決定のゲームが存在するという点で最大です。

不完全情報を伴う興味深いゲームでは、勝利戦略は混合戦略となる。つまり、同じ状況に対して異なる反応をする確率がいくらかあるということである。両方のプレイヤーの最適戦略が混合戦略である場合、ゲームの結果は確実に決定的になることはできない（純粋戦略の場合は決定論的であるため可能である）。しかし、対立する混合戦略の結果の確率分布を計算することはできる。混合戦略を必要とするゲームは、与えられた値を超える最小期待値（可能な対抗戦略に対して）をもたらす戦略が存在する場合に決定的であると定義される。この定義に対して、有限の2人プレイのゼロサムゲームはすべて明らかに決定的である。しかし、不完全情報の無限ゲーム（ブラックウェルゲーム）の決定性はそれほど明確ではない。^[9]

1969年、デイビッド・ブラックウェルは「不完全情報を伴う無限ゲーム」（現在「ブラックウェルゲーム」と呼ばれる）が決定的であることを証明し、1998年にドナルド・A・マーティンは、太字のポイントクラスに対する通常の（完全情報ゲーム）決定性は、ポイントクラスに対するブラックウェル決定性を意味することを証明した。これは、マーティンのボレル決定性定理と組み合わせると 、ボレルの利得関数を持つすべてのブラックウェルゲームが決定的であることを意味する。^{[10] [11]}マーティンは、無限ゲームに対する通常の決定性とブラックウェル決定性は強い意味で同等であると推測した（つまり、太字のポイントクラスに対するブラックウェル決定性は、今度はそのポイントクラスに対する通常の決定性を意味する）が、2010年現在、ブラックウェル決定性が完全情報ゲーム決定性を意味することは証明されていない。^[12]

• ω-オートマトン
• 解決したゲーム
• 厳密に決められたゲーム
• 位相ゲーム

1. ^ これは、 Iがプレイされた近傍の共通部分を、一意の要素がAの要素であるシングルトンにしようとしていることを前提としています。一部の著者は、代わりにそれをプレイヤーIIの目標としています。その使用法では、上記のコメントをそれに応じて修正する必要があります。

• ゲイル、デイビッド、スチュワート、FM (1953)。「完全情報による無限ゲーム」。クーン、ハロルド・ウィリアム、タッカー、アルバート・ウィリアム (編)。ゲーム理論への貢献。数学研究年報。第 28 巻。プリンストン、ニュージャージー: プリンストン大学出版局。pp. 245–266。ISBN 978-0-691-07935-6。
• Harrington, Leo (1978 年 1 月). 「解析的決定性と 0#」. The Journal of Symbolic Logic . 43 (4): 685–693. doi :10.2307/2273508. JSTOR  2273508. S2CID  46061318.
• Hjorth, Greg (1996年1月). 「Π12 ワッジ度」. Annals of Pure and Applied Logic . 77 : 53–74. doi : 10.1016/0168-0072(95)00011-9 .
• ジェック、トーマス(2002)。集合論、第三千年紀版 (改訂・拡張版)。シュプリンガー。ISBN 978-3-540-44085-7。
• マーティン、ドナルド A. (1975)。「ボレルの決定性」。数学年報。第 2 シリーズ。102 ( 2): 363–371。doi :10.2307 / 1971035。JSTOR  1971035。
• Martin, Donald A.およびJohn R. Steel ( 1989年 1 月) 。「射影的決定性の証明」。アメリカ数学会誌。2 (1): 71–125。doi : 10.2307/1990913。JSTOR  1990913 。
• モスコヴァキス、ヤニス・N. (1980)。記述的集合論。ノースホランド。ISBN 978-0-444-70199-2。
• Woodin , W. Hugh (1988). 「超コンパクト基数、実数集合、弱同次木」。米国科学アカデミー紀要。85 (18): 6587–6591。Bibcode : 1988PNAS ... 85.6587W。doi : 10.1073/ pnas.85.18.6587。PMC 282022。PMID  16593979 。 
• Martin, Donald A. (2003). 「決定性はルベーグ測定可能性を意味するという簡単な証明」Rend. Sem. Mat. Univ. Pol. Torino . 61 (4): 393–399. （PDF）
• ウルフ、P. ( 1955)。「特定の無限ゲームの厳密な決定性」。パシフィックJ.数学。5 （5）：補足I：841-847。doi ：10.2140 / pjm.1955.5.841。

• スタンフォード哲学百科事典の「大きな基数と決定性」