μ再歸函數
μ-recursive function。歸納的函數 (recursive function)
原始再歸函數 (primitive recursion function) 定數函數 (constant function)$ \N\to\{0\}は原始再歸函數である 後者函數 (successor function)$ S:\N\to\N,n\mapsto n+1は原始再歸函數である 射影函數 (projection function)$ P^n_i:\N^n\to\N,(x_1,\dots,x_i,\dots,x_n)\mapsto x_iは原始再歸函數である 合成 (composition。置換 (substitution))。$ f:\N^m\to\Nと$ g_1,\dots,g_n:\N^n\to\Nが原始再歸函數ならば、$ f(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n)):\N^n\to\Nも原始再歸函數である 原始再歸 (primitive recursion)。$ f:\N^n\to\Nと$ g:\N^{n+2}\to\Nが原始再歸函數ならば、以下の通り再歸的に定義される函數$ h:\N^{n+1}\to\Nも原始再歸函數である $ h(x_1,\dots,x_n,0):=f(x_1,\dots,x_n)
$ h(x_1,\dots,x_n,y+1):=g(x_1,\dots,x_n,y,h(x_1,\dots,x_1,y))
$ f:\N^{n+1}\to\Nが原始再歸函數であり、$ \forall x_1,\dots,x_n\exist y(f(x_1,\dots,x_n,y)=0)であるならば、$ \mu y(f(x_1,\dots,x_n,y)=0):\N^n\to\Nはμ再歸函數である μ作用素
$ \exist y_{\in\N}~\varphi(n)である時に、$ \mu y\varphi(y):=\min\{y|\varphi(y)\}