一般的には、「k変数\Sigma_n述語を枚挙する述語」というように言うらしい

算術的階層の全ての領域(図中の①②③..)にその領域用の万能関数が存在する

①用の万能述語と言えば、万能関数 comp のこと

①\cup②用には、\Sigma_1万能述語がある

というのが繰り返し存在する

\Sigma_n述語全体には、\Sigma_n万能関数が存在する

これをE(p,\vec{x})とすると

E自身は\Sigma_n述語

適切なpを代入するとどんな\Sigma_n述語の役割も果たす

定理

nを1以上の任意の自然数、kを任意の自然数としたとき以下の2つが成り立つ

(k+1)変数の\Sigma_n述語E^{\Sigma_n}_{k}が存在して以下が成り立つ

k変数の任意の\Sigma_n述語Aに対して

自然数pが存在し、

Aは、A(\vec{x})\iff E^{\Sigma_n}_{k}(p,\vec{x})と表せる

このE^{\Sigma_n}_{k}のことを「k変数用の\Sigma_n万能述語」と言う

(k+1)変数の\Pi_n述語E^{\Pi_n}_{k}が存在して、以下が成り立つ

k変数の任意の\Pi_n述語Aに対して

自然数pが存在し、

Aは、A(\vec{x})\iff E^{\Pi_n}_{k}(p,\vec{x})と表せる

このE^{\Pi_n}_{k}のことを「k変数用の\Pi_n万能述語」と言う

要は万能関数 comp の\Sigma_n版と\Pi_n版

任意の\Sigma_n述語A(\vec{x})を、E^{\Sigma_n}_k(p,\vec{x})で表せる