Μ再帰関数
(6) μ作用素: 関数 f ( y , x 1 , ... , x k ) {\displaystyle f(y,x_{1},\ldots ,x_{k})} をとり、 x 1 , ... , x k {\displaystyle x_{1},\ldots ,x_{k}} を引数とする関数 μ y f ( y , x 1 , ... , x k ) {\displaystyle \mu yf(y,x_{1},\ldots ,x_{k})} を返す操作である。関数 f {\displaystyle f} は自然数 { 0 , 1 , . . . n } {\displaystyle \{0,1,...n\}} から自然数 { 0 , 1 , . . . n } {\displaystyle \{0,1,...n\}} への数論的関数か、または値域 { 0 , 1 } {\displaystyle \{0,1\}} で真偽を示す述語としての指示関数である。
どちらの場合でも、関数 μ y f {\displaystyle \mu yf} は、 f ( 0 , x 1 , ... , x k ) , f ( 1 , x 1 , ... , x k ) , . . . , f ( y , x 1 , ...
以下の定義は Kleene (1952) p. 219 に基づいている。最初の3つの関数(1)-(3)を「初期関数(initial functions)」または「基本関数(basic functions)」と呼ぶ。その他の記号体系については「記号体系」の節を参照されたい。
(1) 定数関数(Constant function): 任意の自然数 n {\displaystyle n} と k {\displaystyle k} について:
f ( x 1 , ... , x k ) = n {\displaystyle f(x_{1},\ldots ,x_{k})=n} . 定数 n {\displaystyle n} は、「初期オブジェクト・ゼロ(initial object 0)」と呼ばれるオブジェクトに後者関数を繰り返し適用することで生成されることがある。
(2) 後者関数(Successor function)S: 既に生成されたオブジェクトから別のオブジェクト n + 1 {\displaystyle n+1} または n ′ {\displaystyle n'} ( n {\displaystyle n} の後者)への逐次的経路
S ( x ) = d e f f ( x ) = x ′ = x + 1 {\displaystyle S(x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,}