Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 2 / 2 / i / Solution

The primitive recursive functions are the smallest collection containing zero functions, successor $S(n)=n+1$, and coordinate projections, and closed under composition and primitive recursion. The recursion scheme forms $F$ from already constructed functions $G,H$ byConstants follow by composing successor with zero. Define addition, multiplication and exponentiation successively byAt each stage the initial and step functions are compositions of primitive recursive functions already available. Induction on $n$ gives $A(m,n)=m+n$, $M(m,n)=mn$, and $E(m,n)=m^n$, with the recursive convention $0^0=1$. Composition with the second projection now gives