Negative Numbers and Gödel’s Incompleteness Theorem

Question

I was examining Q (Robinson Arithmetic) when it occurred to me that Q contains no statements about the negative numbers or subtraction. No resource that I’ve been able to find has discussed Gödel’s Incompleteness Theorems for theories of arithmetic for $\mathbb Z$.

My question is: Is there a reason for this widespread omission?

There seems to be an obvious way to extend axiomatic sets like Q and PA to deal with negative numbers. There also seems like there is an easy way to extend Gödel’s Second Incompleteness Theorem to arithmetic in $\mathbb Z$. Is there a reason why this doesn’t seem to be done, or even noted, in most sources?

Answer 1

I suspect that the main reason is that the extension from $\mathbb{N}$ to $\mathbb{Z}$ is pretty trivial, and $\mathbb{N}$ is a more "limited" system, so there is a perceived elegance in proving the theorem in the most limited context, so that it has the broadest applicability.

One extension from $\mathbb{N}$ to $\mathbb{Z}$ goes through Lagrange's four square lemma: every natural number is the sum of four squares of integers. So, if we can only quantify over $\mathbb{Z}$, we can fake quantifying over $\mathbb{N}$: $$ (\exists n)[(\exists a,b,c,d)[a^2+b^2+c^2+d^2 = n] \land \ldots ] $$ Hence the theory of $(\mathbb{Z},+,\times)$ interprets the theory of $(\mathbb{N},+,\times)$. Similarly, axiomatic theories of $\mathbb{Z}$ will interpret axiomatic theories of $\mathbb{N}$, allowing the incompleteness theorem to transfer.

Answer 2

Godel's theorems do indeed still hold for $\mathbb{Z}$. The easiest one to port over is the "strong first theorem," that no recursively axiomatizable extension of $B$ is complete for some appropriate theory $B$ which is true of $(\mathbb{Z};+,\times, S)$. This (once an appropriate $B$ has been defined) is just a corollary of the usual Godel's theorem since the natural numbers are definable in $\mathbb{Z}$. This means that given any set of sentences $T$ about $\mathbb{Z}$ we get a corresponding set $T_\mathbb{N}$ of "sentences about $\mathbb{N}$ which $T$ proves" - namely, fixing a formula $\varphi$ defining $\mathbb{N}$, $T_\mathbb{N}$ is the set of sentences $\psi$ such that $T\vdash \psi^\varphi$ (where "$\psi^\varphi$" is the relativization of $\psi$ to the set defined by $\varphi$; just change "$\exists x(...)$" to "$\exists x(\varphi(x)\wedge...)$" and change "$\forall x(...)$" to "$\forall x(\varphi(x)\implies ...)$"). The key point is that $T_\mathbb{N}$ is recursively axiomatizable since $T$ is, and will be sufficiently strong as long as $B$ is.

OK, what should our $B$ be? Well, we can just take $B=Q^\varphi$, the set of relativizations-to-$\varphi$ of axioms in Robinson arithmetic; then for any $T\supseteq B$ we'll have $T_\mathbb{N}\supseteq Q$. Note that at no point do we have to "redo" the usual proof of Godel's theorem.

As to why everything is presented over $\mathbb{N}$ rather than $\mathbb{Z}$, I don't know any good reason for that; I think it's probably just convention. (Although maybe Diophantine equations are nicer than integral equations, sometimes?)