Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume first-order Peano arithmetic is consistent and $N$ is its model, we know that every subset of $N$ contains a minimal element. It's a second-order property so I am not sure if it hold in nonstandard models, or specifically, in countable nonstandard models?

Here we define $x<y$ as $\exists z\ne0(x+z=y)$. Anyone can provide some ideas will be appreciated. Thanks!

share|improve this question

3 Answers 3

up vote 8 down vote accepted

It does not hold in any non-standard model, because all such models have to satisfy the sentence that says that every number except $0$ is a successor. In this Wikipedia article you’ll find a description of the order type of countable non-standard models of PA.

share|improve this answer
    
Thanks for the reference! I am reading it. –  Chao Chen Dec 14 '12 at 9:42
    
@ChaoChen: You’re welcome. –  Brian M. Scott Dec 14 '12 at 9:54

It is a general fact that no theory with infinite models defines a wellordering (or even a wellordering on an infinite definable subset).

You can check it easily using compactness or ultraproducts.

For example, take any model $M$ and a definable relation $<$ on $M$ such that it is a wellordering on $\varphi(M)$ (where $\varphi$ is the formula defining the set on which $<$ is a wellordering), and $\{a_n\mid n\in\omega\}\subseteq \varphi(M)$ -- an infinite increasing sequence.

Then if you take whe ultrapower $M^\omega/\mathcal U$ of $M$ with respect to some non-principal ultrafilter $\mathcal U$, then the sequence $b_n=[a_0,\ldots,a_0,a_1,a_2,\ldots]$ (with $n$ $a_0$-s at the beginning) is a subset of $\varphi(M^\omega/\mathcal U)$ and is an infinite decreasing sequence with respect to $<$.

This applies, in particular, to models of set theory, and is one of the reasons why the axiom of foundation is formulated the way it's formulated, and not in some more intuitive way. As a consequence, in an arbitrary model $M$ of ZFC, $\in^M$ need not be well-founded, not even if we restrict it to $\omega^M$.

share|improve this answer

Here is a useful fact, which is not hard to prove, that answers the question (and so it gives a self-contained proof that no nonstandard model of PA is well-ordered).

Fact: In any nonstandard model $M$ the set of standard natural numbers is an initial segment of $M$, but it is never definable in $M$, even with parameters from $M$.

Proof: assume the set of standard numbers is definable by a formula $\phi(n)$ that may have parameters from $M$. Then $\phi(x)$ holds for each $x \in M$ if and only if $x$ is standard, so $\psi(y) = (\forall x \leq y)\phi(x)$ also holds exactly when $y$ is standard, because the set of standard numbers is downward closed. Thus $M$ satisfies $\psi(0)$ and $M$ satisfies $(\forall y)[\psi(y) \to \psi(y+1)]$, but $M$ does not satisfy $(\forall y)\psi(y)$, because $M$ is nonstandard and $\psi$ only holds for standard numbers. Thus the axiom scheme of induction, which is part of PA, cannot hold in $M$, because the instance of the scheme for $\psi$ fails. This is a contradiction, because $M$ satisfies PA.

Now to answer the question. If $M$ is nonstandard, the set $$\{n \in M : n \text{ is not standard }\}$$ cannot have a least element $x$. If it did, then $\{y \in M : y < x\}$ would be the set of standard numbers, and this set would be definable using $x$ as a parameter, but the set of standard numbers is not definable in $M$.

share|improve this answer
    
This proof is quiet nice. –  Chao Chen Dec 17 '12 at 13:31
    
Thanks. Brian M. Scott's answer also shows how to give a complete proof, but I thought that this fact in particular might be useful to know as you look at PA. The name attached to it is "overspill"; it is usually phrased as "any definable set in a model of PA that includes all the standard numbers also includes some nonstandard numbers". You can also do the proof with $\phi$ alone, without using $\psi$, but sometimes it is convenient to use the $\psi$ form, because then by overspill you get a nonstandard number such that everything less than it (even if nonstandard) satisfies the formula. –  Carl Mummert Dec 17 '12 at 13:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.