ボレルの決定性定理

記述的集合論におけるボレルの決定性定理は、利得集合がボレル集合であるゲール・スチュワートゲームは決定的であると述べており、これは 2 人のプレイヤーのうちの 1 人がそのゲームで勝利する戦略を持っていることを意味する。ゲール・スチュワートゲームは、両方のプレイヤーが完全な情報を持ち、ランダム性が関与しない、おそらく無限の 2 人用ゲームである。

この定理は有限ゲームの決定性に関するツェルメロの定理を広範囲に一般化したものである。これは 1975 年にドナルド A. マーティンによって証明され、記述集合論においてポーランド空間のボレル集合が完全集合特性などの規則性特性を持つことを示すために適用されている。

この定理は、そのメタ数学的性質でも知られています。定理が証明される前の 1971 年に、ハーヴェイ・フリードマンは、ツェルメロ-フランケル集合論における定理の証明は、置換公理スキームのインスタンスを繰り返し使用する必要があることを示しました。その後の結果では、より強い決定性定理は、特定の大きな基数が一致する場合、ツェルメロ-フランケル集合論と比較的一致するものの、ツェルメロ-フランケル集合論では証明できないことが示されました。

背景

ゲイル・スチュワートゲーム

ゲイル・スチュワートゲームは、2 人のプレイヤーが完全情報を扱うゲームです。ゲームは集合A を使用して定義され、G _Aと表記されます。2 人のプレイヤーは交互に手番を行い、各プレイヤーは次の手番を行う前にすべての手番を把握しています。各手番で、各プレイヤーはAの 1 つの要素を選択してプレイします。同じ要素を複数回選択しても制限はありません。ゲームは次の図で視覚化できます。この図では、手番は左から右に行われ、プレイヤー I の手番が上に、プレイヤー II の手番が下に表示されます。

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{matrix}}$

ゲームは終わりなく続くため、ゲームを 1 回プレイすると、Aの要素の無限シーケンスが決定されます。このようなシーケンスすべての集合は、A ^ωで示されます。プレイヤーは、ゲームの開始時から、誰が勝つかを決定する固定のペイオフセット(別名、勝利セット) を認識しています。ペイオフセットは、A ^ωのサブセットです。ゲームのプレイによって作成された無限シーケンスがペイオフセット内にある場合、プレイヤー I が勝ちます。そうでない場合は、プレイヤー II が勝ちます。同点はありません。 $\langle a_{1},a_{2},a_{3}\ldots \rangle$

この定義には、チェスなどの伝統的な完全情報ゲームは含まれていないように思われます。なぜなら、そのようなゲームでは、利用可能な動きのセットが毎ターン変化するからです。しかし、この種のケースは、不正な動きをしたプレイヤーは即座に負けると宣言することで対処できるため、ゲール・スチュワートのゲームの概念は、実際にはゲームツリーによって定義されるゲームの概念を一般化しています。

勝利の戦略

プレイヤーの勝利戦略とは、ゲームのどの位置からでもプレイヤーにどのような動きをするかを伝える関数であり、プレイヤーがその関数に従えば確実に勝利する。より具体的には、プレイヤーIの勝利戦略は、Aの偶数長の要素のシーケンスを入力として受け取り、Aの要素を返す関数fであり、プレイヤーIは次の形式のプレイごとに勝利する。

${\begin{matrix}\mathrm {I} &a_{1}=f(\langle \rangle )&\quad &a_{3}=f(\langle a_{1},a_{2}\rangle )&\quad &a_{5}=f(\langle a_{1},a_{2},a_{3},a_{4}\rangle )&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots .\end{matrix}}$

プレイヤーIIの勝利戦略は、 Aの要素の奇数長のシーケンスを受け取り、 Aの要素を返す関数gであり、プレイヤーIIは次の形式のプレイごとに勝利する。

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}=g(\langle a_{1}\rangle )&\quad &a_{4}=g(\langle a_{1},a_{2},a_{3}\rangle )&\quad &a_{6}=g(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )&\cdots .\end{matrix}}$

勝利戦略を持つことができるのは最大で 1 人のプレイヤーです。両方のプレイヤーが勝利戦略を持ち、お互いにその戦略を実行した場合、そのゲームのプレイで勝利できるのは 2 つの戦略のうちの 1 つだけです。プレイヤーの 1 人が特定の報酬セットに対して勝利戦略を持っている場合、その報酬セットは決定されていると言われます。

