極限計算可能関数
e.集合のクラス Σ n − 1 {\displaystyle \Sigma _{n}^{-1}} 、co- n {\displaystyle n} -r.e.集合のクラス Π n − 1 {\displaystyle \Pi _{n}^{-1}} は、それぞれ算術的階層における Δ n 0 , Σ n 0 , Π n 0 {\displaystyle \Delta _{n}^{0},\Sigma _{n}^{0},\Pi _{n}^{0}} と対応する形の階層構造を成している。すなわちこの階層は次のような構造を持つ。ここで矢印は包含を示す。
Σ 1 − 1 Σ 2 − 1 ⋯ ↗ ↘ ↗ Δ 1 − 1 Δ 2 − 1 ⋯ ↘ ↗ ↘ Π 1 − 1 Π 2 − 1 ⋯ Σ n − 1 ⋯ ↗ ↘ Δ n − 1 Δ n + 1 − 1 ⋯ ↘ ↗ Π n − 1 ⋯ {\displaystyle {\begin{matrix}&&\Sigma _{1}^{-1}&&&&\Sigma _{2}^{-1}&&\cdots \\&\nearrow &&\searrow &&\nearrow \\\Delta _{1}^{-1}&&&&\Delta _{2}^{-1}&&&&\cdots \\&\searrow &&\nearrow &&\searrow \\&&\Pi _{1}^{-1}&&&&\Pi _{2}^{-1}&&\cdots \end{matrix}}{\begin{matrix}&&\Sigma _{n}^{-1}&&&\cdots \\&\nearrow &&\searrow \\\quad \Delta _{n}^{-1}&&&&\Delta _{n+1}^{-1}&\cdots \\&\searrow &&\nearrow \\&&\Pi _{n}^{-1}&&&\cdots \end{matrix}}}