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(x₁ … x_n) there corresponds an n-place relation-string r (with the free variables^[38]38: The variables u₁ … u_n 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. u₁, u₂, … u_n) such that for every n‑tuple of numbers (x₁ … x_n) the following hold:

 

R(x₁ … x_n) ⇒ Bew{Sb[r  ^{u₁ … u_n} ⁄ _{Z(x1) … Z(xn)} ]} (3)

     ¬R(x₁ … x_n) ⇒ Bew{Neg Sb[r  ^{u₁ … u_n} ⁄ _{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]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. We prove the proposition for all relations R(x₁ … x_n) of the form: x₁ = Φ(x₂ … x_n)^[40]40: From this it follows immediately that this is valid for every recursive relation, since any such relation is equivalent to 0 = Φ(x₁ … x_n), where Φ is recursive. (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 Φ₁ … Φ_k by the operations of substitution or recursive definition. Since, by the inductive assumption, everything is already proved for Φ₁ … Φ_k, there exist corresponding relation-strings r₁ … r_k such that (3) and (4) hold. The processes of definition whereby Φ is derived from Φ₁ … Φ_k (substitution and recursive definition) can all be formally mapped to the system P. If this is done, we obtain from r₁ … r_k a new relation-string r,^[41]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. 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]42: Where the interpretation of the content of r expresses the existence of that corresponding relation. will be called recursive.

 

---

 

[38]The variables u₁ … u_n 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 = Φ(x₁ … x_n), 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.