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.

  • $\begingroup$ Yeah that makes sense $\endgroup$ – joseph M'Bimbi-Bene Oct 27 '16 at 12:14
  • 1
    $\begingroup$ Ok, and good luck with getting your head around godel's incompleteness theorems. I learned them through self study as well, and found 'Computability and Logic' by Boolos and Jeffrey to be very helpful. $\endgroup$ – Bram28 Oct 27 '16 at 12:30
  • 1
    $\begingroup$ (unadvertedly deleted comment) Thanks ! I will look for that book too. Yeah it's so fascinating and rewarding, while being so frustrating at time. It's too bad because most people that could be interesting in "the real thing", and not some vulgarizations or simplifications, or "way arounds" are kept away from that wonderful pieces of knowledge due to unnecessary complexifications ... Knowledge should be free, easy, accessible to any and everyone. It should be easy and not take weeks/months. Hopefully i can "democratize" Gödel's incompleteness Theorems. Hopefully you can help me too :) $\endgroup$ – joseph M'Bimbi-Bene Oct 27 '16 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.