算術的階層

同義語：arithmetical hierarchyarithmetic hierarchy

概要

前提知識: 計算可能性理論, 計算可能関数, 帰納的可算集合

算術的階層（arithmetical hierarchy）は、自然数の集合や関係を、決定可能な関係に $\exists$ と $\forall$ を交互に何回付けると定義できるかで分類する階層である。自己停止集合 $K=\{e\mid\exists s\ T(e,e,s)\}$ は決定可能な関係に $\exists$ を 1 つ付けた形で、全域的な関数の番号の集合 $\mathrm{Tot}=\{e\mid\forall y\ \exists s\ T(e,y,s)\}$ は $\forall\exists$ の形である。計算可能性理論の記事の定理「全域性の集合とその補集合はどちらも半決定可能でない」は、この量化記号の形の違いが本当に難しさの違いであることの最初の例である。算術的階層は Kleene（1943）と Mostowski（1946）が独立に導入した（Mos09 3J 節の注 4、p. 142）。
この記事では、階層の各段 $\Sigma^0_n$・$\Pi^0_n$・$\Delta^0_n$ を定義し、論理演算と有界・無界の量化についての閉包性、$\Sigma^0_1$ が半決定可能な集合にちょうど一致すること、各段が真に大きくなっていくこと（階層定理）を証明する。さらに $K$・$\mathrm{Tot}$・有限集合を定義域にもつ番号の集合が、それぞれの段の完全な集合であることを示し、算術的な関係が自然数の構造で一階の論理式によって定義できる関係にちょうど一致することを述べる。

定義

記号と番号付け $\varphi_e$、$W_e:=\operatorname{dom}\varphi_e$、性質 (N1)〜(N4)、多対一還元 $\le_{\mathrm m}$、$K$・$\mathrm{Tot}$ は計算可能性理論の記事の「記法と前提」と「定義」に従う。とくに (N3) の原始再帰的な関係 $T$ について $\varphi_e(x)\!\downarrow\iff\exists s\ T(e,x,s)$ である。$\mathbb N^k$ の部分集合を $k$ 変数の関係とよび、$R(\vec x)$ と $\vec x\in R$ を同じ意味に使う。関係が 決定可能 であるとは、その特性関数が計算可能であることをいう。
計算可能な全単射 $\langle\cdot,\cdot\rangle\colon\mathbb N^2\to\mathbb N$ で、逆写像の成分 $w\mapsto(w)_0$、$w\mapsto(w)_1$ も計算可能なものを 1 つ固定する（$\langle y,z\rangle:=\tfrac12(y+z)(y+z+1)+z$ がその例である）。また、列の符号として、$v\ge1$ の素因数分解で $i$ 番目の素数 $p_i$（$p_0=2$）が現れる回数を $[v]_i$ とおき、$[0]_i:=0$ とする。$(v,i)\mapsto[v]_i$ は計算可能であり、有限列 $a_0,\dots,a_{z-1}$ に対して $v:=p_0^{a_0}\cdots p_{z-1}^{a_{z-1}}$ とおけば $i< z$ で $[v]_i=a_i$ となる。

算術的階層

$n\ge0$ について、関係のクラス $\Sigma^0_n$・$\Pi^0_n$・$\Delta^0_n$ を次で定める。

$\Sigma^0_0=\Pi^0_0$ は決定可能な関係の全体とする。
$k$ 変数の関係 $R$ が $\Sigma^0_{n+1}$ に属するとは、$\Pi^0_n$ に属する $k+1$ 変数の関係 $S$ で、すべての $\vec x$ について
$$ R(\vec x)\iff\exists y\ S(\vec x,y) $$
となるものがあることをいう。$\Pi^0_{n+1}$ に属するとは、$\Sigma^0_n$ に属する $S$ で $R(\vec x)\iff\forall y\ S(\vec x,y)$ となるものがあることをいう。量化される変数は $\mathbb N$ を動く。
$\Delta^0_n:=\Sigma^0_n\cap\Pi^0_n$ とする。
どれかの $\Sigma^0_n$ に属する関係を 算術的（arithmetical）であるという。$\Sigma^0_n$ に属する関係を単に $\Sigma^0_n$ の関係、$\Sigma^0_n$ の集合などとよぶ。

