5
$\begingroup$

The standard model of Peano's arithmetic, $\mathbb{N}$, has the useful property that the order $\leq$ is a well-order. However, being a well-order cannot be expressed in the language of first-order Peano arithmetic, because it concerns subsets of numbers, or predicates on numbers, and the first-order logic cannot quantify on those.

In a non-standard Peano model, is the order $\leq$ a well-order ? It seems impossible, because if it was a well-order we could take the smallest non-standard number, and then ask about its predecessor.

But if a non-standard model is not well-ordered, how can we interpret Peano's induction axiom scheme ? It would prove formulas by induction, even though there are infinite descending sequences of non-standard numbers, so nowhere to intuitively initialize the induction.

$\endgroup$
8
  • $\begingroup$ You are right, the irder is far from being a well-ordering: Any infinite $n$ is in a copy of $\mathbb Z$, and the copies themselves form a dense order without endpoints. $\endgroup$ Sep 25 '18 at 13:05
  • $\begingroup$ But it just so happens that in all these models induction for first-order formulas (with parameters) holds.; that is part of what it means to be a model of Peano arithmetic. Obviously, true (second-order) induction fails. $\endgroup$ Sep 25 '18 at 13:07
  • $\begingroup$ "Intuitively", if you live in such a model, it just looks like the ordinary standard model to you, and you expect that any number is reachable from 0 by repeatedly adding 1. Of course, checking this does not take place in time, instead a finite sequence is built. The issue is that the notions of "finite" and "sequence" are now non-standard, though of course you cannot detect this "from inside". $\endgroup$ Sep 25 '18 at 13:11
  • $\begingroup$ Non-standard models of PA are not well-ordered: the set of all "non-standard" elements has no least element. However, all models of PA have the property that every definable non-empty subset has a least element. This is equivalent to the ordinary induction scheme for first order formulas, using roughly the same proof that the well ordering of the naturals implies (second-order) induction. $\endgroup$ Sep 25 '18 at 13:25
  • 1
    $\begingroup$ It would not be an element of the model. That is, it is not coded by any element of the model. $\endgroup$ Sep 25 '18 at 15:11
5
$\begingroup$

If $M\models$ PA, the induction scheme of PA implies that every definable (nonempty) subset of $M$ has a minimal element:

  • Suppose $\varphi$ is a formula in the language of arithmetic; we want to show that either $\varphi^M$ is empty or $\varphi^M$ has a minimal element.

  • So let's suppose $\varphi^M$ has no minimal element. Let $\psi(x)\equiv \forall y\le x(\neg\varphi(y))$. Then:

    • $M\models\psi(0)$, since otherwise $0$ would be the minimal element of $\varphi^M$.

    • If $M\models\psi(n)$, then $M\models\psi(n+1)$: the only way we could have $\psi(n+1)$ fail in $M$ if $\psi(n)$ holds in $M$ would be for $\varphi(n+1)$ to hold in $M$, in which case - since $\psi(n)$ holds in $M$ - $n+1$ would be the least element of $\varphi^M$.

  • But now we can apply the induction scheme of PA - with formula $\psi$ - to conclude that $M\models\forall x\psi(x)$. And this means that $\varphi^M$ is empty.

OK, technically in the above I've only talked about parameter-freely definable sets. But it's easy to fold parameters into the argument above.


This means that if $M\models$ PA is nonstandard, then while in reality there are subsets of $M$ which have no minimal element, no such subset of $M$ is definable in $M$. That is: a nonstandard model of PA is "internally" well-founded, but "externally" ill-founded.

To get a sense of how the external-versus-internal distinction behaves, it might be easier to first consider a toy example. Let $\Sigma$ be the language consisting of a single unary function symbol $succ$ (which we'll think of as "successor"), a single binary relation symbol $<$ (self-explanatory), and a single constant symbol $0$ (self-explanatory). Now consider the $\Sigma$-theory $T$ consisting of:

  • "$succ$ is successor:" $\forall x(x<succ(x))\wedge\forall x,y(\neg(x<y\wedge y<succ(x))) .$

  • The induction scheme: for each formula $\varphi(x)$ in the language $\Sigma$, we have the axiom $$\varphi(0)\wedge\forall x[\varphi(x)\implies\varphi(succ(x))]\implies\forall x(\varphi(x)).$$ It's easy to show that there is a model $M$ of $T$ which "looks like $\mathbb{N}+\mathbb{Z}$" - concretely, one example of such a model is the following:

  • The domain of $M$ is all the integers except the negative even integers.

  • $<^M$ is given by: $$0<2<4<6<...\quad ...<-5<-3<-1<1<3<5<...,$$ and $succ^M$ is the successor operation with respect tot his ordering. The even nonnegative integers form the "$\mathbb{N}$-part" of $M$, and the odd integers form the "$\mathbb{Z}$-part" of $M$.

  • It is not trivial, but not hard either, to show $M\models T$. As a consequence, analogously to the argument above for PA every nonempty definable subset of $M$ has a minimal element.

  • However, clearly $M$ has external subsets with no minimal element - e.g. the "$\mathbb{Z}$-part." And the key point is that such external sets need not be hard to describe. There's nothing "absolutely" mysterious about these non-internally-definable sets without minimal elements; they're just mysterious from the point of view of the model itself.

$\endgroup$
3
  • $\begingroup$ So by completeness, I think you have proved that, for any arithmetical formula $\varphi$, if $PA \vdash \exists x \varphi(x)$, then $PA \vdash \exists m (\varphi(m) \land \forall y <m, \lnot\varphi(y))$. That looks like a model-independent way of saying that $PA$ is internally well-founded. $\endgroup$
    – V. Semeria
    Sep 25 '18 at 16:22
  • $\begingroup$ @V.Semeria Yes, that's correct. (Although the argument I've given is very close already to a formal deduction from PA.) $\endgroup$ Sep 25 '18 at 16:27
  • $\begingroup$ @NoahSchweber In your answer you write: "... in which case - since ψ(n) holds in M - n+1 would be ..." --- the single dash to signal an interjection there is somewhat confusing (it confused me; I read M - n + 1, wondering what it meant). I tried to edit, but it was apparently rejected in favor of a completely unrelated and useless edit. $\endgroup$
    – Jori
    Apr 28 '20 at 14:01

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.