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.
 A: 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.
