I am trying to understand Gödel's first incompleteness theorem from his original 1931 paper.
Here is the translations i am using for my studies :
http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf and
http://mrob.com/pub/math/goedel.html (which seems to be an online version of a 1962 translation)
I am trying to make sense of Gödel's paper so i could explain establish the result from scrath and make it understandable to basically anyone.
I am working on the definition of primitive recursive functions. I am trying to make the precise link between what is described by gödel as "substitution" and what seems to be usually defined as "Composition".
"Substitution" (in Gödel's paper translation) : " A number-theoretic function φ is called recursive, if there exists a finite series of number-theoretic functions $\ φ_1, φ_2, ... φ_n$ which ends in φ and has the property that every function $\ φ_k$ of the series is either recursively defined [180]by two of the earlier ones, or is derived from any of the earlier ones by substitution,$\ ^{27}$ or, finally, is a constant or the successor function x+1. [...] $\ ^{27} $More precisely, by substitution of certain of the foregoing functions in the empty places of the preceding, e.g. $\ φ_k(x_1,x_2) = φ_p[φ_q(x_1,x_2),φ_r(x_2)] (p, q, r < k). $ Not all the variables on the left-hand side must also occur on the right
And "Composition", as it seems to be usually defined : "If f is p.r and has arity m and each $\ g_i$ is p.r and has arity k ≥ 0 then $\ C(f, g_1 , . . . , g_m )$ denotes the unique k-ary function h such that for each k-ary x: $\\ h(x) = f (g_1(x), ..., g_m(x)). " $
My question is then : I guess "substitution" and composition are the same, but why in gödel's paper is "substitution" defined as : $\ φ_k(x_1,x_2) = φ_p[φ_q(x_1,x_2),φ_r(x_2)]$ and not $\ φ_k(x_1,x_2) = φ_p[φ_q(x_1,x_2),φ_r(x_1, x_2)]$ . Is there a reason for that ? Is it to make sure the function terminates (like $\ x_1 $ in his definition of primitive recursion) ? Or is it just to illustrate that not all variables on the left hand side have to be on the right hand side ? Or is there another reason ?
Thank you in advance
My guess is that it is just to illustrate that not all variables need to be used ... Which of course is true for composition as well. So, I would say the two really are the same. The 'termination' is when you hit a basic function like the zero or successor function ... 'Throwing out' variables is not like that.