算術的階層
言い換えれば、X が Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} に属するとは、その中でY に属するかどうかの質問が許されている Σ n 0 {\displaystyle \Sigma _{n}^{0}} に属する論理式で定義されることを意味する。
例えば、Y を整数の集合とする。X は、ある Y の元で割り切れる数の集合とする。すると X は式 φ ( n ) = ∃ m ∃ t ( Y ( m ) ∧ m × t = n ) {\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)} で定義されるので、X は Σ 1 0 , Y {\displaystyle \Sigma _{1}^{0,Y}} に属することになる(実際には、2つの量化子を n で制限できるので Δ 0 0 , Y {\displaystyle \Delta _{0}^{0,Y}} に属する)。
ペアノ算術の言語で書かれた式 φ(n) で、集合 X が n ∈ X ↔ N ⊨ φ ( n ) {\displaystyle n\in X\leftrightarrow \mathbb {N} \models \phi (n)} のように定義されるとする。これはつまり、X の元が φ を満足する数ということを意味している。集合が一階算術で定義可能であるとは、ペアノ算術の言語で書かれた式で定義されることに他ならない。
一階算術で定義可能な自然数の集合 X は、 n {\displaystyle n} を自然数としたときの階層 Σ n 0 {\displaystyle \Sigma _{n}^{0}} 、 Π n 0 {\displaystyle \Pi _{n}^{0}} 、 Δ n 0 {\displaystyle \Delta _{n}^{0}} に以下のように分類される。X が Σ n 0 {\displaystyle \Sigma _{n}^{0}} に属する式で定義可能なら、 X {\displaystyle X} は階層 Σ n 0 {\displaystyle \Sigma _{n}^{0}} に分類される。X が Π n 0 {\displaystyle \Pi _{n}^{0}} に属する式で定義可能なら、 X {\displaystyle X} は階層 Π n 0 {\displaystyle \Pi _{n}^{0}} に分類される。