Lambda definition of primitive recursion by pair iteration

ID: lambda-definition-of-primitive-recursion-by-pair-iteration

If total functions and are represented by lambda terms , define
and
After iterations the Church pair holds , proved by mathematical induction using the defining recursion equations. Consequently represents the total primitive recursive function . This statement concerns total inputs and total recursion constituents; it is not an unguarded composition theorem for arbitrary partial functions.

New to topics? Read the docs here!