# Why is Peano arithmetic undecidable?

I read that Presburger arithmetic is decidable while Peano arithmetic is undecidable, and actually Peano arithmaetic extends Presburger arithmetic just with the addition of the multiplication operator. Can someone please give me the 'intutive' idea behind this?

Or probably a formula in Peano arithmetic that cannot be proved. Does it have something to do with the self reference paradox in Goedel's Incompleteness Theorem?

Regards

-
It has everything to do with the self-reference aspect of Godel's First Incompleteness Thm., which is effectively a rigorous form of the Liar's Paradox. It requires multiplication because to obtain the self-reference Godel develops an effective numbering of formulas (and proofs) that uses prime factorization. So if we have only addition, the proof will not go through (because you don't have prime factors to talk about). –  hardmath Jan 7 '11 at 15:50
@hardmath: so there is no bijection between numbers and formulas which can be expressed only with addition? –  Xodarap Jan 7 '11 at 16:03
I edited the tags since the question isn't about algebraic number theory. –  Apostolos Jan 7 '11 at 18:36
What I'm about to say is very "intuitive" and I honestly don't know if it can be formalized in any sense, but this is something my first logic professor said once: since, in a sense, natural number multiplication is "adding a number to itself finitely many times", multiplication sneaks in a reference to "finite" vs. "infinite". Theories with finite models are decidable, so the infinite "lurks" in undecidability; it is this sudden ability to refer, indirectly, to the infinite that causes problems. Steven Stadnicki's answer seems to me to mesh well with this idea. –  Arturo Magidin Jan 7 '11 at 19:04

Essentially, yes, but I believe the undecidability of Peano arithmetic (henceforth, PA) follows from the way the proof of Gödel's incompleteness theorem goes, rather than being a consequence of the fact that PA is incomplete. The proof (outlined below) starts by showing that PA can talk about computable relations, and goes on to show from this how you can construct an unprovable sentence. However, we can take a different approach to show that PA is undecidable: if PA can talk about computable relations, then you can formulate a sentence in the language of PA that is true if and only if a given algorithm halts / does not halt. (Briefly: An algorithm is the same thing as a computable partial function, and an algorithm halts on some input if and only if the corresponding partial function is defined on that input.) So if an algorithm can decide whether arbitrary sentences in PA are provable or not, we have an algorithm which solves the halting problem... but there are nonesuch. So the key point is that PA is rich enough to talk about computation. An essential ingredient for talking about computation is the ability to encode a pair of numbers as a number and the ability to recover the original pair from the encoding. It's not immediately clear to me that $+$ is insufficient to do this, but it's certainly plausible that you need at least two binary operations.

Here is a sketch of the proof of Gödel's first incompleteness theorem: First let's select a sufficiently powerful theory $T$, e.g. PA, and assume that it is a consistent theory, i.e. does not prove a contradiction.

1. We show that we can encode formulae and proofs in the models of $T$.
2. We show that $T$ is powerful enough to talk about computable relations.
3. We show that there is a computable relation $\mathrm{Prf}(m, n)$ which holds if and only if $m$ encodes a valid proof of the sentence encoded by $n$.
4. The above shows that there is a computable relation $Q(m, n)$ which holds if and only if $n$ encodes a formula $F(-)$ with one free variable and $m$ does not encode a valid proof of $F(n)$.
5. So we can define a formula $P(x)$ by $\forall m. Q(m, x)$. This means $P(x)$ holds if and only if there is no valid proof of $F(x)$, assuming $x$ encodes a formula $F(-)$ with one free variable.
6. But $P(-)$ is a formula with one free variable, and it can be encoded by some number $n$. So is the sentence $P(n)$ provable or not? Suppose it were. Then, that means $P(n)$ is true, so the theory asserts that there is no valid proof of $P(n)$ — a contradiction.
7. So we are forced to conclude that the sentence $P(n)$ is not provable. This is the Gödel sentence which we wished to prove the existence of, so we are done.

Note I haven't said anything about whether $P(n)$ is actually true. It turns out there is some subtlety here. Gödel's completeness theorem tells us that everything that can be proven in a first-order theory is true in every model of that theory and that every sentence which is true in every model of a first-order theory can be proven from the axioms of that theory. With some stronger consistency assumptions, we can also show that $\lnot P(n)$ is also not provable in PA, and this means that there are models of PA where $P(n)$ is true and models where it is false.

The key point is that the phrases "$n$ encodes a formula ..." and "$m$ encodes a valid proof of ..." are strictly outside the theory. The interpretation of a particular number as a formula or proof is defined externally, and we only define it for "standard" numbers. The upshot of this is that in a model $\mathcal{M}$ of PA where $P(n)$ is false, there is some non-standard number $m \in \mathcal{M}$ which $\mathcal{M}$ "believes" is a valid proof of $P(n)$, but because it's non-standard, we cannot translate it into a real proof.

-
It's a good point, that undecidability of a formal first-order theory implies incompleteness but not the converse. –  hardmath Jan 7 '11 at 19:23
It doesn't seem to be enough to have "a sentence in the language of PA that is true if and only if a given algorithm halts" -- we need it to be provable (by PA) iff the given algorithm halts. Luckily the sentence in question happens to have the property that it is provable iff it is true in the standard naturals. –  Henning Makholm Oct 30 '14 at 22:03

While this may not be the intuitive idea you're looking for, I'll note that the same ideas behind Godel's proof that Peano Arithmetic is incomplete (that is, that there are true sentences of PA that can't be proven) can also be applied to show that Presburger Arithmetic is 'hard' in a tangible sense; essentially, one can encode multiplication of small enough numbers (specifically, the predicate '$x\times y = z$' with $x$, $y$ and $z$ 'only' doubly-exponential in the length of the formula) into a formula involving only addition. This means that if sentences in Presburger Arithmetic of length $n$ could be decided without multiplying numbers of size at least (roughly) $2^{2^n}$, then Presburger Arithmetic would suffer from the same Godelian paradox that Peano Arithmetic does and be incomplete. Paul Young wrote up a much better exposition of this for a conference a couple of decades ago than I can possibly give; have a look at http://books.google.com/books?id=2vvg3mRzDtwC&pg=PA503&lpg=PA503 for the details.