定義を繰り返しほどくと、$n\ge1$ について、$R$ が $\Sigma^0_n$ であることは、決定可能な関係 $D$ で
$$ R(\vec x)\iff\exists y_1\,\forall y_2\,\exists y_3\cdots\mathsf Q y_n\ D(\vec x,y_1,\dots,y_n) $$
（$\mathsf Q$ は $n$ が奇数なら $\exists$、偶数なら $\forall$）となるものがあることと同値である。$\Pi^0_n$ は $\forall$ から始まる同じ形である。上付きの $0$ は、量化が自然数を動くことを表す。自然数から自然数への関数を動く量化まで許すと解析的階層 $\Sigma^1_n$ になる（Mos09 3E 節、p. 118）。この記事の $\Sigma^0_n$ は Mos09 3E 節（p. 118）の $\Sigma^0_n$ を $\mathbb N^k$ に制限したものと一致する。そこでは $\Sigma^0_1$ を半決定可能な関係の全体として定義しており、一致は thm-ah-sigma1 による。

階層の例

$K=\{e\mid\exists s\ T(e,e,s)\}$ と $\{e\mid W_e\ne\emptyset\}=\{e\mid\exists w\ T(e,(w)_0,(w)_1)\}$ は $\Sigma^0_1$ である（後者は $\exists y\,\exists s$ を 1 つの $\exists w$ にまとめたもので、prop-ah-basic の 2 により $T(e,(w)_0,(w)_1)$ は決定可能である）。$\mathbb N\setminus K$ と $\{e\mid W_e=\emptyset\}$ は $\Pi^0_1$ である。
$\mathrm{Tot}=\{e\mid\forall y\ \exists s\ T(e,y,s)\}$ と $\mathrm{Inf}:=\{e\mid W_e\text{ は無限集合}\}=\{e\mid\forall m\ \exists y\ \exists s\ (y\ge m\land T(e,y,s))\}$ は $\Pi^0_2$ である。
$\mathrm{Fin}:=\{e\mid W_e\text{ は有限集合}\}=\mathbb N\setminus\mathrm{Inf}$ は $\Sigma^0_2$ である。
$\mathrm{Cof}:=\{e\mid\mathbb N\setminus W_e\text{ は有限集合}\}=\{e\mid\exists m\ \forall y\ \exists s\ (y< m\lor T(e,y,s))\}$ は $\Sigma^0_3$ である。
どれも定義の右辺の量化記号の並びを読めばよく、決定可能な部分は $T$ と大小関係の論理結合である（prop-ah-closure の 1）。

基本的な性質

補集合・包含・代入

$n\ge0$ とする。

$R$ が $\Pi^0_n$ であることと、補集合 $\mathbb N^k\setminus R$ が $\Sigma^0_n$ であることは同値である。
$R$ が $m$ 変数の $\Sigma^0_n$ の関係で、$f_1,\dots,f_m\colon\mathbb N^k\to\mathbb N$ が計算可能なら、$\{\vec x\mid R(f_1(\vec x),\dots,f_m(\vec x))\}$ も $\Sigma^0_n$ である。$\Pi^0_n$ でも同じである。とくに、$A\le_{\mathrm m}B$ で $B$ が $\Sigma^0_n$（$\Pi^0_n$）なら $A$ も $\Sigma^0_n$（$\Pi^0_n$）である。
$\Sigma^0_n\cup\Pi^0_n\subset\Delta^0_{n+1}$ である。

$n$ についての帰納法

どれも $n$ についての帰納法で、定義の $\exists y$・$\forall y$ の中身に帰納法の仮定を当てる。

詳細

1：$n=0$ では決定可能な関係の補集合は決定可能である。$R(\vec x)\iff\exists y\ S(\vec x,y)$（$S$ は $\Pi^0_n$）なら $\lnot R(\vec x)\iff\forall y\ \lnot S(\vec x,y)$ であり、帰納法の仮定により $\lnot S$ は $\Sigma^0_n$ なので、$\lnot R$ は $\Pi^0_{n+1}$ である。逆向きと、$\Pi^0_{n+1}$ から始める場合も同じである。

