0
$\begingroup$

Although the usual natural numbers satisfy the axioms of PA, there are other models as well (called "non-standard models"); the compactness theorem implies that the existence of nonstandard elements cannot be excluded in first-order logic. [...] The original (second-order) Peano axioms... have ONLY ONE MODEL, up to isomorphism." (my emphasis)

Wikipedia, Peano Axioms, Non-standard Models

Would this be an example of the incompleteness of the first-order Peano Axioms?


Update 5 months later

Though I don't fully understand Noah's thoughtful answer and am at a loss to formulate any more follow-up question(s), as helpfully suggested, I did find his comment that Gödel's Incompleteness Theorem has "nothing whatsoever" to do with 2nd order Peano arithmetic to be very interesting. On this basis, I have accepted his answer.

$\endgroup$
1
  • $\begingroup$ In the interest of moving this off the unanswered queue, do you have any further questions about my answer? $\endgroup$ Feb 22, 2022 at 4:01

1 Answer 1

5
$\begingroup$

No. Compactness merely guarantees that $\mathsf{PA}$ (as is now standard I'll write simply "$\mathsf{PA}$" for first-order Peano arithmetic) has multiple models up to isomorphism. It does not prevent such models from all looking the same from the perspective of their internal first-order theories - that is, from being elementarily equivalent. Indeed, compactness applies to all first-order theories, including the complete ones. True arithmetic $\mathsf{TA}$ for example has $2^{\aleph_0}$-many non-isomorphic countable models, but is by definition complete.

The incompleteness of $\mathsf{PA}$ is a much stronger result, and does not follow from coarse considerations alone. Compactness shows that $\mathsf{PA}$ is not categorical (and indeed no first-order theory with infinite models is categorical). But even that is limited: it takes more than mere compactness to even show that $\mathsf{PA}$ isn't $\aleph_0$-categorical (we have to bring in Lowenheim-Skolem, or use Godel).

$\endgroup$
7
  • $\begingroup$ Thanks for your authoritative answer, but from Wikipedia's, Gödel's Incompleteness theorem: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers." en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems Isn't having only one model up to an isomorphism not considered to be one of those "truths about the natural numbers?" $\endgroup$ Aug 30, 2021 at 16:53
  • 1
    $\begingroup$ @DanChristensen No. "Truths about the arithmetic of natural numbers" means "all first-order sentences true in $(\mathbb{N};+,\times)$" (or something morally equivalent to that). Don't take wiki's quick informal gloss too seriously. $\endgroup$ Aug 30, 2021 at 16:54
  • $\begingroup$ Does GIT have nothing to say about second-order PA? $\endgroup$ Aug 30, 2021 at 17:02
  • 3
    $\begingroup$ @DanChristensen Nothing whatsoever. $\endgroup$ Aug 30, 2021 at 17:05
  • 1
    $\begingroup$ @DanChristensen There's a fair bit to unpack there, but the short version is that second-order theories of any type are terrible to work with and it's much better to use a first-order theory treating a richer class of objects (like $\mathsf{ZFC}$) than a second-order theory treating a narrow class of objects (like second-order $\mathsf{PA}$). Arguments which are naively formulated in second-order PA typically reformulate effortlessly in (first-order) $\mathsf{ZFC}$ ... to which Godel of course applies. But this is all getting a bit far from the topic of the OP, and long for a comment thread. $\endgroup$ Aug 30, 2021 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .