7
$\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 15:11

1 Answer 1

7
$\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
  • 1
    $\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, 2018 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, 2018 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, 2020 at 14:01

You must log in to answer this question.

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