賃金階層

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

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

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

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

ワッジの補題は、計算可能性理論における円錐の補題と類似している。

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

ゲームが決定されていると仮定します。プレイヤー I が必勝戦略を持っている場合、これは連続 (偶数リプシッツ) 写像を縮小します。${\displaystyle B}$補うために${\displaystyle A}$、一方プレイヤーIIが必勝戦略を持っている場合は、${\displaystyle A}$に${\displaystyle B}$例えば、プレイヤーIIが必勝戦略を持っていると仮定します。すべてのシーケンスxを、プレイヤーIIがプレイするシーケンスyにマッピングします。${\displaystyle G(A,B)}$プレイヤー I がシーケンスxをプレイし、プレイヤー II が自身の勝利戦略に従う場合、これは、xがに含まれるという性質を持つ連続マップfを定義します。${\displaystyle A}$f ( x )が${\displaystyle B}$。

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

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

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

• 分析的階層構造― 数理論理学および集合論における概念 
• 算術的階層– 集合を定義する式の複雑性クラスの階層 
• 決定性の公理― 集合論における可能性のある公理 
• ボレル同値関係
• ボレル階層– 数学的論理階層 
• 決定性― 集合論の分野 
• 点クラス– 記述的集合論の概念 
• ヴァイラウフ還元可能性– 計算可能性からの概念 

• Alexander S. Kechris、Benedikt Löwe、John R. Steel 編 (2011 年 12 月)。Wadge Degrees and Projective Ordinals: The Cabal Seminar Volume II。Lecture Notes in Logic。ケンブリッジ大学出版局。ISBN 9781139504249。
• Andretta, Alessandro (2007). 「SLO原理とワッジ階層」。Bold, Stefan、Benedikt Löwe、Räsch, Thoralf 他編『 無限ゲーム：2004年11月26日～29日にボンで開催された会議「形式科学の基礎V」論文集』所収。Studies in Logic. Vol.  11. College Publications. pp. 1–38 . ISBN  9781904987758。。
• 金森章弘（2000）．高次の無限(第 2 版)。スプリンガー。ISBN 3-540-00384-3。
• Kechris, Alexander S. (1995).古典的記述集合論. Springer. ISBN 0-387-94374-9。
• Wadge, William W. (1983).ベール空間における還元可能性と決定性(PDF) (博士論文). カリフォルニア大学バークレー校.

• アンドレッタ、アレッサンドロ、マーティン、ドナルド (2003)。「ボレル・ウェッジ度」。数学の基礎。177 (2): 175–192 .土井: 10.4064/fm177-2-5。
• Cenzer, Douglas (1984). 「単調還元可能性と無限集合の族」。『記号論理学ジャーナル』49 (3). 記号論理学会: 774–782 . doi : 10.2307/2274130 . JSTOR 2274130 . S2CID 37813340 .  
• Duparc, Jacques (2001). "Wadge階層とVeblen階層。パートI：有限ランクのBorel集合". Journal of Symbolic Logic . 66 (1): 55–86 . doi : 10.2307/2694911 . JSTOR 2694911. S2CID 17703130 .  
• セリバノフ、ビクター L. (2006). 「ドメインのような構造のための記述的集合論に向けて」 . Theoretical Computer Science . 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日取得。