Are Gödel's incompleteness theorems really about primitive recursive functions?

Question

Any formulation of Gödel's incompleteness theorems seems to involve arithmetic. Why is arithmetic so fundamental? After thinking about the issue a little bit, I came to the conclusion that the theorems are about more general objects called primitive recursion functions: it just so happens that the arithmetical operations are the most familiar (even to a first-grader) examples of these objects. In other words, arithmetic is used to state the theorems in a way most people would understand, but really the most technical statement must involve primitive recursive functions. Question: am I right in this conclusion?

Answer 1

1) Gödel's theorems necessarily involve arithmetic, due to the method of the proof. The basic idea is to get a statement to refer to itself, and this is done by having it refer to its Gödel number, an encoding of the statement into a natural number. To refer to the natural number, the system must be about arithmetic.

2) One commonly overlooked detail about Gödel's theorems is that they deal with computable axiom systems: ones where a computer could decide whether or not a given statement is an axiom of the system. This computability means decidability by a recursive function. Primitive recursive is not required, just recursive. To quote Wolfram MathWorld which quotes Gödel 1931, " "To every $\omega$-consistent recursive class $\kappa$ of formulas, there correspond recursive class-signs $r$ such that neither ($v$ Gen $r$) nor Neg($v$ Gen $r$) belongs to Flg($\kappa$), where $v$ is the free variable of $r$".

Therefore I conclude that your conclusion is close to being right but is still not quite right.

Answer 2

If you are looking specifically at the word "arithmetic", it may help know that, although "arithmetic" in general mathematics today refers to the four basic operations, the meaning of "arithmetic" in formal logic settings is the theory of the natural numbers. There is first-order arithmetic (e.g. Peano arithmetic), second-order arithmetic, Presberger arithmetic, etc.

Similarly, "analysis" in logical settings refers to the theory of the real numbers, which is not the way that term is used in general mathematical settings.

So primitive recursive functions are not something separate from "arithmetic", in modern logic. In fact there is an entire theory called "primitive recursive arithmetic" that focuses on them. Primitive recursive functions can also be developed in stronger theories such as Peano arithmetic.