2：$n=0$ では計算可能関数の合成で特性関数が得られる。$R(\vec u)\iff\exists y\ S(\vec u,y)$ なら $R(f_1(\vec x),\dots,f_m(\vec x))\iff\exists y\ S(f_1(\vec x),\dots,f_m(\vec x),y)$ であり、右辺の $\exists y$ の中は、帰納法の仮定を計算可能関数 $f_1,\dots,f_m$ と射影 $(\vec x,y)\mapsto y$ に使えば $\Pi^0_n$ である。$\Pi^0_{n+1}$ も同じである。$f$ が $A$ から $B$ への多対一還元なら $A=\{x\mid B(f(x))\}$ である。

3：$n$ についての帰納法で示す。$R$ を決定可能とすると、2 により $S(\vec x,y):\iff R(\vec x)$ も決定可能で、$R(\vec x)\iff\exists y\ S(\vec x,y)\iff\forall y\ S(\vec x,y)$ なので $R$ は $\Sigma^0_1$ かつ $\Pi^0_1$ である。$R$ が $\Sigma^0_{n+1}$ で $R(\vec x)\iff\exists y\ S(\vec x,y)$（$S$ は $\Pi^0_n$）とする。帰納法の仮定により $S$ は $\Pi^0_{n+1}$ なので $R$ は $\Sigma^0_{n+2}$ である。また $S'(\vec x,z):\iff R(\vec x)$ は 2 により $\Sigma^0_{n+1}$ で、$R(\vec x)\iff\forall z\ S'(\vec x,z)$ なので $R$ は $\Pi^0_{n+2}$ である。$\Pi^0_{n+1}$ の関係も同じである。$\square$

量化記号を付ける操作について、各段は次のように閉じている。$\forall y< z\ S(\vec x,y)$ は「$y< z$ を満たすすべての $y$ について」を表す 有界な量化 で、$\exists y< z$ も同様である。

論理演算と量化についての閉包性

決定可能な関係の全体 $\Sigma^0_0$ は、$\land$・$\lor$・否定 $\lnot$ と有界な量化 $\forall y< z$・$\exists y< z$ で閉じている。
$n\ge1$ について、$\Sigma^0_n$ は $\land$・$\lor$・$\exists y$・$\forall y< z$・$\exists y< z$ で閉じており、$\Pi^0_n$ は $\land$・$\lor$・$\forall y$・$\exists y< z$・$\forall y< z$ で閉じている。
$\Delta^0_n$ は $\land$・$\lor$・$\lnot$ で閉じている。

ここで、たとえば「$\Sigma^0_n$ が $\land$ で閉じている」とは、$R,R'$ が同じ変数をもつ $\Sigma^0_n$ の関係なら $R\land R'$ も $\Sigma^0_n$ であることをいう。変数をそろえることは prop-ah-basic の 2 でできる。

同じ種類の量化記号をまとめる

要点は 2 つある。同じ種類の量化記号が続くときは $\langle\cdot,\cdot\rangle$ で 1 つにまとめられる：$\exists y\,\exists y'\ S(\vec x,y,y')\iff\exists w\ S(\vec x,(w)_0,(w)_1)$。有界な $\forall$ は、各 $y< z$ の証拠を列の符号 1 つにまとめて、$\exists$ の外に出せる：
$$ \forall y< z\ \exists u\ S(\vec x,z,y,u)\iff\exists v\ \forall y< z\ S(\vec x,z,y,[v]_y). $$
右から左は $u:=[v]_y$ とすればよく、左から右は各 $y< z$ について証拠 $u_y$ を選び、$[v]_y=u_y$（$y< z$）となる $v$ をとればよい。

詳細

1：特性関数を $\chi_R,\chi_{R'}$ とすると、$\chi_{R\land R'}=\chi_R\chi_{R'}$、$\chi_{R\lor R'}=\chi_R+\chi_{R'}-\chi_R\chi_{R'}$、$\chi_{\lnot R}=1-\chi_R$ である。$\forall y< z\ S(\vec x,y)$ の特性関数は $\prod_{y< z}\chi_S(\vec x,y)$ で、$z$ についての原始再帰で計算できる。$\exists y< z$ はその否定を使う。

