算術的階層

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

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

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

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

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

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

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

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

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

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

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