解析的階層

ウィキペディア

解析的階層

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/02/28 18:47 UTC 版)

数理論理学や記述集合論において、解析的階層（かいせきてきかいそう、Analytical hierarchy）は算術的階層の拡張である。論理式の解析的階層には二階算術の言語による式が含まれ、すなわち、自然数全体の集合 ${\displaystyle \mathbb {N} }$ をわたる量化と${\displaystyle \mathbb {N} }$ から ${\displaystyle \mathbb {N} }$ への関数全体をわたる量化を持つものが含まれる。集合の解析的階層は、集合を定義するのに使える論理式によって集合を分類するもので、射影階層の細字版である。

論理式の解析的階層

表記 ${\displaystyle \Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}}$ が示すのは、二階算術の言語の式のクラスであって、数の量化のみをもち集合の量化は持たないもののクラスである。この言語は集合パラメータを含んでいない。ここでのギリシャ文字は細字記号であり、そのタイプの言語の選択を示している。対応するそれぞれの太字記号は、実数をパラメータとする拡張言語における数式の対応するクラスを示す; 詳細は射影階層を参照。

二階算術の言語の式は、それが ${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$（ただし ${\displaystyle \psi }$ は ${\displaystyle \Pi _{n}^{1}}$ 式）の形の論理式と論理的同値であるとき、${\displaystyle \Sigma _{n+1}^{1}}$と定義される。同様に、${\displaystyle \forall X_{1}\cdots \forall X_{k}\psi }$（ただし ${\displaystyle \psi }$ は ${\displaystyle \Sigma _{n}^{1}}$ 式）の形の論理式と論理的同値であるとき、${\displaystyle \Pi _{n+1}^{1}}$と定義される。全ての自然数 ${\displaystyle n}$ に対してこの帰納的定義でクラス ${\displaystyle \Sigma _{n}^{1}}$、${\displaystyle \Pi _{n}^{1}}$ を定める。

クラトフスキとタルスキは1931年、どんな二階算術言語の式も冠頭標準形を持つことを示した。^[1] そしてそれゆえ、そのような式はある ${\displaystyle n}$ に対する ${\displaystyle \Sigma _{n}^{1}}$ か ${\displaystyle \Pi _{n}^{1}}$ である。どんな式にも無意味な量化を追加することができるため、いったんある ${\displaystyle n}$ に対する ${\displaystyle \Sigma _{n}^{1}}$ や ${\displaystyle \Pi _{n}^{1}}$ に属した式は ${\displaystyle n}$ より大きい ${\displaystyle m}$ に対する ${\displaystyle \Sigma _{m}^{1}}$ や ${\displaystyle \Pi _{m}^{1}}$ にも必ず属することになる。

自然数の集合に対する解析的階層

自然数からなる集合にクラス ${\displaystyle \Sigma _{n}^{1}}$ が割り当てられるのは、それが ${\displaystyle \Sigma _{n}^{1}}$ 式で定義可能であるときである。同様に ${\displaystyle \Pi _{n}^{1}}$ が割り当てられるのは ${\displaystyle \Pi _{n}^{1}}$ 式で定義できるときである。集合が ${\displaystyle \Sigma _{n}^{1}}$ と ${\displaystyle \Pi _{n}^{1}}$ 両方に該当するとき、追加クラス ${\displaystyle \Delta _{n}^{1}}$ に割り当てられる。

${\displaystyle \Delta _{1}^{1}}$ 集合は超算術的と呼ばれる。これに該当する集合は、超算術理論による計算可能関数を繰り返し用いる方法でも与えられる。

カントール空間とベール空間の部分集合に対する解析的階層

解析的階層は任意の実効ポーランド空間で定義できる。カントール空間とベール空間は通常の二階算術の言語に合うので、定義は特に単純である。カントール空間は0と1からなる全ての無限列の集合であり、ベール空間は自然数からなる全ての無限列の集合である。これらはどちらもポーランド空間である。

二階算術の通常の公理化では、集合量化子がカントール空間上の量化として自然に見ることができる集合ベースの言語を用いる。カントール空間の部分集合は、${\displaystyle \Sigma _{n}^{1}}$ 式によって定義可能であれば ${\displaystyle \Sigma _{n}^{1}}$ のクラスが割り当てられる。同様に、${\displaystyle \Pi _{n}^{1}}$ 式で定義可能な集合には ${\displaystyle \Pi _{n}^{1}}$ という分類が割り当てられる。集合が ${\displaystyle \Sigma _{n}^{1}}$ と ${\displaystyle \Pi _{n}^{1}}$ の両方である場合、追加のクラス ${\displaystyle \Delta _{n}^{1}}$ が与えられる。

ベール空間の部分集合は、${\displaystyle \omega }$ から ${\displaystyle \omega }$ への各関数をそのグラフの特徴関数に写す写像の下で、カントール空間上に対応する部分集合をもつ。よって、ベール空間上で集合が ${\displaystyle \Sigma _{n}^{1}}$, ${\displaystyle \Pi _{n}^{1}}$, ${\displaystyle \Delta _{n}^{1}}$ のクラスに分類されることは、カントール空間上で対応する同じクラスに分類されることと同値である。ベール空間上の解析的階層と同値な定義は二階算術の関数版を用いた式の解析的階層を定義することによって与えられる; それゆえカントール空間上の解析的階層はベール空間上の階層から定義できる。この代替の定義は最初の定義と全く同じ分類を与える。

カントール空間は、それ自身の任意有限個のデカルト直積と同相であるので、ベール空間も同様に自身の任意有限個のデカルト直積と同相である。それらの空間でも解析的階層は同様に適用される。同様の拡張が、カントール空間の可算直積、ベール空間の可算直積でも可能である。

拡張

算術的階層での場合と同様に、解析的階層でも相対化バージョンを定義することができる。言語が集合の定数記号 A を追加して拡張されているとする。この拡張された言語で ${\displaystyle \Sigma _{n}^{1,A}}$ や ${\displaystyle \Pi _{n}^{1,A}}$ であることが上記の定義と同様に帰納的に定義できる。与えられた集合 ${\displaystyle Y}$ について、ある集合が ${\displaystyle \Sigma _{n}^{1,Y}}$ であるとは、それがある ${\displaystyle \Sigma _{n}^{1,A}}$ 式内の ${\displaystyle A}$ を ${\displaystyle Y}$ で解釈したもので定義できることをいう; ${\displaystyle \Pi _{n}^{1,Y}}$ と ${\displaystyle \Delta _{n}^{1,Y}}$ についても同様である。あるパラメータ ${\displaystyle Y}$ によって ${\displaystyle \Sigma _{n}^{1,Y}}$ や ${\displaystyle \Pi _{n}^{1,Y}}$ となるような集合は射影階層に分類される。射影階層はパラメータを用いていることを表すために太字のギリシャ文字でしばしば書かれる。^[2]

例

• ${\displaystyle \mathbb {N} ^{2}}$ 上の関係 ${\displaystyle \prec }$ について、文 "${\displaystyle \prec }$ は ${\displaystyle \mathbb {N} }$ 上の整列順序である" は ${\displaystyle \Pi _{1}^{1}}$ 式である。(集合の上の一般的な整礎関係の場合と混同してはいけない。レヴィ階層を参照)

• 自然数の集合でその要素が計算可能な順序数でインデックスされているようなものは ${\displaystyle \Pi _{1}^{1}}$ であって ${\displaystyle \Sigma _{1}^{1}}$ でない。
  • こういった集合はちょうど ${\displaystyle \omega }$ の ${\displaystyle \omega _{1}^{CK}}$-帰納的可算な部分集合である。^[3]

• 連続関数 ${\displaystyle f:[0,1]\to \mathbb {[} 0,1]}$ で平均値の定理の性質を持つようなもの全体の集合は ${\displaystyle \Delta _{2}^{1}}$ 未満の階層には入らない。^[4]
• ${\displaystyle \omega }$ の整列関係の特徴関数をカントール空間の元で表したもの全体による集合は ${\displaystyle \Pi _{1}^{1}}$ 集合であって ${\displaystyle \Sigma _{1}^{1}}$ でない。事実、この集合はベール空間のどんな元 ${\displaystyle Y}$ を持ってきてもそれを用いた ${\displaystyle \Sigma _{1}^{1,Y}}$ 集合としては表現できない。
• 構成可能性公理が成立するとき、ベール空間とそれ自身の直積の部分集合であって ${\displaystyle \Delta _{2}^{1}}$ 集合であって、それがベール空間の整列順序のグラフになっているものが存在する。また、同様にカントール空間でも ${\displaystyle \Delta _{2}^{1}}$ な整列順序が存在する。

性質

各 ${\displaystyle n}$ について次のように真の包含関係が成り立つ:

${\displaystyle \Pi _{n}^{1}\subset \Sigma _{n+1}^{1}}$,

${\displaystyle \Pi _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}}$.