2：$n$ についての帰納法で、$\Sigma^0_n$ と $\Pi^0_n$ の主張を同時に示す。prop-ah-basic の 1 により $\Pi^0_n$ の主張は $\Sigma^0_n$ の主張の補集合をとったもの（$\land$ と $\lor$、$\exists$ と $\forall$ が入れ替わる）なので、$\Sigma^0_n$ について示せばよい。$R(\vec x)\iff\exists y\ S(\vec x,y)$、$R'(\vec x)\iff\exists y\ S'(\vec x,y)$ で、$S,S'$ は $\Pi^0_{n-1}$ とする（$n=1$ なら決定可能）。$\Pi^0_{n-1}$ は $\land$・$\lor$・$\forall y< z$ で閉じている（$n=1$ なら 1、$n\ge2$ なら帰納法の仮定による）。

$\land$：$R\land R'\iff\exists w\ (S(\vec x,(w)_0)\land S'(\vec x,(w)_1))$。$\lor$：$R\lor R'\iff\exists y\ (S(\vec x,y)\lor S'(\vec x,y))$。$\exists$：$\exists z\ R(\vec x,z)\iff\exists w\ S(\vec x,(w)_0,(w)_1)$。どれも中身は prop-ah-basic の 2 と $\Pi^0_{n-1}$ の閉包性により $\Pi^0_{n-1}$ である。$\forall y< z$：上の同値の右辺の $\forall y< z\ S(\vec x,z,y,[v]_y)$ は、$\Pi^0_{n-1}$ の関係に計算可能関数を代入して有界な $\forall$ を付けたものなので $\Pi^0_{n-1}$ であり、左辺は $\Sigma^0_n$ である。$\exists y< z\ R(\vec x,z,y)\iff\exists w\ ((w)_0< z\land S(\vec x,z,(w)_0,(w)_1))$ で、$(w)_0< z$ は決定可能なので prop-ah-basic の 3 により $\Pi^0_{n-1}$ に属し、中身は $\Pi^0_{n-1}$ である。$n\ge2$ の $\Pi^0_{n-1}$ が $\forall y< z$ で閉じていることは、$\forall y< z\ P\iff\forall y\ (y\ge z\lor P)$ と、$\Pi^0_{n-1}$ が $\lor$ と $\forall$ で閉じていること（帰納法の仮定）による。

3：$\Sigma^0_n$ と $\Pi^0_n$ がともに $\land$・$\lor$ で閉じていること（$n=0$ では 1）と、prop-ah-basic の 1 による。$\square$

閉包性により、決定可能な関係から $\land$・$\lor$・有界な量化と、$\exists$ から始まり交互に $n$ ブロック（同じ種類の量化記号の続き）の量化記号で作った関係は $\Sigma^0_n$ である。有界な $\forall$ を $\exists$ の外に出す上の同値は、「証拠を有限個まとめて選ぶ」ことに相当する。無界な $\forall$ では外に出せない（下の反例の表の 1 行目）。

半決定可能な集合との関係

半決定可能な集合と決定可能な集合

$A\subset\mathbb N$ とする。

$A$ が $\Sigma^0_1$ であることと、$A$ が半決定可能であることは同値である。
$A$ が $\Delta^0_1$ であることと、$A$ が決定可能であることは同値である。

1：$A(x)\iff\exists y\ S(x,y)$（$S$ は決定可能）なら、$g(x):\simeq\mu y\,[\,1\mathbin{\dot-}\chi_S(x,y)=0\,]$ は部分計算可能で、$g(x)\!\downarrow\iff\exists y\ S(x,y)$ なので $A=\operatorname{dom}g$ は半決定可能である。逆に $A$ が半決定可能なら、(N1) により $A=W_e$ となる $e$ があり、(N3) により $A=\{x\mid\exists s\ T(e,x,s)\}$ で $T$ は決定可能なので、$A$ は $\Sigma^0_1$ である。
2：$A$ が決定可能なら prop-ah-basic の 3 により $\Delta^0_1$ である。$A$ が $\Delta^0_1$ なら、1 と prop-ah-basic の 1 により $A$ と $\mathbb N\setminus A$ はともに半決定可能であり、停止問題の記事の定理「決定可能性と半決定可能性」により $A$ は決定可能である。$\square$

