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*≼

_{Σn}

*N*) iff

*M*and

*N*satisfy exactly the same Σ

_{n}sentences of L(PA)

*. Note: since the negation of a Σ*

_{M}_{n}sentence is a Π

_{n}sentence, this is the same as ‘Π

*-elementary substructure’. In the special case*

_{n}*n*=0, people usually write

*M*≼

_{Δ0}

*N.*

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*⊆_{e}*N*.) 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*⊆_{cf}*N*.) 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*⊆_{e}*N*, then *M*≼_{Δ0}*N*. 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*⊆_{e}*N* implies *M*≼_{Δ1}*N*. 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*≼_{Δ0}*N* imply *M*⊆_{e}*N*? Nope! Indeed, we can have *M*≼*N* with *M*⊆_{cf}*N* and *M*≠*N*. (Notation: *M*≺*N* and *M*⊂_{cf}*N*. Caveat: some authors use ≺ and ⊂ to mean ≼ and ⊆.)

I like to think about such a pair (*M*≺*N* and *M*⊂_{cf}*N*) 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*⊂_{e}*N*) 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*⊆_{cf}*N,**M*⊧PA,*N*⊧PA^{−}, and*M*≼_{Δ0}*N*, 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*⊆_{cf}*K*⊆_{e}*N*. 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 Σ
-elementary submodel, for any given_{n}*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*≼_{Δ0}*N*.

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 Σ

*-elementary submodels. Why does this not contradict the countability of the model? Hint: think about ℚ.)*

_{n}
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

Nof PA we have a corresponding ringN^{±}of “integers”. Let’s sayM⊆Nare two models, forget about cofinal or not. And let’s sayM^{±}⊆N^{±}are the corresponding rings of “integers”. ThenM^{±}is a subring ofN^{±}. Forgetting about multiplication for the moment,M^{±}andN^{±}are abelian groups, so you can form the quotient groupN^{±}/M^{±}. That’s what your equivalence relation produces (mutatis mutandis).Now as for cofinality, let’s say

Kis the cofinal part ofN:K={x∈N: ∃y∈Mx≤y}. SoM⊆_{cf}K⊆_{e}N, and it’s easy to see thatKis an initial substructure ofN.K\Mare the “moles”.K^{±}containsM^{±}, and we can formK^{±}/M^{±}as an abelian group. We can also formN^{±}/K^{±}.Mthinks of the elements ofKas “finite”, so to speak, and the elements ofN\Kas “infinite”.Gaifman’s Splitting Theorem tells us that

Kis a model of PA, but it’s not hard to see directly thatKsatisfies PA^{−}. (Use downward Π_{1}persistence.)Reintroducing multiplication,

M^{±}is a subring ofK^{±}, which is a subring ofN^{±}. 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

algebraswirling 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

MandNwithM⊆_{cf}N, then I assume we getK=N. But then it saysM≼N, which seems stronger than what you said directly aboutM⊆_{cf}N.That’s right. If

M⊆_{cf}NandMandNare both models of PA, thenM≼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

ringsbut very little aboutrigs, 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,

Nsits transparently insideN^{±}, expressed briefly by writingN^{±}=N∪(−N). In other words, every element ofN^{±}is eithernor −nfor somen∈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.