JB: The only books I know on models of Peano arithmetic are Kaye’s Models of Peano Arithmetic and Kossack and Schmerl’s more demanding The Structure of Models of Peano Arithmetic, and I’m trying to read both. But I have a certain dream which is being aided and abetted by this paper:
• Ali Enayat, Standard Models of Arithmetic.
Roughly, my dream is to show that “the” standard model is a much more nebulous notion than many seem to believe.
One first hint of this is the simple fact that for any sentence that’s not decidable in Peano Arithmetic, there are models where this sentence is satisfied and models where it’s not. In which camp does the standard model lie? We can only say: “one or the other”. And the same is true in any recursively enumerable consistent extension of PA. There are always undecidable sentences in any such extension, and there are always models—infinitely many, in fact—where the sentence is satisfied, and infinitely many where it is not!
So, choosing “the” standard model among all the pretenders—or even this lesser task: finding it up to elementary equivalence—is a herculean task, like finding ones way through an infinite labyrinth of branching paths, where at each branch deciding which way to go requires brand-new insights into mathematics, not captured by our existing axioms. I’m not convinced it makes sense to talk about the “right” decision in every case.
Another hint is the Overspill Lemma, used ubiquitously in the study of nonstandard models. Roughly:
Overspill Lemma: In a nonstandard model of Peano arithmetic, any predicate in the language of arithmetic that holds for infinitely many standard natural numbers also holds for infinitely many nonstandard ones.
Corollary: There is no way to write down a predicate in the language of arithmetic that singles out the standard natural numbers.
So, if our supposed “standard” model were actually nonstandard, we still couldn’t pick out the nonstandard numbers. The aliens could be among us, and we’d never know!
But you know all this stuff, and probably have different interpretations of what it means. I don’t mainly want to argue about that; I mainly want to learn more, so I can prove some interesting theorems.
So, thanks for your great introduction! I especially love the idea of types, which I just learned. Your explanation was great. Here’s more, in case anyone is reading:
• Types (model theory), Wikipedia.
You didn’t quite get to “recursively saturated models”, so I pestered Joel David Hamkins (a logician I know, now at Oxford) and got this nice explanation, which fits nicely with yours:
Saturation is about realizing types. The type of an element a in a model M is the set of all formulas such that M satisfies . You can allow parameters in a type. For example, if you consider the reals as an ordered field, then any two elements a and b have different types, since there is some rational between them, and a, say, will realize the formula , while b does not. This formula is expressible in the language of fields.
Does realize all types that it could? No, because you can write down a collection of formulas asserting that and . This is expressible in that language, and it is consistent with the diagram of the reals, meaning that this type could be realized in some elementary extension of . The type asserts that x is a positive infinitesimal number. So the reals are not saturated.
Indeed, since that type was very easy to describe, the reals are not even recursively saturated (I usually call it computably saturated). To be recursively saturated, a model M must realize every computable type (the formulas, as a set, are a computable set of formulas) that is consistent with its diagram.
In general, saturated models are very thick—they have lots of points of all the types that one could in principle have in a model of that theory. Usually, countable models are not saturated (except when the language is trivial in some way). To get around this, the idea of recursive saturation works very well with countable models, and this is what is going on in Kaye’s book.
Hope this helps, and let me know if I can explain anything more about it…
It’s so much easier to learn stuff by talking with people than by fighting through a thicket of logic symbols! But it’s also good for me to keep reading the books.