16 - Representability of Recursive Functions

Summary

In the preceding chapter we connected our work on recursion with our work on formulas and proofs in one way, by showing that various functions associated with formulas and proofs are recursive. In this chapter we connect the two topics in the opposite way, by showing how we can ‘talk about’ recursive functions using formulas, and prove things about them in theories formulated in the language of arithmetic. In section 16.1 we show that for any recursive function f, we can find a formula φ_f such that for any natural numbers a and b, if f(a) = b then ∀y(φ_f (a, y) ↔ y = b) will be true in the standard interpretation of the language of arithmetic. In section 16.2 we strengthen this result, by introducing a theory Q of minimal arithmetic, and showing that for any recursive function f, we can find a formula ψ_f such that for any natural numbers a and b, if f(a) = b then ∀_y(ψ_f (a, y) ↔ y =b) will be not merely true, but provable in Q. In section 16.3 we briefly introduce a stronger theory P of Peano arithmetic, which includes axioms of mathematical induction, and explain how these axioms enable us to prove results not obtainable in Q. The brief, optional section 16.4 is an appendix for readers interested in comparing our treatment of these matters here with other treatments in the literature.