万能述語
一般的には、「$ k変数$ \Sigma_n述語を枚挙する述語」というように言うらしい
①$ \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版mrsekut.icon 任意の$ \Sigma_n述語$ A(\vec{x})を、$ E^{\Sigma_n}_k(p,\vec{x})で表せる