ワッジ階層

数学における記述的集合論において、ワッジ次数は実数の集合の複雑さのレベルです。集合は連続的な簡約によって比較されます。ワッジ階層はワッジ次数の構造です。これらの概念はウィリアム・W・ワッジにちなんで名付けられました。

およびがベール空間ω ^ωの部分集合であるとする。このとき、ω ^ω上に を満たす 連続関数が存在する場合、ワッジはまたは≤ _Wに還元可能である。ワッジ順序は、ベール空間の部分集合上の前順序または準順序である。この前順序による集合の同値類はワッジ次数と呼ばれ、集合の次数は[ ] _{Wで表されます。ワッジ順序で順序付けられたワッジ次数の集合は、}ワッジ階層と呼ばれる。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$ ${\displaystyle B}$${\displaystyle f}$${\displaystyle A=f^{-1}[B]}$${\displaystyle A}$${\displaystyle A}$

ワッジ次数の特性には、定義可能性の観点から述べられた複雑さの尺度との一貫性が含まれます。たとえば、≤ _Wであり、 が開集合の可算な共通部分である場合、 も可算です。同じことが、ボレル階層と差分階層のすべてのレベルに当てはまります。ワッジ階層は、決定性公理のモデルで重要な役割を果たします。ワッジ次数へのさらなる関心は、コンピューター サイエンスからも寄せられており、いくつかの論文では、ワッジ次数がアルゴリズムの複雑さに関連していることが示唆されています。 ${\displaystyle A}$ ${\displaystyle B}$${\displaystyle B}$ ${\displaystyle A}$

