算術的階層のソースを表示

'''算術的階層'''（さんじゅつてきかいそう、{{lang-en-short|Arithmetical hierarchy}}）は、[[数理論理学]]において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。'''クリーネ階層'''（Kleene hierarchy）とも。このような分類が可能な集合は'''算術的'''である。

算術的階層は、[[再帰理論]]や[[ペアノの公理|ペアノ算術]]のような形式理論の研究で重要である。

算術的階層での式や集合の分類の拡張として、[[超算術的階層]]や[[解析的階層]]がある。

== 数式の算術的階層 ==
算術的階層では、[[ペアノの公理|ペアノ算術]]の言語で書かれた式を分類する。階層は自然数 ''n'' を使って、<math>\Sigma^0_n</math> および <math>\Pi^0_n</math> と記される。ここでのギリシア文字は細活字(lightface)であり、式に集合パラメータが含まれないことを示している。

式 <math>\phi</math> が有界[[量化子]]しか含まない式と論理的に等価であれば、<math>\phi</math> は階層 <math>\Sigma^0_0</math> と <math>\Pi^0_0</math> に相当する。

階層 <math>\Sigma^0_n</math> と <math>\Pi^0_n</math> は、全ての自然数 ''n'' について以下のように帰納的に定義される。
* <math>\psi</math> が <math>\Pi^0_n</math> であるとき、<math>\exists n_1 \cdots \exists n_k \psi</math> という形式と論理的に等価な式 <math>\phi</math> は、階層 <math>\Sigma^0_{n+1}</math> に相当する。
* <math>\psi</math> が <math>\Sigma^0_n</math> であるとき、<math>\forall n_l \cdots \forall n_k  \psi</math> という形式と論理的に等価な式 <math>\phi</math> は、階層 <math>\Pi^0_{n+1}</math> に相当する。

あらゆる式は等価な[[冠頭標準形]]に変換できるため、集合量化子のないあらゆる式は少なくとも1つの階層に分類される。意味のない量化子を式に追加することが可能なため、<math>\Sigma^0_n</math> または <math>\Pi^0_n</math> に分類された式は、''n'' より大きいあらゆる ''m'' について <math>\Sigma^0_m</math> と <math>\Pi^0_m</math> にも分類可能である。従って、最も重要な分類は最小の ''n'' に対応する階層であり、他の分類はそこから決定可能である。

== 自然数の集合の算術的階層 ==
ペアノ算術の言語で書かれた式 &phi;(n) で、集合 ''X'' が <math>n \in X \leftrightarrow \mathbb{N} \models \phi(n)</math> のように定義されるとする。これはつまり、''X'' の元が &phi; を満足する数ということを意味している。集合が一階算術で定義可能であるとは、ペアノ算術の言語で書かれた式で定義されることに他ならない。

一階算術で定義可能な自然数の集合 ''X'' は、<math>n</math> を自然数としたときの階層 <math>\Sigma^0_n</math>、<math>\Pi^0_n</math>、<math>\Delta^0_n</math> に以下のように分類される。''X'' が <math>\Sigma^0_n</math> に属する式で定義可能なら、<math>X</math> は階層 <math>\Sigma^0_n</math> に分類される。''X'' が <math>\Pi^0_n</math> に属する式で定義可能なら、<math>X</math> は階層 <math>\Pi^0_n</math> に分類される。<math>X</math> が <math>\Sigma^0_n</math> にも <math>\Pi^0_n</math> にも属するなら、<math>X</math> は追加の階層 <math>\Delta^0_n</math> に分類される。

なお、<math>\Delta^0_n</math> に属する式と言った場合、ほとんど意味をなさない。これはつまり、先頭の量化子が[[存在記号|存在量化子]]か[[全称記号|全称量化子]]の式を意味する。従って <math>\Delta^0_n</math> に属する集合は <math>\Delta^0_n</math> に属する式で定義されるのではなく、<math>\Sigma^0_n</math> に属する式と <math>\Pi^0_n</math> に属する式の両方で定義される集合である。