-

Peano arithmetic is strong enough to reason about Turing machines. Thus, if Peano arithmetic were decidable, the Halting problem would be decidable. I learned essentially this idea from Scott Aaronson.

-
The question is why you can't, say, reason about Turing machines with Presburger's. –  Mariano Suárez-Alvarez Jan 7 '11 at 20:31
Well, if Presburger arithmetic can't reason about multiplication, it certainly can't reason about arbitrary Turing machines... –  Qiaochu Yuan Jan 7 '11 at 20:43
Qiaochu, your answer could be taken as suggesting that this argument might be due to Aaronson, but of course it was known long ago by the early model theorists, such as Tarski and Robinson. –  JDH Jan 8 '11 at 4:12

@hardmath: "It's a good point, that undecidability of a formal first-order theory implies incompleteness but not the converse" - that is simply not true. The theorem (that is actually an easy consequence of Post's theorem) we have here is:

For any FO-theory T, if T is recursively axiomatizable and complete, then it is decidable.

This does not mean that an undecidable theory is necessarily incomplete - it can be complete, but lack recursive axiomatization. That is e.g. the case of ${Th(N, +, \times, 0, 1)}$. Moreover, there are theories which are both recursive and decidable, but incomplete, e.g. $T=\{0=0\}$.

-
Do you claim that $\{0=0\}$ is decidable in the sense that we can decide the logical validity of arbitrary wffs over the language $\{{+},{\times},0,1\}$? That's not what I've learned. On the other hand, $\{x+y=0, x\times y=0, x=0\lor x=1\}$ would be an example of a theory over this language that is recursive, decidable and incomplete. –  Henning Makholm Oct 30 '14 at 21:59