Primitive Recursive Function - Examples - Subtraction

Subtraction

Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a limited subtraction function is studied in this context. This limited subtraction function sub(a,b) returns if this is nonnegative and returns 0 otherwise.

The predecessor function acts as the opposite of the successor function and is recursively defined by the rules:

pred(0)=0,

pred(n+1)=n.

These rules can be converted into a more formal definition by primitive recursion:

pred(0)=0,

pred(S(n))=P₁2(n, pred(n)).

The limited subtraction function is definable from the predecessor function in a manner analogous to the way addition is defined from successor:

sub(0,x)=P₁1(x),

sub(S(n),x)=pred(P₂3(n,sub(n,x),x)).

Here sub(a,b) corresponds to b-a; for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion. This could easily be rectified using composition with suitable projections.

Other primitive recursive functions include exponentiation and primality testing. Given primitive recursive functions e, f, g, and h, a function that returns the value of g when e≤f and the value of h otherwise is primitive recursive.