Well-orders on non-standard models of Peano arithmetic

Question

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.

Answer 1

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.