How simple it can be?

Question

My dream axiom system is only the integers with the usual addition axioms (commutative, associative), and with induction. a) does it have a name, b) can I show define ab, and show ab=ba in this system?, c) is Gödel valid for this system?

Answer 1

The natural context for looking at addition of natural numbers alone is Presburger arithmetic, $Pres$. The language consists only of the binary function symbol "$+$" and constant symbols "$0$" and "$1$" together with the usual logical symbols, including "$=$." The axioms consist of some basic facts about addition, and the induction scheme for all formulas in the language.

(Note that in fact the constant symbols are redundant, since they can be defined using $+$ alone: $0$ is the unique $x$ such that for all $y$, $x+y=y$, and $1$ is the unique $x$ such that for all $y$, either $y=0$ or there is some $z$ such that $x+z=y$.)

The theory $Pres$ is meant to describe the structure $\mathcal{N}_+=(\mathbb{N}; +, 0, 1)$, in the same way that the intended model of PA is $\mathcal{N}=(\mathbb{N}; +,\times, 0, 1)$. There is a fundamental difference, however: it turns out that $Pres$ completely describes $\mathcal{N}_+$, in the sense that every sentence true in $\mathcal{N}_+$ is provable from $Pres$. Note that this immediately implies that $Pres$ is a complete theory (since if $\varphi$ is any sentence, either $\varphi$ is true in $\mathcal{N}_+$ or $\neg\varphi$ is true in $\mathcal{N}_+$). In particular, Godel's incompleteness theorem does not apply to it.

Note that by the compactness theorem, $Pres$ does not completely describe $\mathcal{N}_+$ up to isomorphism - there will be models of $Pres$ which aren't isomorphic to $\mathcal{N}_+$, for example any uncountable model of $Pres$.

Now, multiplication can be "recursively defined" using addition in an obvious way (more on this below). However, this does not constitute an actual definition in the sense of first-order logic: to put this precisely, the function $\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}: (x, y)\mapsto x\cdot y$ is not definable in the structure $\mathcal{N}_+$. There is a fundamental difference between the idea of a recursive definition and a first-order definition, and in general they can't be conflated.

As an aside, and very broadly speaking, the key property of a "strong enough" theory of arithmetic as far as Godel is concerned is that it can "first-orderize" a large class of recursive definitions in an appropriate way. This largely comes down to the ability to treat finite sequences appropriately (see e.g. this question): once we have multiplication, we can talk about finite sequences via Godel's $\beta$ function (and it's even easier if we work in a context with exponentiation directly built in) but in Presburger arithmetic we don't even have a pairing function.

---

Now let's say a bit about the "recursive definition" of multiplication in $Pres$. There are a few ways to approach this. In my opinion, the most natural one is the following: we write a sentence $\varphi$ in the expanded language $\{+, 0,1, *\}$ which is intended to say that "$*$" is just multiplication. One obvious candidate formula is the universal closure of the conjunction of the following formulas:

• $x*0=0$,

• $x*y=y*x$,

• $x*(y+1)=(x*y)+x$.

(There are plenty of others.) Let's work with this choice of $\varphi$ for the moment.

Good news: there is exactly one expansion of $\mathcal{N}_+$ to our larger language which satisfies $\varphi$ - namely, we have to interpret $*$ as multiplication. This is an easy induction argument.

Bad news: this really only works with this particular model. In general, if $M\models Pres$, there is no reason to believe that there is exactly one expansion of $M$ to a model of $Pres\cup\{\varphi\}$ - maybe there are several, or none. That is, $Pres$ isn't strong enough to guarantee that "multiplication," defined in the obvious recursive way, is a unique well-defined thing.

---

Now a natural next question is:

Starting with Presburger arithmetic, how much of the basic theory of multiplication can I add before I hit Godelian phenomena?

(Or conversely, starting with PA, how much can I take away and still have a theory to which Godel applies?)

I think a good place to get started, if you're interested, is to read about self-verifying theories; these are theories which can talk about multiplication to a certain extent, but which manage to prove their own consistency by virtue of not quite proving enough basic facts about multiplication for Godel to apply.

Specifically, they don't prove that multiplication is total! So this is really a big gap. To see the importance of totality, note that even the extremely weak theory Robinson arithmetic, $Q$, is susceptible to Godel, and really the only thing $Q$ can do that Willard's theories can't is prove that multiplication is always defined. Note that there isn't an axiom of $Q$ stating this; the totality of multiplication is an immediate consequence of having multiplication be denoted by a function symbol. In Willard's theories, we don't have a function symbol for multiplication but rather a relation symbol for the graph of multiplication.