Given operation Primitive recursion, we can do pred(x)=x-1 as

f(0,x) = x
f(i+1,x) = i
pred(x) = f(x,x)

and zero as

g(0,x) = x
g(i+1,x) = pred(g(i,x))
zero(x) = g(x,x)

So why add such an axiom that The 0-ary constant function 0 is primitive recursive.? Does it just enable zero-argument functions?

  • 2
    $\begingroup$ There’s no single standard definition of primitive recursive functions, since we only care about the resulting class of functions, not the minutiae of the definition. In particular, we don’t necessarily care about minimality of axioms. $\endgroup$ – Yuval Filmus Dec 10 '19 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.