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 in L(PA) and any tuple in M (of the right length),
Notice that if is in N but not in M, then “” doesn’t even make any sense.
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.)
How about the converse? 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 ℚ.)