Multiplication (Primitive Recursion)

Definition

Multiplication ( Primitive Recursion)

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

The base returns ; each step adds to the previous result. Thus

Here, is the unary zero function, is addition, and denotes a projection function.

Construction

The base function starts with an empty sum. It is unary because is the one parameter remaining after fixing the recursion argument .

The step function receives the previous index , previous result , and unchanged parameter . The projections select and :

Starting at , each step adds . If the previous result is , the next result is . Thus steps compute .

Example

Repeatedly adding

The second argument stays fixed while the first argument counts the additions: