Primitive recursive functions

The primitive recursive functions form the smallest class of functions that

  1. includes
    • the zero function: \( z(x) = 0 \)
    • the successor function: \( s(x) = x+1 \)
    • the projection functions: \( p_i(x_1,\ldots,x_i,\ldots,x_m) = x_i \)
  2. is closed under
    • composition: \( h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n) ) \)
    • primitive recursion: \( h(x,0)=f(x);\, h(x,y+1)=g(x,y,h(x,y))\)

Examples: