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

Question

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?

Answer 1

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.

Answer 2

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.