トポロジー

与えられた集合Aに対して、 A ^ωの部分集合が決定されるかどうかは、ある程度、その位相構造に依存します。ゲール・スチュワートゲームの目的では、集合Aには離散位相が与えられ、A ^ωには結果の積位相が与えられます。ここで、A ^ωはAとそれ自身の可算無限位相積とみなされます。特に、Aが集合 {0,1} のとき、A ^{ω上で定義される位相は、}カントール空間上の通常の位相とまったく同じであり、Aが自然数の集合のとき、それはベール空間上の通常の位相です。

集合A ^{ω は、ある}木を通る経路の集合とみなすことができ、これにより、その位相の 2 つ目の特徴付けが導かれます。木はAの要素のすべての有限シーケンスで構成され、木の特定のノード σ の子は、まさに σ を 1 つの要素で拡張したシーケンスです。したがって、A = {0, 1 } の場合、木の最初のレベルはシーケンス ⟨ 0 ⟩ と ⟨ 1 ⟩ で構成され、2 番目のレベルは 4 つのシーケンス ⟨ 0, 0 ⟩、⟨ 0, 1 ⟩、⟨ 1, 0 ⟩、⟨ 1, 1 ⟩ などで構成されます。木内の有限シーケンス σ のそれぞれについて、σ で始まるA ^{ωのすべての要素の集合は、}A上の位相における基本的な開集合です。A ^ωの開集合は、まさにこれらの基本開集合の和集合として表現できる集合です。閉集合は、通常どおり、その補集合が開いている集合です。

A ^ωのボレル集合は、開集合を含み、補集合と可算和集合の下で閉じているA ^ωの部分集合の最小のクラスです。つまり、ボレル集合は、すべての開集合を含むA ^ωの部分集合の最小のσ 代数です。ボレル集合は、開集合から生成するのに補集合と可算和集合の演算が何回必要かに基づいて、ボレル階層に分類されます。

過去の結果

ゲイルとスチュワート (1953) は、ペイオフセットがA ^ωの開集合または閉集合である場合、そのペイオフセットを持つゲイル–スチュワートゲームは常に決定されることを証明しました。その後 20 年間で、この証明はさらに複雑な証明を経て、ボレル階層のわずかに高いレベルにまで拡張されました。これにより、ペイオフセットがA ^ωのボレルサブセットである場合は常にゲームが決定される必要があるかどうかという疑問が生じました。選択公理を使用すると、決定されていない {0,1} ^ωのサブセットを構築できることがわかっていました(Kechris 1995、p. 139)。

ハーヴェイ・フリードマン(1971) は、カントール空間 ({0,1} ^ω ) のすべてのボレル部分集合が決定されていることの証明には、置換公理スキームのインスタンスを繰り返し使用する必要があることを証明しました。この公理は、カントール空間などの「小さな」構造に関する、明示的に「集合論的」ではない (つまり、公理的集合論を探求する目的で構築された) 定理を証明するために通常は必要とされない公理です。

ボレル決定性

ドナルド A. マーティン(1975) は、任意の集合Aに対して、 A ^ωのすべてのボレル部分集合が決定されることを証明しました。最初の証明は非常に複雑だったため、マーティンは 1982 年に、それほど技術的な仕組みを必要としないより短い証明を発表しました。マーティンの論文のレビューで、ドレイクは 2 番目の証明を「驚くほど簡単」と評しています。

記述集合論の分野では、ポーランド空間（本質的には、完全に分離可能な距離空間）の性質を研究する。ボレルの決定性定理は、これらの空間のボレル部分集合の多くの^{[出典が必要]}性質を確立するために使用されてきた。たとえば、ポーランド空間のすべての解析的部分集合は、完全集合の性質、ベールの性質、およびルベーグ測定可能であるを持つ。ただし、最後の 2 つの性質は、ボレルの決定性を使用せずに、測定可能な集合またはベールの性質を持つ集合の σ 代数がススリン演算 ${\mathcal {A}}$ の下で閉じていることを示すことによって、より簡単に証明できる。

集合論的側面

ボレルの決定性定理は、そのメタ数学的性質だけでなく、記述的集合論における結果でも興味深いものです。