自然数の有限な[[直積集合]]の算術的階層の定義には並列定義が使われる。1つの[[自由変項]]の式の代わりに ''k'' 個の自由変項の式を使い、''k''-タプルの自然数の集合についての算術的階層を定義する。

== 相対化算術的階層 ==
集合 ''X'' が 集合 ''Y'' に対して再帰的相対性を持つということを、''Y'' を一種の[[神託機械]]として ''X'' を求められることと定義すると、これを算術的階層全体に拡張し、''Y'' に対して ''X'' が <math>\Sigma^0_n</math>、<math>\Delta^0_n</math>、<math>\Pi^0_n</math> であるということをそれぞれ <math>\Sigma^{0,Y}_n</math>、<math>\Delta^{0,Y}_n</math>、<math>\Pi^{0,Y}_n</math> と記述する。このために、整数の集合''Y'' を固定し、ペアノ算術の言語に ''Y'' のメンバーシップ述語を追加する。''X'' が <math>\Sigma^{0,Y}_n</math> に属するとは、この拡張された言語で書かれた <math>\Sigma^0_n</math> の式で定義されることを意味する。言い換えれば、''X'' が <math>\Sigma^{0,Y}_n</math> に属するとは、その中で''Y'' に属するかどうかの質問が許されている <math>\Sigma^{0}_n</math> に属する論理式で定義されることを意味する。

例えば、''Y'' を整数の集合とする。''X'' は、ある ''Y'' の元で割り切れる数の集合とする。すると ''X'' は式 <math>\phi(n)=\exists m \exists t (Y(m)\land m\times t = n)</math> で定義されるので、''X'' は <math>\Sigma^{0,Y}_1</math> に属することになる（実際には、2つの量化子を ''n'' で制限できるので <math>\Delta^{0,Y}_0</math> に属する）。

== 算術還元性と次数 ==
算術還元性は、[[チューリング還元]]性と超算術還元性の中間の概念である。

ある集合が'''算術的'''であるとは、それがペアノ算術の言語で書かれた式で定義されることを意味する。これと等価的に ''X'' が算術的であるとは、''X'' が何らかの整数 ''n'' の <math>\Sigma^0_n</math> または <math>\Pi^0_n</math> に属することを意味する。集合 ''X'' が集合 ''Y'' において算術的であるということを <math>X \leq_A Y</math> で表し、''Y'' についてのメンバーシップ述語で拡張されたペアノ算術の言語で書かれた式で ''X'' を定義可能であることを意味する。これと等価的に ''X'' が ''Y'' において算術的であるとは、ある整数 ''n'' に対し ''X'' が <math>\Sigma^{0,Y}_n</math> または <math>\Pi^{0,Y}_n</math> に属することを意味する。<math>X \leq_A Y</math> は、''X'' が ''Y'' に'''算術還元可能'''であることを意味する。

<math>X \leq_A Y</math> は[[反射関係]]かつ[[推移関係]]であり、したがって <math>\equiv_A</math> という関係を次のように定義すると、これは[[同値関係]]となる。

:<math> X \equiv_A Y \Leftrightarrow X \leq_A Y \land Y \leq_A X</math>

この関係における同値類を'''算術次数'''（arithmetic degrees）と呼ぶ。これらは <math>\leq_A</math> のもとで半順序的である。

== 関連項目 ==
* [[再帰理論]]
* [[ポストの定理]]

== 参考文献 ==
{{参照方法|date=2023年8月}}
* [http://www.csc.villanova.edu/~japaridz/ G.Japaridze], "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic '''66''' (1994), pp.89-112.
* {{cite book | author=Moschovakis, Yiannis N. | title=Descriptive Set Theory | publisher=North Holland | date=1980年 |id=ISBN 0-444-70199-0}}
* {{cite book | author=Rogers, H. | title= Theory of recursive functions and effective computability|
publisher=McGraw-Hill | date=1967年}}

{{複雑性クラス}}

{{DEFAULTSORT:さんしゆつてきかいそう}}
[[Category:数理論理学的階層]]
[[Category:エフェクティブ記述集合論]]
[[Category:数学に関する記事]]