ある n についての ${\displaystyle \Sigma _{n}^{1}}$ であるような集合を 解析的(analytical) と呼ぶことがある。歴史的に使われてきた語である解析集合(analytic set)とは異なるので混同しないように注意が必要である。こちらは ${\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}$ 集合のことを指す。^[5]

表

このボックス:

• 表示
• ノート
• 編集
• 履歴

細字		太字
Σ0 0 = Π0 0 = Δ0 0 (しばしばΔ0 1と同じ)		Σ0 0 = Π0 0 = Δ0 0 (定義されていれば)
Δ0 1 = 帰納的		Δ0 1 = 開かつ閉
Σ0 1 = 帰納的可算	Π0 1 = 補-帰納的可算	Σ0 1 = G = 開	Π0 1 = F = 閉
Δ0 2		Δ0 2
Σ0 2	Π0 2	Σ0 2 = Fσ	Π0 2 = Gδ
Δ0 3		Δ0 3
Σ0 3	Π0 3	Σ0 3 = Gδσ	Π0 3 = Fσδ
⋮		⋮
Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = 算術的		Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = boldface arithmetical
⋮		⋮
Δ0 α (αは再帰的)		Δ0 α (αは可算)
Σ0 α	Π0 α	Σ0 α	Π0 α
⋮		⋮
Σ0 ωCK 1 = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1 = 超算術的		Σ0 ω1 = Π0 ω1 = Δ0 ω1 = Δ1 1 = B = ボレル
Σ1 1 = lightface analytic	Π1 1 = lightface coanalytic	Σ1 1 = A = 解析集合	Π1 1 = CA = 補解析集合
Δ1 2		Δ1 2
Σ1 2	Π1 2	Σ1 2 = PCA	Π1 2 = CPCA
Δ1 3		Δ1 3
Σ1 3	Π1 3	Σ1 3 = PCPCA	Π1 3 = CPCPCA
⋮		⋮
Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = 解析的階層に属する集合		Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = P = 射影集合
⋮		⋮

関連項目

• 算術的階層
• レヴィ階層

参考文献

1. ^ P. Odifreddi, Classical Recursion Theory (1989), p.378. North-Holland, 0-444-87295-7
2. ^ P. D. Welch, "Weak Systems of Determinacy and Arithmetical Quasi-Inductive Definitions" (2010 draft ver., p. 3). Accessed 31 July 2022.
3. ^ J. Barwise, Admissible sets and structures, (1975), p.168. Springer
4. ^ Quintanilla, M. (2022). "The realm numbers in inner models of set theory". arXiv:2206.10754。
5. ^ T. Jech, "The Brave New World of Determinacy" (PDF download). Book review, Bulletin of the American Mathematical Society, vol. 5, number 3, November 1981 (pp.339--349).

• Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. https://archive.org/details/theoryofrecursiv00roge 
• Kechris, A. (1995). Classical Descriptive Set Theory (Graduate Texts in Mathematics 156 ed.). Springer. ISBN 0-387-94374-9. https://archive.org/details/classicaldescrip0000kech