# Well-orders on non-standard models of Peano arithmetic

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.

• 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. Sep 25 '18 at 13:05
• 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. Sep 25 '18 at 13:07
• "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". Sep 25 '18 at 13:11
• 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. Sep 25 '18 at 13:25
• It would not be an element of the model. That is, it is not coded by any element of the model. Sep 25 '18 at 15:11

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

• 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.

• 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. Sep 25 '18 at 16:22
• @V.Semeria Yes, that's correct. (Although the argument I've given is very close already to a formal deduction from PA.) Sep 25 '18 at 16:27
• @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.
– Jori
Apr 28 '20 at 14:01