$\mathbb N^k$ の関係についても、$\langle\cdot,\cdot\rangle$ を繰り返して $\mathbb N^k$ と $\mathbb N$ を計算可能な全単射で結べば、同じことが成り立つ。

階層定理

各段に、その段のすべての集合を番号で並べる関係がある。

万能な関係

$n\ge1$ について、$\Sigma^0_n$ の 2 変数の関係 $U_n$ で、次を満たすものがある：$\Sigma^0_n$ の集合 $A\subset\mathbb N$ ごとに $e$ があって $A=\{x\mid U_n(e,x)\}$ となる。

$n$ についての帰納法

$n=1$：$U_1(e,x):\iff\exists s\ T(e,x,s)$ とおく。$U_1$ は $\Sigma^0_1$ であり、thm-ah-sigma1 の 1 により $\Sigma^0_1$ の集合 $A$ は $A=W_e=\{x\mid U_1(e,x)\}$ と書ける。
$n\to n+1$：$U_{n+1}(e,x):\iff\exists y\ \lnot U_n(e,\langle x,y\rangle)$ とおけばよい。

詳細

prop-ah-basic の 1・2 により $\lnot U_n(e,\langle x,y\rangle)$ は $\Pi^0_n$ なので、$U_{n+1}$ は $\Sigma^0_{n+1}$ である。$A$ を $\Sigma^0_{n+1}$ の集合とし、$A(x)\iff\exists y\ S(x,y)$（$S$ は $\Pi^0_n$）とする。$B:=\{w\mid\lnot S((w)_0,(w)_1)\}$ は prop-ah-basic の 1・2 により $\Sigma^0_n$ の集合なので、帰納法の仮定により $B=\{w\mid U_n(e,w)\}$ となる $e$ がある。すると $A(x)\iff\exists y\ S(x,y)\iff\exists y\ \lnot B(\langle x,y\rangle)\iff\exists y\ \lnot U_n(e,\langle x,y\rangle)\iff U_{n+1}(e,x)$ である。$\square$

階層定理

$n\ge1$ とし、$D_n:=\{x\mid U_n(x,x)\}$ とおく。

$D_n$ は $\Sigma^0_n$ に属するが $\Pi^0_n$ に属さない。$\mathbb N\setminus D_n$ は $\Pi^0_n$ に属するが $\Sigma^0_n$ に属さない。
$\mathbb N$ の部分集合のクラスとして、$\Delta^0_n\subsetneq\Sigma^0_n\subsetneq\Delta^0_{n+1}$、$\Delta^0_n\subsetneq\Pi^0_n\subsetneq\Delta^0_{n+1}$ であり、$\Sigma^0_n\ne\Pi^0_n$ である。

対角線論法

1：$D_n$ は $U_n$ に $x\mapsto(x,x)$ を代入したものなので、prop-ah-basic の 2 により $\Sigma^0_n$ である。$D_n$ が $\Pi^0_n$ だとすると、$\mathbb N\setminus D_n$ は $\Sigma^0_n$ なので、lem-ah-universal により $\mathbb N\setminus D_n=\{x\mid U_n(e,x)\}$ となる $e$ がある。$x=e$ とおくと
$$ e\notin D_n\iff U_n(e,e)\iff e\in D_n $$
となって矛盾する。後半は前半と prop-ah-basic の 1 による。
2：包含は定義と prop-ah-basic の 3 による。1 により $D_n\in\Sigma^0_n\setminus\Pi^0_n$ なので $\Sigma^0_n\ne\Pi^0_n$、$\Delta^0_n\ne\Sigma^0_n$ であり、$\mathbb N\setminus D_n\in\Delta^0_{n+1}\setminus\Sigma^0_n$ なので $\Sigma^0_n\ne\Delta^0_{n+1}$ である。$\Pi^0_n$ についても $D_n$ と $\mathbb N\setminus D_n$ の役割を入れ替えればよい。$\square$

$n=1$ の $D_1=\{x\mid\exists s\ T(x,x,s)\}$ は $K$ そのものであり、1 は計算可能性理論の記事の定理「自己停止集合の決定不能性」の後半にあたる。階層定理は、各段で同じ対角線論法を繰り返したものである（Mos09 3F.7 の階層定理、p. 130 は、一般の積空間の上で同じ包含の図を述べている）。

完全な集合

$n\ge1$ とする。$A\subset\mathbb N$ が $\Sigma^0_n$ に属し、$\Sigma^0_n$ のすべての集合 $B\subset\mathbb N$ について $B\le_{\mathrm m}A$ となるとき、$A$ は $\Sigma^0_n$ 完全 であるという。$\Pi^0_n$ 完全も同様に定める。

$A$ が $\Sigma^0_n$ 完全なら $A$ は $\Pi^0_n$ に属さない。属するとすると、prop-ah-basic の 2 によりすべての $\Sigma^0_n$ の集合が $\Pi^0_n$ に属し、thm-ah-hierarchy の 1 の $D_n$ に反するからである。同じ理由で、$\Pi^0_n$ 完全な集合は $\Sigma^0_n$ に属さない。また、同じ $f$ が $B$ から $A$ への多対一還元であることと $\mathbb N\setminus B$ から $\mathbb N\setminus A$ への多対一還元であることは同値なので、prop-ah-basic の 1 により、$A$ が $\Sigma^0_n$ 完全であることと $\mathbb N\setminus A$ が $\Pi^0_n$ 完全であることは同値である。

完全な集合の例

$K$ は $\Sigma^0_1$ 完全である。
$\mathrm{Tot}$ は $\Pi^0_2$ 完全である。
$\mathrm{Fin}=\{e\mid W_e\text{ は有限集合}\}$ は $\Sigma^0_2$ 完全であり、$\mathrm{Inf}=\mathbb N\setminus\mathrm{Fin}$ は $\Pi^0_2$ 完全である。
とくに $\mathrm{Tot}$ と $\mathrm{Inf}$ は $\Sigma^0_2$ に属さず、$\mathrm{Fin}$ は $\Pi^0_2$ に属さない。

証拠を探す計算の番号を作る

どの集合も ex-ah-examples によりそれぞれの段に属する。以下、計算可能関数 $\sigma$ は (N4) のものである。
1：thm-ah-sigma1 の 1 により $\Sigma^0_1$ の集合は半決定可能な集合なので、計算可能性理論の記事の定理「自己停止集合の完全性」そのものである。
2：$A$ を $\Pi^0_2$ の集合とする。定義により、決定可能な $R$ で $A(x)\iff\forall y\ \exists z\ R(x,y,z)$ となるものがある。$h(x,y):\simeq\mu z\,[\,1\mathbin{\dot-}\chi_R(x,y,z)=0\,]$ は部分計算可能で、$h(x,y)\!\downarrow\iff\exists z\ R(x,y,z)$ である。(N1) により $h=\varphi^{(2)}_c$ となる $c$ をとり、$f(x):=\sigma(c,x)$ とおくと、$f$ は計算可能で $\varphi_{f(x)}(y)\simeq h(x,y)$ である。よって
$$ f(x)\in\mathrm{Tot}\iff\forall y\ h(x,y)\!\downarrow\iff\forall y\ \exists z\ R(x,y,z)\iff A(x) $$
であり、$f$ は $A$ から $\mathrm{Tot}$ への多対一還元である。
3：$A$ を $\Sigma^0_2$ の集合とし、決定可能な $R$ で $A(x)\iff\exists y\ \forall z\ R(x,y,z)$ となるものをとる。
$$ g(x,m):\simeq\mu v\,\bigl[\,\forall y\le m\ \exists z\le v\ \lnot R(x,y,z)\,\bigr] $$
とおく。括弧の中は prop-ah-closure の 1 により決定可能なので、$g$ は部分計算可能であり、$g(x,m)\!\downarrow$ は「$m$ 以下のすべての $y$ について、$\lnot R(x,y,z)$ となる $z$ がある」と同値である（各 $y$ の $z$ の最大値を $v$ にとればよい）。2 と同じく $g=\varphi^{(2)}_c$ とし、$f(x):=\sigma(c,x)$ とおくと $W_{f(x)}=\{m\mid g(x,m)\!\downarrow\}$ である。
$A(x)$ のとき、$\forall z\ R(x,y_0,z)$ となる $y_0$ をとると、$m\ge y_0$ では $y=y_0$ に対する $z$ がないので $g(x,m)\!\uparrow$ であり、$W_{f(x)}\subset\{0,\dots,y_0-1\}$ は有限集合である。$A(x)$ でないとき、すべての $y$ に $\lnot R(x,y,z)$ となる $z$ があるので、すべての $m$ で $g(x,m)\!\downarrow$ となり $W_{f(x)}=\mathbb N$ は無限集合である。よって $f$ は $A$ から $\mathrm{Fin}$ への多対一還元である。$\mathrm{Inf}$ については上の注意による。
最後の主張は、定義の直後の注意による。$\square$

2 の還元は「$y$ ごとに証拠 $z$ を探す計算」であり、全域的になるのはすべての $y$ に証拠があるときだけである。3 の還元は、入力 $m$ で「$m$ 以下のどの $y$ についても、$y$ が証拠でないことの確認（$\lnot R(x,y,z)$ となる $z$）を探す計算」であり、証拠 $y_0$ があればそれより先の入力で止まらなくなる。計算可能性理論の記事の定理「全域性の集合とその補集合はどちらも半決定可能でない」は、2 から $\mathrm{Tot}\notin\Sigma^0_1\cup\Pi^0_1$ として改めて得られる（$\Sigma^0_1\cup\Pi^0_1\subset\Delta^0_2$ に属する集合は $\Pi^0_2$ 完全でありえない）。

論理式による定義

算術の言語を $L_A=\{0,S,+,\cdot,<\}$、その標準的な構造を $\mathfrak N=(\mathbb N,0,S,+,\cdot,<)$ とする（Tarskiの真理定義の記事の記号）。$k$ 変数の関係 $R$ が $\mathfrak N$ で 定義可能 であるとは、自由変数が $v_1,\dots,v_k$ の中にある $L_A$ の論理式 $\varphi$ で、すべての $\vec n$ について $R(\vec n)\iff\mathfrak N\models\varphi[\vec n]$ となるものがあることをいう。

算術的な関係と定義可能な関係

関係が算術的であることと、$\mathfrak N$ で定義可能であることは同値である。

定義可能なら算術的。 論理式 $\varphi$ の組み立てについての帰納法で、$\varphi$ が定める関係が算術的であることを示す。項の値は変数の値の多項式なので計算可能であり、原子論理式 $t_1=t_2$・$t_1< t_2$ が定める関係は決定可能である。算術的な関係は、prop-ah-basic の 3 により、どれも十分大きい $m$ について $\Delta^0_m$ に属する。2 つの関係を同じ $\Delta^0_m$ にとれば、prop-ah-closure の 3 により $\land$・$\lor$・$\lnot$ をとった関係も $\Delta^0_m$ である（$\to$ は $\lnot$ と $\lor$ で書ける）。$\Delta^0_m\subset\Sigma^0_m$ なので $\exists v\,\varphi$ が定める関係は prop-ah-closure の 2 により $\Sigma^0_m$、$\Delta^0_m\subset\Pi^0_m$ なので $\forall v\,\varphi$ が定める関係は $\Pi^0_m$ である。
算術的なら定義可能。 決定可能な関係 $R$ は Robinson の算術 $\mathsf Q$ で表現可能である（OLT26 Definition 35.28・Theorem 35.29、p. 567。この記事では証明しない）。すなわち論理式 $\varphi_R$ で、$R(\vec n)$ なら $\mathsf Q\vdash\varphi_R(\underline{\vec n})$、そうでなければ $\mathsf Q\vdash\lnot\varphi_R(\underline{\vec n})$ となるものがある（$\underline n$ は数項）。$\mathfrak N$ は $\mathsf Q$ のモデルなので、健全性により $\varphi_R$ は $\mathfrak N$ で $R$ を定義する。あとは $n$ についての帰納法で、$R(\vec x)\iff\exists y\ S(\vec x,y)$ で $S$ が $\varphi_S$ で定義されるなら $R$ は $\exists y\,\varphi_S$ で定義される（$\forall$ も同じ）。$\square$

証明から、$n\ge1$ について、$\Sigma^0_n$ の関係は $\exists$ から始まる $n$ ブロックの量化記号を、決定可能な関係を定義する論理式の前に付けた論理式で定義できる。

真理の集合は算術的でない

