算術的階層

算術的階層(さんじゅつてきかいそう、英: Arithmetical hierarchy)は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層(Kleene hierarchy)とも。このような分類が可能な集合は算術的である。

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

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

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

式 ${\displaystyle \phi }${\displaystyle \phi } が有界量化子しか含まない式と論理的に等価であれば、${\displaystyle \phi }${\displaystyle \phi } は階層 ${\displaystyle \Sigma _{0}^{0}}${\displaystyle \Sigma _{0}^{0}} と ${\displaystyle \Pi _{0}^{0}}${\displaystyle \Pi _{0}^{0}} に相当する。

階層 ${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}} と ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}} は、全ての自然数 n について以下のように帰納的に定義される。

• ${\displaystyle \psi }${\displaystyle \psi } が ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}} であるとき、${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi }${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi } という形式と論理的に等価な式 ${\displaystyle \phi }${\displaystyle \phi } は、階層 ${\displaystyle \Sigma _{n+1}^{0}}${\displaystyle \Sigma _{n+1}^{0}} に相当する。
• ${\displaystyle \psi }${\displaystyle \psi } が ${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}} であるとき、${\displaystyle \forall n_{l}\cdots \forall n_{k}\psi }${\displaystyle \forall n_{l}\cdots \forall n_{k}\psi } という形式と論理的に等価な式 ${\displaystyle \phi }${\displaystyle \phi } は、階層 ${\displaystyle \Pi _{n+1}^{0}}${\displaystyle \Pi _{n+1}^{0}} に相当する。

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

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

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

なお、${\displaystyle \Delta _{n}^{0}}${\displaystyle \Delta _{n}^{0}} に属する式と言った場合、ほとんど意味をなさない。これはつまり、先頭の量化子が存在量化子か全称量化子の式を意味する。従って ${\displaystyle \Delta _{n}^{0}}${\displaystyle \Delta _{n}^{0}} に属する集合は ${\displaystyle \Delta _{n}^{0}}${\displaystyle \Delta _{n}^{0}} に属する式で定義されるのではなく、${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}} に属する式と ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}} に属する式の両方で定義される集合である。

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

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

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

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

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

${\displaystyle X\leq _{A}Y}${\displaystyle X\leq _{A}Y} は反射関係かつ推移関係であり、したがって ${\displaystyle \equiv _{A}}${\displaystyle \equiv _{A}} という関係を次のように定義すると、これは同値関係となる。

${\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X}${\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X}

この関係における同値類を算術次数(arithmetic degrees)と呼ぶ。これらは ${\displaystyle \leq _{A}}${\displaystyle \leq _{A}} のもとで半順序的である。

• 再帰理論
• ポストの定理

• G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
• Moschovakis, Yiannis N. (1980年). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0  
• Rogers, H. (1967年). Theory of recursive functions and effective computability. McGraw-Hill 

• 数理論理学的階層
• エフェクティブ記述集合論
• 数学に関する記事

• 参照方法
• ISBNマジックリンクを使用しているページ