The following proposition is an exact expression of a fact that can be roughly formulated in this manner: every recursive relation is definable in the system P (interpreted according to its content), regardless of what interpretation is given to the formulas of P:
Proposition V: To every recursive relation R(x1 … xn) there corresponds an n-place relation-string r (with the free variables[38] u1, u2, … un) such that for every n‑tuple of numbers (x1 … xn) the following hold:
R(x1 … xn) ⇒ Bew{Sb[r u1 … un ⁄ Z(x1) … Z(xn) ]} (3)
¬R(x1 … xn) ⇒ Bew{Neg Sb[r u1 … un ⁄ Z(x1) … Z(xn) ]} (4)
We are content here with indicating the proof of this proposition in outline, since it offers no difficulties in principle and is somewhat involved.[39] We prove the proposition for all relations R(x1 … xn) of the form: x1 = Φ(x2 … xn)[40] (where Φ is a recursive function) and apply mathematical induction on the degree of Φ. For functions of the first degree (i.e: constants and the function x + 1) the proposition is trivial. Let Φ then be of degree m. It derives from functions of lower degree Φ1 … Φk by the operations of substitution or recursive definition. Since, by the inductive assumption, everything is already proved for Φ1 … Φk, there exist corresponding relation-strings r1 … rk such that (3) and (4) hold. The processes of definition whereby Φ is derived from Φ1 … Φk (substitution and recursive definition) can all be formally mapped to the system P. If this is done, we obtain from r1 … rk a new relation-string r,[41] for which we can readily prove the validity of (3) and (4) by use of the inductive assumption. A relation-string r, assigned in this fashion to a recursive relation,[42] will be called recursive.
[38]The variables u1 … un could be arbitrarily assigned. There is always, e.g. an r with the free variables 17, 19, 23 … etc., for which (3) and (4) hold.
[39]Proposition V naturally is based on the fact that for any recursive relation R, it is decidable, for every n-tuple of numbers, from the axioms of the system P, whether the relation R holds or not.
[40]From this it follows immediately that this is valid for every recursive relation, since any such relation is equivalent to 0 = Φ(x1 … xn), where Φ is recursive.
[41]In the precise development of this proof, r is of course defined, not indirectly by an interpretation of its content, but by its purely formal structure.
[42]Where the interpretation of the content of r expresses the existence of that corresponding relation.