1
$\begingroup$

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?

  • 2
    How would the incompleteness of FO group theory imply the incompleteness of PA?2012-04-17
  • 0
    Never said that.2012-04-17
  • 0
    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.2013-07-28
  • 0
    @لويسالعرب: 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".2013-07-28

2 Answers 2

5

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.

2

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.

  • 1
    How is this related to http://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.2012-04-17
  • 0
    @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)].2012-04-18
  • 1
    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.2012-04-18
  • 0
    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...2013-07-28
  • 0
    @Steven: No -- PA proves that sentence wrong by induction on $x$.2013-07-29
  • 0
    @HenningMakholm Ahhh, okay. And that doesn't disrupt consistency, but I presume that that means that the theory in example 3 is $\omega$-inconsistent since we have $\exists y: Sy=c$ but cannot exhibit such a $y$?2013-07-29
  • 0
    @HenningMakholm Actually, I take that back - the theory must be much more complicated than the obvious stacked copies of $\mathbb{N}$. I thought I had a somewhat straightforward model, but it doesn't work - I'll have to chew on that a bit more, and may ask it as a question here.2013-07-29
  • 0
    @Steven: Note that the $\omega$-insconsistency of the theory of example 3 is witnessed already by the property $P(x)\equiv x\ne c$, which is true for every _numeral_ yet provably false for _something_ (namely $c$). No need to involve the successor function.2013-07-30