In Wikipedia, it says that a nonstandard model of natural numbers is not first-order. But, from the Lowenheim-Skolem theorem, I don't see anything that points to this conclusion. Can anyone show me how to deduce this result from the theorem?

Thanks very much.

Here's the quote:

Let N denote the natural numbers and R the reals. It follows from the theorem that the theory of (N, +, ×, 0, 1) (the theory of true first-order arithmetic) has uncountable models, and that the theory of (R, +, ×, 0, 1) (the theory of real closed fields) has a countable model. There are, of course, axiomatizations characterizing (N, +, ×, 0, 1) and (R, +, ×, 0, 1) up to isomorphism. The Löwenheim–Skolem theorem shows that these axiomatizations cannot be first-order. For example, the completeness of a linear order, which is used to characterize the real numbers as a complete ordered field, is a non-first-order property.

(from Wikipedia Löwenheim–Skolem_theorem: Examples_and_consequences )

  • $\begingroup$ I recommend posting a link to the Wikipedia article and quoting it verbatim so potential helpers can know exactly what you're referring to. $\endgroup$ – Quinn Culver Mar 30 '12 at 3:20
  • $\begingroup$ I don't see anything it that quote that implies "a finite model of natural numbers is not first-order". $\endgroup$ – Ted Mar 30 '12 at 3:36
  • $\begingroup$ @Ted oops. my typo. I was intending to write nonstandard.... $\endgroup$ – user27515 Mar 30 '12 at 3:47
  • 1
    $\begingroup$ I don't know what it would mean for a model to not be first-order, and that quote doesn't make any use of such a notion. The only things it refers to as being non-first-order are axiomatizations and properties. $\endgroup$ – Chris Eagle Mar 30 '12 at 9:40

What the section you've quoted is discussing is "axiomatizations characterizing $(N,+,\times,0,1)$ and $(R,+,\times,0,1)$ up to isomorphism." This means axioms which have only a single model, up to isomorphism. The Löwenheim-Skolem theorems tell us a first-order theory with an infinite model has infinite models of every infinite cardinality. This justifies the statement made in the quoted section.

As has been pointed out, this quoted section is not a discussion about finite models for those first-order theories. Clearly no reasonable first-order theory "characterizing" $N$ or $R$ would have a finite model, though one might articulate a first-order theory (e.g. commutative semi-rings) which has both finite models as well as infinite models $(N,+,\times,0,1)$ and $(R,+,\times,0,1)$.

Added: Since the Question was edited to replace "finite model" with "nonstandard model", I'll try to respond to that update. The quoted passage (from Wikipedia) says nothing about nonstandard models explicitly, but the implication is not far from the surface that any first-order theory with "standard" models $\mathbb{N}$ of natural numbers and $\mathbb{R}$ of real numbers, respectively, must have nonstandard models as well (models that are not isomorphic to the standard ones). This is again evident from the Löwenheim-Skolem theorems, since models of different cardinality clearly are not isomorphic.

The formulation "a nonstandard model of natural numbers is not first-order" is suspect because we define "first-order" as a property of a theory (logic+language+axioms), and not in any direct sense as a property of models. Perhaps you mean that it is not possible to "characterize" a nonstandard model of natural numbers with first-order logic, but even so your meaning stands in need of clarification about the kind of characterization sought. If the meaning is "up to isomorphism" (also known as the categorical property of first-order theories), then the Löwenheim-Skolem theorems are sufficient for the purpose for reasons already discussed.

  • $\begingroup$ @ChrisEagle: Thanks, I'll correct that! $\endgroup$ – hardmath Mar 30 '12 at 9:41

"In Wikipedia, it says that a nonstandard model of natural numbers is not first-order."

It says nothing of the kind. If it did, the meaning of that assertion would not be clear. And indeed if you look at the standard argument that leads to a non-standard model of arithmetic, you will see that it uses basic tools from first-order logic. Recall that to the usual language for arithmetic (constant symbol $0$, unary function symbol $S$ (successor), and binary function symbols $+$ and $\times$, we add a constant symbol $M$, and axioms $\lnot(M=0)$, $\lnot(M=S0)$, $\lnot(M=SS0)$, and so on. Every finite subset of our set of axioms has a model, so by Compactness our set of axioms has a model, which cannot be isomorphic to the natural numbers.

  • $\begingroup$ why can't it be isomorphic to the naturals? $\endgroup$ – pichael May 28 '12 at 5:54
  • $\begingroup$ Because the interpretation of $M$ is different from the interpretations of $0$, $S0$, and so on forever. So no isomorphism could take it to $2012$. $\endgroup$ – André Nicolas May 28 '12 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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