算術的階層
集合 X が 集合 Y に対して再帰的相対性を持つということを、Y を一種の神託機械として X を求められることと定義すると、これを算術的階層全体に拡張し、Y に対して X が Σ n 0 {\displaystyle \Sigma _{n}^{0}} 、 Δ n 0 {\displaystyle \Delta _{n}^{0}} 、 Π n 0 {\displaystyle \Pi _{n}^{0}} であるということをそれぞれ Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} 、 Δ n 0 , Y {\displaystyle \Delta _{n}^{0,Y}} 、 Π n 0 , Y {\displaystyle \Pi _{n}^{0,Y}} と記述する。このために、整数の集合Y を固定し、ペアノ算術の言語に Y のメンバーシップ述語を追加する。X が Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} に属するとは、この拡張された言語で書かれた Σ n 0 {\displaystyle \Sigma _{n}^{0}} の式で定義されることを意味する。
X ≤ A Y {\displaystyle X\leq _{A}Y} は、X が Y に算術還元可能であることを意味する。
X ≤ A Y {\displaystyle X\leq _{A}Y} は反射関係かつ推移関係であり、したがって ≡ A {\displaystyle \equiv _{A}} という関係を次のように定義すると、これは同値関係となる。
X ≡ A Y ⇔ X ≤ A Y ∧ Y ≤ A X {\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X}
この関係における同値類を算術次数(arithmetic degrees)と呼ぶ。これらは ≤ A {\displaystyle \leq _{A}} のもとで半順序的である。