任意のAに対するA ^ωの閉集合の決定性は、ZF上の選択公理と同等です(Kechris 1995、p. 139)。選択公理が想定されていない集合論的システムで作業する場合、準戦略と呼ばれる一般化された戦略 (Kechris 1995、p. 139) を考慮するか、決定性公理のように、 A が自然数の集合であるゲームのみを考慮することで、これを回避できます。

ツェルメロ集合論(Z) は (大まかに言えば)置換公理スキームのないツェルメロ・フランケル集合論である。ZF と異なる点の 1 つは、任意の無限集合から始めてべき集合演算を無限回反復できることを証明しない点である。特に、可算ランクを持つ累積階層の特定のレベルであるV _{ω + ω}は、ツェルメロ集合論のモデルである。一方、置換公理スキームは、 κ が強く到達不可能な基数である場合など、κ の値が著しく大きい場合にのみV _κによって満たされる。1971 年のフリードマンの定理は、ボレルの決定性が満たされないツェルメロ集合論のモデル (選択公理を含む) が存在することを示し、したがってツェルメロ集合論だけではボレルの決定性定理を証明できない。^[1]

可算指数のすべてのベス数の存在は、ボレルの決定性定理を証明するのに十分である。^[2]

より強い決定性

記述集合論では、ボレル決定性よりも強い決定性に関するいくつかの集合論的原理が研究されています。それらは、大基数公理と密接に関連しています。

射影決定性公理は、ポーランド空間のすべての射影部分集合が決定されていることを述べています。これは ZFC では証明不可能であることが知られていますが、比較的それと整合しており、特定の大きな基数公理によって暗示されています。測定可能な基数の存在は、ポーランド空間のすべての解析的部分集合が決定されているという結果を ZFC 上で暗示するのに十分であり、これは完全な射影決定性よりも弱いものです。

決定性公理は、すべてのポーランド空間のすべての部分集合が決定されることを述べています。これは ZFC とは矛盾しますが、ZF + DC (ツェルメロ–フランケル集合論と従属選択公理) では、特定の大きな基数公理と等しく矛盾しません。

参考文献

^ H. フリードマン、「高等集合論と数学的実践」、Annals of Mathematical Logic 2 (1971)。pp.326--357。
^ Leinster, Tom (2021年7月23日). 「Borel Determinacy Does Not Require Replacement」. The n-Category Café . テキサス大学オースティン校. 2021年8月25日閲覧。

フリードマン、ハーヴェイ（1971）。「高等集合論と数学的実践」。数学論理年報。2（3）：325-357。doi ：10.1016/0003-4843（71）90018-0。
- L. ブコフスキー、評論家、数学レビュー、MR 284327。
Gale, D. および FM Stewart (1953)。「完全情報による無限ゲーム」。ゲーム理論への貢献、第 2 巻。数学研究年報、第 28 巻。第 28 巻。プリンストン大学出版局。pp. 245–266。
- S. Sherman、査読者、Mathematical Reviews、MR 54922。
アレクサンダー・ケクリス(1995)。古典的記述集合論。数学大学院テキスト。第 156 巻。ISBN 0-387-94374-9。
マーティン、ドナルド A. (1975)。「ボレルの決定性」。数学年報。第 2 シリーズ。102 (2): 363–371。doi :10.2307/1971035。
- John Burgess、査読者。Mathematical Reviews、MR 403976。
Martin, Donald A. (1982)。「ボレル決定性の純粋に帰納的な証明」。再帰理論。Proc. Sympos。純粋数学 (ニューヨーク州イサカで開催された AMS-ASL 夏期講習会の議事録)。pp. 303–308。
- FR Drake、査読者、Mathematical Reviews、MR 791065。

外部リンク

ボレルの決定性とメタ数学。ロス・ブライアント。修士論文、ノーステキサス大学、2001 年。
スタンフォード哲学百科事典の「大きな基数と決定性」

[1] H. フリードマン、「高等集合論と数学的実践」、Annals of Mathematical Logic 2 (1971)。pp.326--357。

[2] Leinster, Tom (2021年7月23日). 「Borel Determinacy Does Not Require Replacement」. The n-Category Café . テキサス大学オースティン校. 2021年8月25日閲覧。