What does Gödel mean by "constant" relating godel definition of recursion to the modern def.

Question

In "On formally undecidable propositions..." he writes a function is recursive if "... it is a constant or the successor function" is he referring to the constant function c(x)=k, and if so, is this somehow equivalent to the usual formulation of primitive recursive functions in terms of the projection and zero functions? I'm having trouble relating his formulation to the modern one in Elliot Mendelson's Introduction to Mathematical Logic.

Answer 1

Yes, this is equivalent to the usual formulation. Any constant function can be created by composing the zero function with the successor function an appropriate number of times.

On the other hand, the successor function must be included as a base case for primitive recursive functions -- otherwise it would be impossible to build any nonzero function.

In the fourth edition of Meldelson's book (which is the one I have available to consult), the successor function is explicitly listed as one of the initial functions on the definition at the beginning of section 3.3.

---

Edit: I now understand you're wondering how Gödel could apparently do without projection functions. The answer seems to be that he actually couldn't, but viewed substitution as trivial enough not to be explicitly mentioned. His definition of "recursive" functions allows a function to be defined from prior functions either by the recursion scheme or by substitution ("Einsetzung").

Footnote 27 in the 1931 paper gives a not-quite-formal description of what he means by Einsetzung, mainly in the form of an example. One interpretation of the example would be (in modern language) you can define a function by setting $f(x_1,\ldots,x_k)$ equal to any expression build from the variables and previously defined functions -- in particular it is at least arguable that defining the function as simply one of the variables is allowed, producing a projection function.

The footnote then explicitly warns: "Not all of the variables from the left-hand side need to appear on the right (and similarly for the recursion scheme (2))."

So for Gödel, projection was implicitly allowed everywhere and didn't need to count as a separate step in the construction. Later authors have then identified this as a point where the rigor of the development could be improved upon.