Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 4J / d / Solution

Assume a complete list $f$ were primitive recursive. Closure under diagonal composition and successor makesprimitive recursive. Completeness gives a row $n$ with $f(n,k)=d(k)$ for every $k$, but at $k=n$ this says $f(n,n)=f(n,n)+1$. This is the diagonal argument.