解析的階層のソースを表示

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

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

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

クラトフスキとタルスキは1931年、どんな二階算術言語の式も[[冠頭標準形]]を持つことを示した。<ref>P. Odifreddi, ''Classical Recursion Theory'' (1989), p.378. North-Holland, 0-444-87295-7</ref> そしてそれゆえ、そのような式はある <math>n</math> に対する <math>\Sigma^1_n</math> か <math>\Pi^1_n</math> である。どんな式にも無意味な量化を追加することができるため、いったんある <math> n </math> に対する <math>\Sigma^1_n</math> や <math>\Pi^1_n</math> に属した式は <math>n</math> より大きい <math>m</math> に対する <math>\Sigma^1_m</math> や <math>\Pi^1_m</math> にも必ず属することになる。

== 自然数の集合に対する解析的階層 ==
自然数からなる集合にクラス <math>\Sigma^1_n</math> が割り当てられるのは、それが <math>\Sigma^1_n</math> 式で定義可能であるときである。同様に <math>\Pi^1_n</math> が割り当てられるのは <math>\Pi^1_n</math> 式で定義できるときである。集合が <math>\Sigma^1_n</math> と <math>\Pi^1_n</math> 両方に該当するとき、追加クラス <math>\Delta^1_n</math> に割り当てられる。

<math>\Delta^1_1</math> 集合は'''超算術的'''と呼ばれる。これに該当する集合は、[[超算術理論]]による計算可能関数を繰り返し用いる方法でも与えられる。

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

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

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

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

== 拡張 ==

[[算術的階層]]での場合と同様に、解析的階層でも相対化バージョンを定義することができる。言語が集合の定数記号 ''A'' を追加して拡張されているとする。この拡張された言語で <math>\Sigma^{1,A}_n</math> や <math>\Pi^{1,A}_n</math> であることが上記の定義と同様に帰納的に定義できる。与えられた集合 <math>Y</math> について、ある集合が <math>\Sigma^{1,Y}_n</math> であるとは、それがある <math>\Sigma^{1,A}_n</math> 式内の <math>A</math> を <math>Y</math> で解釈したもので定義できることをいう; <math>\Pi^{1,Y}_n</math> と <math>\Delta^{1,Y}_n</math> についても同様である。あるパラメータ <math>Y</math> によって <math>\Sigma^{1,Y}_n</math> や <math>\Pi^{1,Y}_n</math> となるような集合は[[射影階層]]に分類される。射影階層はパラメータを用いていることを表すために太字のギリシャ文字でしばしば書かれる。<ref>P. D. Welch, [https://people.maths.bris.ac.uk/~mapdw/det17.pdf "Weak Systems of Determinacy and Arithmetical Quasi-Inductive Definitions"] (2010 draft ver., p. 3). Accessed 31 July 2022.</ref>

== 例 ==
* <math>\mathbb N^2</math> 上の関係 <math>\prec</math> について、文 "<math>\prec</math> は <math>\mathbb N</math> 上の[[整列順序]]である" は <math>\Pi_1^1</math> 式である。(集合の上の一般的な整礎関係の場合と混同してはいけない。[[レヴィ階層]]を参照)

* 自然数の集合でその要素が計算可能な順序数でインデックスされているようなものは <math>\Pi^1_1</math> であって <math>\Sigma^1_1</math> でない。
**こういった集合はちょうど <math>\omega</math> の [[:en:Alpha recursion theory|<math>\omega_1^{CK}</math>-帰納的可算]]な部分集合である。<ref>J. Barwise, Admissible sets and structures, (1975), p.168. Springer</ref>

* 連続関数 <math>f:[0,1]\to\mathbb [0,1]</math> で[[平均値の定理]]の性質を持つようなもの全体の集合は <math>\Delta_2^1</math> 未満の階層には入らない。<ref>{{Cite arXiv|last=Quintanilla|first=M.|eprint=2206.10754|title=The realm numbers in inner models of set theory|date=2022}}</ref>
* <math>\omega</math> の整列関係の特徴関数をカントール空間の元で表したもの全体による集合は <math>\Pi^1_1</math> 集合であって <math>\Sigma^1_1</math> でない。事実、この集合はベール空間のどんな元 <math>Y</math> を持ってきてもそれを用いた <math>\Sigma^{1,Y}_1</math> 集合としては表現できない。
* [[構成可能性公理]]が成立するとき、ベール空間とそれ自身の直積の部分集合であって <math>\Delta^1_2</math> 集合であって、それがベール空間の[[整列順序]]のグラフになっているものが存在する。また、同様にカントール空間でも <math>\Delta^1_2</math> な整列順序が存在する。

== 性質 ==
各 <math>n</math> について次のように真の包含関係が成り立つ:

:<math>\Pi^1_n \subset \Sigma^1_{n+1}</math>,
:<math>\Pi^1_n \subset \Pi^1_{n+1}</math>,
:<math>\Sigma^1_n \subset \Pi^1_{n+1}</math>,
:<math>\Sigma^1_n \subset \Sigma^1_{n+1}</math>.

ある ''n'' についての <math>\Sigma^1_n</math> であるような集合を '''解析的(analytical)''' と呼ぶことがある。歴史的に使われてきた語である[[解析集合]](analytic set)とは異なるので混同しないように注意が必要である。こちらは <math>\boldsymbol\Sigma_1^1</math> 集合のことを指す。<ref>T. Jech, "[https://projecteuclid.org/journalArticle/Download?urlid=bams%2F1183548432 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).</ref>

==表==
{{pointclasses}}

== 関連項目 ==
* [[算術的階層]]
* [[レヴィ階層]]

== 参考文献 ==
{{Reflist}}
* {{cite book | author=Rogers, H. | title= Theory of recursive functions and effective computability| url=https://archive.org/details/theoryofrecursiv00roge | url-access=registration |
publisher=McGraw-Hill | year=1967}}
* {{cite book | author=Kechris, A. | title= Classical Descriptive Set Theory | url=https://archive.org/details/classicaldescrip0000kech | url-access=registration |
publisher=Springer | year=1995 | isbn = 0-387-94374-9| edition=Graduate Texts in Mathematics 156}}

{{DEFAULTSORT:かいせきてきかいそう}}
[[Category:計算可能性理論]]
[[Category:実効記述集合論]]
[[Category:ヒエラルキー]]
[[Category:数理論理学的階層]]
[[Category:数学に関する記事]]