Addition (Primitive Recursion)

Definition

Addition ( Primitive Recursion)

Addition , with , is primitive-recursive. Recursing over the first argument gives

The base returns ; each step increases the previous result by one. Thus

Here, is the successor function, denotes a projection function, and is the primitive recursion operator.

Construction

The base function returns the unchanged second argument. The step function receives the previous index , previous result , and parameter :

Thus each step adds one to the previous result. Starting at , exactly steps give .

Example

Adding to

The second argument stays fixed while the first argument counts the successor steps: