Substructures and extensions loom large in math: subgroups, subrings, extension fields, submanifolds, subspaces of topological spaces… So too in the model theory of PA.
Say M⊆N, with N a structure for L(PA). We can characterize their relationship along a couple of dimensions.
We can ask how much M resembles N—at least through the lens of L(PA). At one end of the spectrum, M can be an elementary substructure of N. (Notation: M≼N. We also say N is a elementary extension of M.) This means that for any formula 
Notice that if 
I like a slight reframing of this definition: M≼N iff M and N satisfy exactly the same sentences of L(PA)M, which is L(PA) augmented with names for all the elements of M.
The arithmetic hierarchy immediately suggests a weaker relation: M is a Σn-elementary substructure of N (written M≼ΣnN) iff M and N satisfy exactly the same Σn sentences of L(PA)M. Note: since the negation of a Σn sentence is a Πn sentence, this is the same as ‘Πn-elementary substructure’. In the special case n=0, people usually write M≼Δ0N.
Even weaker: maybe M is just a substructure of N. This means naturally ‘structure for L(PA)’—so M must contain 0,1, and be closed under plus and times; also it inherits the <-relation from N (i.e., a<b in M iff a<b in N). Can we get any weaker? Yes! We can demand only that M is closed under plus. Or still weaker: just under successor. Of course, many sentences of L(PA) cease to have meaning for M in this scenario. But such M’s can still reward attention. Or we might have an M that actually is a substructure, but we don’t know that a priori.
The <-relation furnishes another dimension to look at. Suppose as before that M⊆N. If every element of N\M is greater than every element of M, we say N is an end extension of M, and M is an initial segment of N. (Notation: M⊆eN.) At the other extreme, if every element of N is less than or equal to some element of M, we say M is cofinal in N. (Notation: M⊆cfN.) The two extremes are not incompatible! But of course, if M is both an initial and a cofinal segment of N, then M=N.
(Incidentally, in axiomatic set theory, the analog of ‘initial segment’ is ‘transitive subclass’. This is a class M such that if a∈b∈M, then a∈M.)
An initial segment closed under successor is called a cut.
If an initial segment contains 2 and is closed under multiplication, then its a substructure. For this reason, Wong calls an initial substructure a ‘multiplicative cut’.
Our two “characterization dimensions” are not independent. For example, if M⊆eN, then M≼Δ0N. Basic idea: the meaning of “∃x<t” and “∀x<t” is the same for M and N when t is an element of M. (For a detailed argument, see Kaye, Theorem 2.7 p.24. Or do it as an exercise—a routine induction on formula complexity.)
If M and N are models of PA, we have something stronger: M⊆eN implies M≼Δ1N. Recall that Δ1—or more correctly, Δ1(PA)—means that we have a Σ1 formula φ and a Π1 formula ψ, and PA proves that they are equivalent. It’s easy to see that Σ1 formulas are upwards persistent and Π1 formulas are downward persistent for L(PA) structures, so with the pair φ,ψ we have persistence in both directions for models of PA. We noted in Topics 3 that all recursive relations are Δ1(PA), so this is often useful.
How about a converse for the Δ0 result? For L(PA) structures, does M≼Δ0N imply M⊆eN? Nope! Indeed, we can have M≼N with M⊆cfN and M≠N. (Notation: M≺N and M⊂cfN. Caveat: some authors use ≺ and ⊂ to mean ≼ and ⊆.)
I like to think about such a pair (M≺N and M⊂cfN) with an espionage metaphor, inspired by The Americans. Elements of N have infiltrated M—let’s call them moles. A mole, then, is an a∈N with a∉M and a less than some element of M. It lives among the true elements of M. It does everything it can to “blend in”—that is, if φ(x) is a formula satisfied by all elements of M (so M⊧∀x φ(x)), then the mole tries to satisfy φ(x) too (i.e., N⊧φ(a), for a fully disguised mole). Parameters from M are allowed in the formulas: if c is an element of M such that M⊧∀x φ(x,c), then N⊧φ(a,c). Beware suspicious neighbors!
(Observe, though, that the immediate neighbors of a mole are also moles: if a is a mole, then a±n is a mole for all n∈ℕ. In other words, the whole “ℤ-patch” containing the mole consists of moles.)
Perhaps the mole isn’t quite so proficient at disguise: maybe it only satisfies all the Δ0 formulas (or all the Σn formulas) that hold universally in M. Finally, both the mole and the parameters could be tuples (a cell; a neighborhood watch).
For proper elementary end extensions (M≺N and M⊂eN) I like to use a Roman analogy. The Roman Empire extended citizenship to the denizens of the provinces it conquered. Imagine that M is Rome, N\M are the provinces, and formulas universally valid in M are the rights and perquisites of Roman citizenship.
Here’s a grab bag of facts about extensions. I may outline proofs (none of which are trivial) for some of these in later posts.
- The MacDowell-Specker Theorem: every model of PA has a proper elementary end extension.
- Every nonstandard model of PA has a proper elementary cofinal extension.
- If M⊆cfN, M⊧PA, N⊧PA−, and M≼Δ0N, then M≼N, so N⊧PA also. (The “mole disguise” lemma! If you’re Δ0 disguised, you’re fully disguised.)
- Gaifman’s Splitting Theorem: If M and N are models of PA with M⊆N, then there is a unique K such that M⊆cfK⊆eN. This K is an elementary extension of M, so it’s also a model of PA.
- Friedman’s Theorem: Every countable nonstandard model of PA is isomorphic to a proper initial segment of itself. Moreover we can demand that the segment contain any given element of the model, and that it be a Σn-elementary submodel, for any given n.
A few words about these items. The MacDowell-Specker Theorem is an older result (1961). Gaifman later strengthened this: every model of PA has a proper elementary conservative extension. Here, N is a conservative extension of M if every definable subset of N, when intersected with M, gives a definable subset of M. The definitions can use parameters, although the defining formula and the parameters can be different for the subset S⊆N and its intersection S∩M. It’s a nice exercise to show that any conservative extension is an end extension. (Hint: if not, there are moles.)
The second and third bullets are also due to Gaifman. (The third bullet helps prove the second.) Gaifman’s Splitting Theorem uses the celebrated MRDP theorem, aka the solution to Hilbert’s 10th problem. I’ll say more about it in the next Topics post. But I will mention a corollary to MRDP, another fact for the grab bag:
- If M⊆N and both M and N are models of PA, then M≼Δ0N.
The hypothesis of countability in Friedman’s Theorem can’t be dropped, nor can you replace ‘Σn-elementary’ with ‘elementary’. There are models of PA with cardinality ℵ1 whose proper initial segments are all countable, so they’re obviously not isomorphic to the model. And there are countable nonstandard models of PA (so-called prime or minimal models) that have no proper elementary submodels at all, let alone initial ones. On the other hand, when the hypotheses do hold, there’s not just one, but 2ℵ0 such submodels! (That is, isomorphic proper initial Σn-elementary submodels. Why does this not contradict the countability of the model? Hint: think about ℚ.)
Diagonal Argument 
Very interesting!
Am I correct that, for a mole w belonging to N\M, not only is w’s ℤ-patch made of moles, but w+x and w-x are moles for every x ∈ M? In fact, I think you can partition N using the equivalence relation abs(x-y) ∈ M, with one equivalence class being M. (By abs(x-y) I mean either x-y or y-x depending on whether x<y.)
That’s right. More generally, for any model N of PA we have a corresponding ring N± of “integers”. Let’s say M⊆N are two models, forget about cofinal or not. And let’s say M±⊆N± are the corresponding rings of “integers”. Then M± is a subring of N±. Forgetting about multiplication for the moment, M± and N± are abelian groups, so you can form the quotient group N±/M±. That’s what your equivalence relation produces (mutatis mutandis).
Now as for cofinality, let’s say K is the cofinal part of N: K={x∈N : ∃y∈M x≤y}. So M⊆cfK⊆eN, and it’s easy to see that K is an initial substructure of N. K\M are the “moles”. K± contains M±, and we can form K±/M± as an abelian group. We can also form N±/K± . M thinks of the elements of K as “finite”, so to speak, and the elements of N\K as “infinite”.
Gaifman’s Splitting Theorem tells us that K is a model of PA, but it’s not hard to see directly that K satisfies PA−. (Use downward Π1 persistence.)
Reintroducing multiplication, M± is a subring of K±, which is a subring of N±. But to form a quotient ring, you need to divide out by an ideal. Since 1 belongs to all three subrings, you don’t get ideals except for the trivial cases where a ring equals a subring.
There’s a bunch of interesting algebra swirling around these nonstandard models of PA. Sometime I may get round to writing about that.
(Correction: w-x is either a mole (if w > x) or doesn’t exist (if w < x).)
If we apply Gaifman’s Splitting Theorem to M and N with M ⊆cfN, then I assume we get K = N. But then it says M≼N, which seems stronger than what you said directly about M ⊆cfN.
That’s right. If M⊆cfN and M and N are both models of PA, then M≼N. But the proof of this relies on the MRDP theorem, hardly a straighforward result. It solved a Hilbert problem!
One sad thing about so-called “modern algebra” is that it talks a lot about rings but very little about rigs, so we need to process a model of Peano arithmetic, which is a rig, and get a ring before modern algebra will have anything to say about it. This is mainly just a defect in modern algebra as currently taught: in the future it will cover rigs as well, and people will call the current version “primitive algebra”.
Nice! For models of PA, though, N sits transparently inside N±, expressed briefly by writing N±=N∪(−N). In other words, every element of N± is either n or −n for some n∈N, and only 0 is both. A more complicated story I know for monoids in general and their so-called universal enveloping groups (see §2.2 of my Leinster notes, especially pp.33–34). I assume also not so simple for rigs and rings, in general.