ワッジの補題は、決定性公理（AD ）の下で、ベール空間の任意の2つの部分集合に対して、 ≤ _Wまたは≤ _W ω ^ω \であることを述べている。^[1]ワッジの補題がΓ内の集合に対して成り立つという主張は、ΓまたはSLO(Γ)の半線型順序原理である。${\displaystyle A,B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$半線型順序は、補集合を法とする同値類上の線型順序を定義します。ワッジの補題は、任意の点クラスΓ、たとえばボレル集合、 Δ ¹ _n集合、 Σ ¹ _n集合、またはΠ ¹ _n集合に局所的に適用できます。これは、Γ 内の集合の差の決定性から生じます。ボレルの決定性はZFCで証明されている、ZFC はボレル集合に対するワッジの補題を意味します。

Wadge の補題は、計算可能性理論の円錐補題に似ています。

ワッジゲームは、ベール空間の部分集合の連続的簡約の概念を調査するために用いられる単純な無限ゲームである。ワッジは1972年までにゲームを用いてベール空間のワッジ階層の構造を分析していたが、この結果はずっと後になってから博士論文で発表した。ワッジゲームでは、プレイヤーIとプレイヤーIIがそれぞれ整数をプレイし、プレイヤーIとIIが生成したシーケンスxとyがそれぞれ集合Aと集合Bに含まれるかどうかを調べることでゲームの勝敗が決まる。両方のプレイヤーの結果が同じ場合、つまり がにあり、かつ がにある場合に限り、プレイヤーIIが勝ちとなる。結果が異なる場合、プレイヤーIが勝ちとなる。これはリプシッツゲームと呼ばれることもあり、プレイヤーIIが有限回パスできるオプションを持つ変種はワッジゲームと呼ばれる。 ${\displaystyle G(A,B)}$${\displaystyle x}$${\displaystyle A}$${\displaystyle y}$${\displaystyle B}$

ゲームが と決定されていると仮定します。プレーヤー I が勝利戦略を持っている場合、これはの補数に簡約する連続（偶数Lipschitz）マップを定義し、一方プレーヤー II が勝利戦略を持っている場合、を に簡約します。たとえば、プレーヤー II が勝利戦略を持っているとします。プレーヤー I がシーケンス x をプレイし、プレーヤー II が勝利戦略に従う場合、すべてのシーケンス x をプレーヤー II がプレイするシーケンス y にマップします。これは、f ( x )がにある場合のみxが含まれるという特性を持つ連続マップf を定義します。 ${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle G(A,B)}$${\displaystyle A}$${\displaystyle B}$

マーティンとモンクは 1973 年に、AD はベール空間のワッジ順序が整列していることを証明した。したがって、AD のもとでは、補集合を法とするワッジ類は整列順序を形成する。集合のワッジ階数は、[ ] _Wより厳密に下の補集合を法とするワッジ次数の集合の順序型である。ワッジ階層の長さはΘであることが示された。ワッジはまた、ボレル集合に制限されたワッジ階層の長さが φ _{ω 1} (1) (または表記法によっては φ _{ω 1} (2)) であることを証明した。ここで φ _{γは基数 ω 1} (通常の ω ではなく) に対するγ^番目のヴェブレン関数である。${\displaystyle A}$${\displaystyle A}$

Wadge の補題に関しては、これは決定性公理を仮定して、任意の点クラス Γ に対して成り立つ。各集合をWadge 階層で厳密に下位にあるすべての集合のコレクションと関連付けると、これが点クラスを形成する。同様に、各順序数α ≤ θ に対して、ステージα の前に現れる集合の コレクション W _αは点クラスである。逆に、すべての点クラスは何らかの_αに等しい。点クラスは、補集合に関して閉じている場合、自己双対であると言われる。W _αが自己双対であるのは、 αが 0、偶数後続順序数、または可算共終性の極限順序数のいずれかである場合のみであることが示される。 ${\displaystyle A}$${\displaystyle A}$${\displaystyle W}$

同様の簡約と次数の概念は、連続関数を、恒等関数を含み合成に関して閉じている関数の任意のクラスFで置き換えることによって生じます。F内の何らかの関数に対して、≤ F_と書きます。このような関数の任意のクラスは、再び、ベール空間の部分集合の順序を決定します。リプシッツ関数によって与えられる次数はリプシッツ次数と呼ばれ、ボレル関数によって与えられる次数はボレル–ワッジ次数と呼ばれます。 ${\displaystyle A}$ ${\displaystyle B}$${\displaystyle A=f^{-1}[B]}$${\displaystyle f}$

• 分析的階層 – 数理論理学と集合論における概念
• 算術階層 – 集合を定義する式の複雑さのクラスの階層
• 決定性公理 – 集合論の可能な公理
• ボレル同値関係
• ボレル階層
• 決定性 – 集合論のサブフィールド
• ポイントクラス – 記述的集合論の概念
• ヴァイラウフ還元可能性 – 計算可能性からの概念

• Alexander S. Kechris、Benedikt Löwe、John R. Steel 編 (2011 年 12 月)。Wadge度と射影順序数: Cabal セミナー第 2 巻。論理学講義ノート。ケンブリッジ大学出版局。ISBN 9781139504249。
• Andretta, Alessandro (2007)。「SLO 原理と Wadge 階層」。Bold, Stefan、Benedikt Löwe、Räsch, Thoralf 他 (編)。Infinite Games、2004 年 11 月 26 ～ 29 日にボンで開催された「Foundations of the Formal Sciences V」会議の論文。論理学研究。第 11 巻。大学出版。pp. 1 ～38。ISBN 9781904987758。。
• 金森章弘（2000）．高次の無限(第 2 版)。スプリンガー。ISBN 3-540-00384-3。
• ケクリス、アレクサンダー S. (1995)。古典的記述集合論。シュプリンガー。ISBN 0-387-94374-9。
• Wadge, William W. (1983). Baire 空間における還元性と決定性(PDF) (博士論文). カリフォルニア大学バークレー校.

• アンドレッタ、アレッサンドロ、マーティン、ドナルド (2003)。 「ボレル・ウェッジ度」。数学の基礎。177 (2): 175–192。土井：10.4064/fm177-2-5。
• Cenzer, Douglas (1984). 「単調な還元性と無限集合族」. The Journal of Symbolic Logic . 49 (3). Association for Symbolic Logic: 774–782. doi :10.2307/2274130. JSTOR  2274130. S2CID  37813340.
• デュパルク、ジャック ( 2001  ) 。「ワッジ階層とヴェブレン階層。パート I: 有限ランクのボレル集合」。Journal of Symbolic Logic。66 ( 1): 55–86。doi : 10.2307/2694911。JSTOR 2694911。S2CID 17703130  。
•  セリバノフ、ビクター L. (2006)。「ドメインのような構造の記述的集合論に向けて」。理論計算機科学。365 ( 3): 258–282。doi : 10.1016/ j.tcs.2006.07.053。ISSN 0304-3975。
• セリバノフ、ビクター L. (2008)。「ワッジの還元可能性と無限計算」。 コンピュータサイエンスにおける数学。2 (1): 5–36。doi : 10.1007/s11786-008-0042- x。ISSN 1661-8270。S2CID 38211417  。
• Harry Bliss (2006)。ボレル関数のツリーゲーム (プレプ​​リント)。アムステルダム大学、ILLC プレ出版 PP-2006-24。2007年 8 月 12 日閲覧。