Nonstandard Models of Arithmetic 25

Previous Enayat post

MW: It’s been ages since John Baez and I discussed Enayat’s paper—not since October 2020! John has since moved on to fresh woods and pastures new. I’ve been reading novels. But I feel I owe it to our millions of readers to finish the tale, so here goes.

Since it has been awhile, I’ll start with a recap. Last season on Nonstandard Models of Arithmetic…

Our goal was to understand Enayat’s paper, Standard Models of Arithmetic. The very title seems a bit paradoxical—nonstandard standard models of arithmetic?!? But by “standard”, Enayat means “the ‘standard’ (nonnegative) integers ω in a model of ZF set theory”.

Since John has been duking it out with Plato’s ghost for decades, and I like to pretend to be a Platonist,  it took us a little while just to agree on terminology. We finally settled on the “three decker sandwich” paradigm, whose bumper-sticker reads

ωUUV.

Here V is the “real” universe of all sets, where “real” just means “we won’t be looking outside of V”. U is a model of ZF sitting inside V. And ωU is what U “thinks is the real ω”. Since U is not the “real” universe of all sets, its ω need not be the “real” ω (the ω of V). In fact, ωV must be an initial segment of ωU. That’s because ZF can prove that ω is an initial segment of any model of PA.

(We assume of course that V satisfies ZF. And since V is the outermost universe, I’ll usually just write ω instead of ωV.)

Enayat says that ωU is ZF-standard. Most important: ωU may be nonstandard so far as V is concerned. In that case of course, U must look pretty strange to V. If U is a model of some extension T of ZF, Enayat says that ωU is T-standard.

Enayat’s question: can we characterize T-standard models of PA, for a recursively axiomatizable T extending ZF? Enayat proves a couple of big results that go far towards an answer. These both mention recursive saturation, a concept that occupied us for several posts. While recapping this, I’ll dot some i’s and cross some t’s.

We start with the concept of an n-type for a model N of PA. (We first encountered these in post 1 and post 2.) If a1,…,anN, then the n-type of (a1,…,an) is the set of all formulas φ(x1,…,xn) in L(PA) such that N⊧φ(a1,…,an). Or actually, since we want to allow parameters:

• The n-type of (a1,…,an) with parameters c1,…,cmN is

{φ(x1,…,xn,y1,…,ym)∈L(PA): N⊧φ(a1,…,an,c1,…,cm)}.

• Because of the recursive pairing mechanism of PA, we can restrict ourselves to one free variable and one parameter: {φ(x,y)∈L(PA) : N⊧φ(a,c)}. In other words, any n-type can be “coded” as a 1-type. This fact will make our notation less cluttered. I’ll just write “type” from now on.

These are the realized types. What about types more generally? First recall that ThN(N) is the set of all sentences in LN(PA) that hold in N, where LN(PA) is L(PA) augmented with a name for every element of N. (ThN(N) is called the elementary diagram of N.) Note that ThN(N) is a complete theory. Also, every model of ThN(N) contains an isomorphic copy of N.

• A type over N is a set of formulas in LN(PA), {φi(x,c) : i∈ℕ}, that is consistent with ThN(N) in this sense: if a is a brand-new constant, then ThN(N)+{φi(a,c) : iI} is a consistent theory.
• (Here c is supposed to be the only name from N, so all the φi(x,y) belong to L(PA).)
• (If the type has only finitely many different formulas, just repeat one of them endlessly.)
• Equivalently, by the Completeness Theorem, N has an extension M containing an element a such that M⊧φi(a,c) for all φi. The element a realizes the type in M.

It’s useful to think of a type as an infinite conjuction:

• Think of {φi(x,c) : i∈ℕ} as ⋀i∈ℕ φi(x,c).
• Because ThN(N)+{φi(a,c) : i∈ℕ} is consistent iff every finite subset is, we have another version of the consistency requirement: ThN(N)+{φi(a,c) : 1≤ik} is consistent for every k.
• Because a is a brand-new constant, yet another: ThN(N)+∃x1≤ik φi(x,c) is consistent for every k.
• Because ThN(N) is complete, yet one more version: ThN(N)⊢∃x1≤ik φi(x,c) for every k.
• Or finally, this version: N⊧∃x1≤ik φi(x,c) for every k.

After all that throat-clearing, we’re ready for the notion of saturated:

• N is saturated if every type that is realized in some elementary extension of N (i.e., model of ThN(N)) is already realized in N.
• Equivalently: given a set of formulas {φi(x,c) : i∈ℕ} as above, if for every k we have N⊧∃x1≤ik φi(x,c), then N contains an element a such that N⊧φi(a,c) for all i∈ℕ.

For recursively saturated we need the concept of a recursive type:

• A type {φi(x,c) : i∈ℕ} over N is recursive when the set of Gödel numbers {⌜φi(x,y)⌝ : i∈ℕ} is a recursive set.
• Notice that all the φi(x,y) belong to L(PA). We sidestep the question, what would “recursive” even mean for non-standard parameters?  We begin with a recursively given collection of formulas in L(PA), and then plug the parameter in.
• N is recursively saturated if every recursive type is realized in N.

That’s quite a lot to chew on. I’ll finish the recap in the next post.

Previous Enayat post