I'd like to know where the following result comes from (that is, whether there is a more general result from which it follows or else how it can be proven):
There is no first-order sentence which is true in all non-standard models of arithmetic but false in the standard one, whereas there are second-order sentences which have this property.
(I've found this briefly stated in the wikipedia article on Nonfirstorderizability)
Help is much appreciated. Thanks!
Best,
Berta
Let $\varphi$ be any sentence that is false in the natural numbers. Let theory $T$ be first-order Peano arithmetic with $\lnot\varphi$ as an added axiom. Then $T$ has a model, the natural numbers. Thus by the Lowenheim-Skolem Theorem, $T$ has models of arbitrarily high cardinality, and in particular models other than $\mathbb{N}$. The sentence $\varphi$ is not true in such a model.
Let $\varphi$ be a sentence that is true in all non-standard models of arithmetic but false in the standard model.
Then the theory T constructed by adding $\neg \varphi$ to Peano's axioms has a unique model; the standard model of arithmetic.
Thus, every statement $P$ in the language of number theory is either true in every model of $T$ or false in every model of $T$. In particular, Gödel's completeness theorem implies that every such $P$ is provable or disprovable: $T$ is complete.
Our axioms for $T$ are recursively enumerable, so Gödel's first incompleteness theorem implies $T$ must be incomplete: thus we get a contradiction.
In order to understand this fact, see George Boolos, Logic Logic and Logic (1998), page 57 :
[Consider the formula : ]
(C) $\quad \exists X(\exists x Xx \land \forall x \forall y[Xx \land (x = 0 \lor x = y+1) \rightarrow x \ne y \land Xy])$.
[It] is a sentence that is true in all nonstandard models of arithmetic but false in the standard model [footnote : To see that (C) is true in any nonstandard model, take as $X$ the set of all nonstandard elements of the model. $X$ is nonempty, does not contain $0$, hence contains only successors, and contains the immediate predecessor of any of its members.]
To see that it is false in the standard model, suppose that there is some suitable set $X$ of natural numbers. $X$ must be nonempty: if its least member $x$ is $0$, let $y = 0$; otherwise $x = y + 1$ for some $y$. Since $x$ is least, $y$ is not in $X$, and "$Xy$" is false.
For non-standard models of first-order $\mathsf {PA}$, see George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007), page 304 :
To sum up: the elements of the domain of any nonstandard model $\mathcal M$ of arithmetic are going to be linearly ordered by LESS THAN. This ordering will have an initial segment that is isomorphic to the usual ordering of natural numbers, followed by a sequence of blocks, each of which is isomorphic to the usual ordering of the integers (negative, zero, and positive). There is neither an earliest nor a latest block, and between any two blocks there lies a third. Thus the ordering of the blocks is what was called [...] a dense linear ordering without endpoints, and so, it is isomorphic to the usual ordering of the rational numbers.
Added
Assuming that we have convinced ourselves that the formula (C) is true every non-standard model but false in $\mathbb N$, if we assume that (C) is expressible in first-order logic, we can use it as the formula $\varphi$ of Hurkyl's answer and the conclusion follows.
Why aren't there any first-order sentences which have the property of being true in all non-standard models of PA and false in the standard one?
There is a set of sentences with the property that all sentences are true in all non-standard models of PA, but infinitely many are false in the standard one:
$\omega \neq 0$, $\omega \neq \sigma(0)$, $\omega \neq \sigma(\sigma(0))$, ...
For these formulas to be sentences, $\omega$ must be a constant and part of the signature $S=\{\sigma,0,\omega\}$.
