# Is this incompleteness result easier to get than incompleteness of PA?

Gödel's theorem for Peano Arithmetic shows that (under consistency hypothesis on PA) there is a statement which cannot be proved or disproved within PA that is true under the standard model (naturals). An immediate consequence of Gödel's theorem is that there must be some different (nonstandard) model(s) of PA. Gödel's method to accomplish incompleteness of PA involves a noticeable amount of machinery.

I know that there is surely a statement in FO group theory (the statement that in a rough interpretation would intuitively say that the group is abelian) which is easy to see that is not provable nor disprovable because it is true in some models and false in other models. Am I missing something, or this second approach is more natural and effortless than the whole Gödel's construction with respect to PA?

-
How would the incompleteness of FO group theory imply the incompleteness of PA? – azarel Apr 17 '12 at 20:21
Never said that. – Oo3 Apr 17 '12 at 23:09
The existence of nonstandard models is a consequence of compactness, and has nothing to do with incompleteness. Perhaps you mean that the models are not elementarily equivalent to the standard model. – Andrés E. Caicedo Jul 28 '13 at 6:40
@لويسالعرب: A theory $T$ is defined to be decidable if the set $\{\phi : T \vdash \phi\}$ is a computable set. The definition you gave for "decidable" is actually the definition for "complete". – Carl Mummert Jul 28 '13 at 11:37

Proving that a particular theory is undecidable is more difficult than proving that there exists some theory that is undecidable, which is more difficult than proving that there exists an incomplete theory. The easy example about commutativity accomplishes only the last task.

Undecidability implies incompleteness (searching for a proof or disproof is a decision procedure if theory is complete), but not the reverse. Undecidability of first-order group theory is a difficult theorem that was not proved for several decades after Goedel's theorem, while incompleteness was known from the moment that an axiom system for group theory was written down.

Another indication of the difference is that Goedel showed essential undecidability, every consistent extension of first-order arithmetic is undecidable. For first-order theories of a class of structures such as groups, rings, graphs, or ordered sets, this is not true because one can consistently add axioms like "there is no set of 3 distinct elements". For arithmetic there are no such simplifications.

-
+1 Interesting answer. – Oo3 Apr 17 '12 at 23:09

That would indeed be simpler -- from at least some points of view -- if only we could find an explicit model of PA that disagreed in some obvious way with the standard model.

Unfortunately, it's not very easy to construct nonstandard models of PA. Making sure that all of the infinitely many instances of the induction axiom scheme are true in the model really constrains the result. The most common ways to produce one are:

1. Prove Gödel's incompleteness theorem! Then appeal to the completeness theorem to get a model for $PA+\neg G$, where $G$ is a Gödel sentence of $PA$. That's of course a useless strategy for your program.

2. Use Robinson's ultrapower construction on $\mathbb N$ to create a nonstandard model. This doesn't help us here either, because the resulting model is elementarily equivalent to the original model even though it is not isomorphic.

3. Add a constant symbol $c$ and an infinity of new axioms that say that $c$ is greater than every numeral. The resulting theory is consistent by compactness (assuming that PA is consistent). Appeal, again, to the completeness theorem to get a model of PA where $c$ is an "infinite" element. Then all you have to do is find a concrete sentence that is true in the new model but false in the standard model. Good luck with that.

A more principled argument against your plan is that any argument that uses model theory requires that we believe in set theory, whereas Gödel's construction can be formalized in PA itself (which is weaker than set theory). So if one is concerned with finding a minimal "leap of faith" required for mathematics to work, one will generally prefer methods that can be carried out in the weaker theory.

-
How is this related to en.wikipedia.org/wiki/Robinson_arithmetic ? It's possible to prove Gödel's incompleteness theorem(s) for Robinson arithmetic (or Q), but contrary to PA it's easy to find explicit computable non-standard models of Q. I think the incompleteness theorem(s) for PA follow from those for Q. However, I have no idea of whether the incompleteness proofs can by simplified by making use of these facts. – Thomas Klimpel Apr 17 '12 at 21:16
@ThomasKlimpel: Since Q is strictly weaker than PA, I don't see any direct way to reason from incompleteness of Q to incompleteness of PA. [Analogously, one can easily prove that the first-order theory of fields is incomplete, but we cannot deduce from that that the strictly stronger theory of real closed fields is incomplete (because it isn't)]. – Henning Makholm Apr 18 '12 at 10:50
I think I understand now. The point is that Q (like PA) is not just incomplete, but recursively incompletable (and essentially undecidable). So a statement in Q which is true in some models and false in other models only proves incompleteness of Q, but not that Q is recursively incompletable. – Thomas Klimpel Apr 18 '12 at 23:00
Wouldn't 'there exists an element $x$ such that $x\neq 0$ and there is no $y$ with $Sy=x$' be a valid sentence for approach 3? Of course, proving (rather than intuiting) that this is false in the 'standard' PA model is pretty tricky... – Steven Stadnicki Jul 28 '13 at 23:13
@Steven: No -- PA proves that sentence wrong by induction on $x$. – Henning Makholm Jul 29 '13 at 13:11