2
$\begingroup$

This might be an easy question, but I still struggle to comprehend non-standard models for Peano axioms. I understand that Godel Theorem tells us that the theory defined by Peano axioms is not complete and therefore there exist propositions which are not provable with Peano axioms.

So my question is how do we construct or what is a model which is not isomorphic to Natural numbers but satisfies all the Peano axioms?

$\endgroup$
  • $\begingroup$ It is important that we are using a first-order version of Peano's axioms. (Peano himself phrased induction as a second-order property, and Goedel need not apply in that case.) $\endgroup$ – GEdgar Dec 18 '14 at 14:50
  • $\begingroup$ There is a discussion of this in The Incompleteness Phenomenon by Goldstern and Judah along with a sketch of what the model looks like if it is countable. It has a countable infinity of copies of $\Bbb Z$ of nonstandard numbers. The copies are ordered like $\Bbb Q$ $\endgroup$ – Ross Millikan Dec 18 '14 at 14:58
4
$\begingroup$

A simple method for constructing a nonstandard model of arithmetic is to use compactness as follows. Let $c$ be a new constant symbol not occurring in the language of arithmetic and add to PA the infinitely many new axioms $0<c$, $S0<c$, $SS0<c$, etc. This new theory is consistent, since any finite subset $F$ of it contains only finitely many of the new axioms and has a model consisting of the standard model with the new constant $c$ interpreted as a sufficiently large integer to cover the finitely many new axioms occurring in $F$.

Now take a model of the (whole) new theory -- it is a model of PA and contains an element (the interpretation of $c$ ) which is bigger than all the standard natural numbers $0, S0, SS0$, etc. To be precise, the reduct of this model to the language of PA is the model you want.

Finally, this construction has nothing to do with incompleteness. You could start with complete arithmetic (i.e. all first order sentences true in the standard model) instead of PA and then we'd have proved the existence of non-standard models which satisfy exactly the same sentences of arithmetic as does the standard model.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. What is F? $\endgroup$ – Огњен Шобајић Dec 19 '14 at 2:31
  • $\begingroup$ F is an arbitrary finite subset (i.e. sub-theory) of the theory T consisting of the axioms of PA together with the list of new axioms. If all such finite subsets F of T are consistent, then T is consistent, and then T must have a model. $\endgroup$ – Ned Dec 19 '14 at 15:53
  • 1
    $\begingroup$ Is there an intuitive way to see that the induction axiom holds for the model constructed here? Since our element c is somehow "disconnected" from the initial segment N, it's not obvious that a formula holding for 0 and for the successor of any other number it holds for should also hold for c. I suppose the compactness theorem guarantees it, but it's hard to get an intuition from. $\endgroup$ – ziggurism Apr 5 '16 at 21:49
  • $\begingroup$ The induction formulas that hold are first-order, that is to say, induction on properties that are definable by first-order formulas. That's much weaker than full (2nd order) induction. For example, the set of standard numbers {0,1,2,... } is not definable in one these models, since by induction, any definable set which contains 0 and is closed under successor must include the entire domain of the structure. $\endgroup$ – Ned Apr 6 '16 at 2:14
  • $\begingroup$ @Ned: yeah that's what we've been told. First-order formulas can't distinguish between the initial segment $\mathbb{N}$ and the chain $... < c-1 < c < c+1 < ...$. But it's hard to reconcile that with my elementary understanding of how mathematical induction works. How does one prove, assuming ZFC, that the model described here satisfies the induction axiom for first-order formulas? Must it go through the compactness theorem? Does it require some form of the axiom of choice in an essential way, or can it be checked explicitly? $\endgroup$ – ziggurism Apr 6 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.