$\mathfrak N$ で真な $L_A$ の文の Gödel 数の集合は算術的でない。とくに、それはどの $\Sigma^0_n$ にも属さない。

算術的なら thm-ah-definable により $\mathfrak N$ で定義可能になり、Tarskiの真理定義の記事の定理「Tarski の真理の定義不可能性定理」に反する（Gödel 数はその記事と Gödel数化の記事のものを使う）。$\square$

したがって、算術の文の真偽の全体は、算術的階層のどの段にも収まらない。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
量化が有界（prop-ah-closure の 2 の $\Sigma^0_1$ の $\forall y< z$）	$\Sigma^0_1$ の関係 $W(e,y):\iff\varphi_e(y)\!\downarrow$ に無界な $\forall y$ を付けた $\mathrm{Tot}$	$\Sigma^0_1$ に属すること
演算に否定を含まない（prop-ah-closure の 2）	$\Sigma^0_1$ の集合 $K$ の補集合	$\Sigma^0_1$ に属すること
$n\ge1$（thm-ah-hierarchy の 2）	$n=0$	$\Sigma^0_n\ne\Pi^0_n$
包含の向き（prop-ah-basic の 3 の逆向き $\Delta^0_{n+1}\subset\Sigma^0_n\cup\Pi^0_n$）	$n=1$ と $J:=\{2x\mid x\in K\}\cup\{2x+1\mid x\notin K\}$	$\Delta^0_2$ の集合がすべて $\Sigma^0_1$ か $\Pi^0_1$ に属すること

反例の確かめ

1・2 行目は既知の定理を当て、3 行目は定義を見て、4 行目は還元で確かめる。

詳細

1 行目：$W$ は (N3) により $\exists s\ T(e,y,s)$ と書けるので $\Sigma^0_1$ であり、$\forall y\ W(e,y)$ は $\mathrm{Tot}$ を定める。thm-ah-complete の 2 と定義の直後の注意により $\mathrm{Tot}$ は $\Sigma^0_2$ にも属さないので、とくに $\Sigma^0_1$ に属さない（prop-ah-basic の 3）。

2 行目：$K$ は $\Sigma^0_1$ だが、$\mathbb N\setminus K$ は thm-ah-hierarchy の 1（$D_1=K$）により $\Sigma^0_1$ に属さない。$\Sigma^0_n$ は否定で閉じていない。

3 行目：$\Sigma^0_0$ と $\Pi^0_0$ はともに決定可能な関係の全体と定めたので等しい。

4 行目：$x$ が偶数か奇数かは決定可能なので、$J(x)\iff(x\text{ が偶数}\land\lfloor x/2\rfloor\in K)\lor(x\text{ が奇数}\land\lfloor x/2\rfloor\notin K)$ は、$\Delta^0_2$ の関係を prop-ah-closure の 3 で組み合わせた形なので $\Delta^0_2$ である。$x\mapsto2x$ は $K$ から $J$ への、$x\mapsto2x+1$ は $\mathbb N\setminus K$ から $J$ への多対一還元である。$J$ が $\Pi^0_1$ なら prop-ah-basic の 2 により $K$ も $\Pi^0_1$ になり、$J$ が $\Sigma^0_1$ なら $\mathbb N\setminus K$ も $\Sigma^0_1$ になって、どちらも thm-ah-hierarchy の 1 に反する。

補足

Borel 階層との類似。 算術的階層は、位相空間の開集合から補集合と可算和を交互にとって作る Borel階層の有限段を「計算できる」形に精密にしたものにあたり、自然数から自然数への関数についての量化を許すと射影階層の有効版（解析的階層）になる（Mos09 3E 節、p. 118。そこでは $\Sigma^0_1$ を開集合の有効版として、Borel 階層の定義の可算和・補集合を自然数についての $\exists$・否定に置き換えている）。
算術の体系との関係。 原子論理式から論理結合と有界な量化だけで作った論理式に $\exists$ を 1 つ付けた文は、$\mathfrak N$ で真なら $\mathsf Q$ で証明できる（OLT26 Definition 35.33・Theorem 35.38、pp. 569–571。この記事では証明しない）。このような論理式が定める関係は prop-ah-closure の 1・2 により $\Sigma^0_1$ である。