5
$\begingroup$

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to a = b$, unless we agree that $Z=0$, in which case what we have is exactly the standard natural numbers.

Similarly, consider the following structure: $$\Bbb T = \Bbb N \cup \{a, Sa, SSa, SSSa, SSSSa\},$$ where $S(SSSSa) = a $. This fails to satisfy the Peano axioms, but the failure is a little harder to find. The induction schema includes an axiom $$((0\ne SSSSS0)\land(\forall n. n\ne SSSSSn\to Sn\ne SSSSS(Sn))\to \\ \forall n. n\ne SSSSSn. $$

The andecedent is provable, and so the Peano axioms prove $\forall n. n\ne SSSSSn$, which rules out the possibility of $SSSSSa=a$.

Next, consider the structure $$\Bbb U = \Bbb N \cup \{ \overline 0, S\overline{0}, SS\overline{0}, \ldots\}.$$

This is ruled out by an induction axiom for the predicate $n=0\lor \exists m. n=Sm$; the predicate fails to hold for the element $\overline 0$.

Finally, consider $$\Bbb V = \Bbb N \cup \{ \ldots, N_{-2}, N_{-1}, N_0, N_1, \ldots\}$$

with the rule that $S(N_k) = N_{k+1}$. Here I wasn't able to find a theorem of PA that ruled out $\Bbb V$ as a model.

My questions (amended as per comments):

  1. I know at least two arguments that nonstandard models of PA must exist. But how can we be sure that some specific object is one of them, and some other object is not?
  2. Given some structure like $\Bbb U$ or $\Bbb V$ that is not a model of PA, is there a technique for finding a proof that it is not a model? Is there a technique for finding a particular theorem of PA that fails to hold in the non-model?
  3. I suppose this is treated in some elementary model theory textbook. Where can I find it?
$\endgroup$
  • 1
    $\begingroup$ It looks as if you are using second order Peano arithmetic, in which case there are no non-standard models. If you have first order PA in mind, you have not described the non-standard model. $\endgroup$ – André Nicolas Jan 14 '14 at 4:41
  • $\begingroup$ I want to use first-order Peano arithmetic, with an infinite class of axioms of the form $(\Phi(0)\land (\forall n. \Phi(n)\to\Phi(Sn)))\to\forall n. \Phi(n)$ for each first-order predicate $\Phi$. If $\Bbb U$ is not a model of these axioms, which axiom does it violate? $\endgroup$ – MJD Jan 14 '14 at 4:42
  • $\begingroup$ Are you sure $\mathbb{U}$ is a model? If $N_x + N_y = N_z$, then I'm pretty sure we ought to have $N_x + N_{x+y-z-1} = N_{x-1}$, which violates the theorem that $a + b \geq a$. $\endgroup$ – Hurkyl Jan 14 '14 at 4:44
  • 3
    $\begingroup$ A theorem of Tennenbaum says that there are no recursive countable nonstandard models of $\mathsf{PA}$. This implies that whenever you can simply describe a supposed countable nonstandard model of $\mathsf{PA}$, it's not. $\endgroup$ – user642796 Jan 14 '14 at 5:08
  • 3
    $\begingroup$ @MJD: So you are looking at language that has a single unary function symbol $S$, and theory $T$ whose axioms the usual successor axioms plus induction (restricted, of course, to formulas in the language). Then your model is, I am pretty sure, a model of $T$, so you will not find a sentence of the desired kind. But it is far from being a model of first order PA: not only are addition and multiplication not specified, but no addition, multiplication can be specified (constructively or not) that will turn your structure into a model of PA. $\endgroup$ – André Nicolas Jan 14 '14 at 5:23
6
$\begingroup$

nonstandard models of PA must exist. But how can we be sure that some specific object is one of them, and some other object is not?

There are some necessary conditions on the order type but Tenenbaum's theorem (addition and multiplication are non-computable in countable nonstandard models of PA whose elements are identified with $N$) sets a strong limit on how "specific" the object can be. Basically you would have to construct the object as a nonstandard model of PA, not start from a concrete combinatorial structure that plausibly could be a model and show that it is one.

Given some structure like U that is not a model of PA, is there a technique for finding a proof that it is not a model? Is there a technique for finding a particular theorem of PA that fails to hold in the non-model?

It violates some necessary condition (usually order type, e.g., the example in the question with a cycle of length 5). According to the comment from Andres Caicedo, having an infinite ordinal be first-order definable in $U$ would make it not a model.

I suppose this is treated in some elementary model theory textbook.

Kaye's book on models of PA.

$\endgroup$
  • $\begingroup$ Thanks, especially for the reference to Kaye. $\endgroup$ – MJD Jan 14 '14 at 5:18
  • 1
    $\begingroup$ Re $\epsilon_0$: A candidate structure that is not isomorphic to the standard model already has nonstandard numbers, so it cannot define any infinite ordinal; if it does, we already know it is not a model of $\mathsf{PA}$. $\endgroup$ – Andrés E. Caicedo Jan 14 '14 at 8:43
  • $\begingroup$ That certainly simplifies things. Thanks. I wonder though whether there is some sense in which a structure being "too deep" excludes it as a model of PA. For example, in the uncountable models there is a dense linear order's worth of $\mathbb{Z}$'s but that DLO cannot be isomorphic to $\mathbb{R}$. Maybe excess complexity is the wrong idea here, in the sense that a nonstandard model of a bigger theory that interprets PA is a solution to a much stricter problem. Excessive homogeneity, such as automorphism groups (which have to be big) being too continuous, might be more relevant. @AndresCa $\endgroup$ – zyx Jan 14 '14 at 9:48
  • $\begingroup$ (That's another necessary condition on a nonstandard model: $U$ should have a very large automorphism group). $\endgroup$ – zyx Jan 14 '14 at 21:31

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.