Nonstandard Models of Arithmetic 31

Prev TOC Next

MW: Last time we learned about the “back-and-forth” condition for two countable structures M and N for a (countable) language L:

For all n, given any elements a1,…,anM and corresponding elements b1,…,bnN, if the (parameter-free) n-types are the same:

{φ(x1,…,xn)∈L : M⊧φ(a1,…,an)} = {φ(x1,…,xn)∈L : N⊧φ(b1,…,bn)}

then for any aM there is a bN so the 1-types of a and b with corresponding parameters (ai) and (bi) are the same:

{φ(x,x1,…,xn)∈L : M⊧φ(a,a1,…,an)} = {φ(x,x1,…,xn)∈L : N⊧φ(b,b1,…,bn)}

and vice versa, with the roles of M and N and the a’s and b’s switched.

When that holds, you can use the back-and-forth method to construct an isomorphism between M and N. We noted that the n=0 case is Th(M)=Th(N), i.e., M is elementarily equivalent to N.

Using this, we want to show that any two countable recursively saturated models M and N of PA are isomorphic if Th(M)=Th(N) and SSy(M)=SSy(N). First question: how do the standard systems SSy(M) and SSy(N) get into the act?

The basic idea: go “up, over, and down”. That is:

Using recursive saturation, we code a type in M. That gives us an element of SSy(M). Since SSy(M)=SSy(N), we’ve traversed two of links. Finally we have to translate the element of SSy(N) down to a type in N, again using recursive saturation. That’s the roadmap.

I recapped n-types in post 25, so I won’t go over all that again. Just a brief reminder about what ‘recursive’ means for them. The n-type {φi(x1,…,xn,e1,…,ek) : i∈ℕ} with parameters e1,…,ek is recursive if the set of Gödel numbers {⌜φi(x1,…,xn,y1,…,yk)⌝ : i∈ℕ} is recursive (with the y variables replacing the e parameters).

The n-type of elements a1,…,an (with or without parameters) unfortunately won’t always be recursive—Truth is Undefinable! We get around this with what I call the ‘equivalence trick’. Instead of the set

{φ(x1,…,xn) : M ⊧ φ(a1,…,an)}

we start with a recursive enumeration of all formulas of L(PA) with the free variables x1,…,xn, say {ψi(x1,…,xn) : i∈ℕ}. Then we look at the set of formulas

{[u]i =1 ↔ ψi(a1,…,an) : i∈ℕ}

where u is a variable; if u=c realizes this set, then c will be the intended code. (Recall that [c]i is the i-th bit of c, when c is written in binary.) The set of Gödel numbers

{⌜[u]i =1 ↔ ψi(x1,…,xn)⌝ : i∈ℕ}

is recursive because {ψi} is a recursive enumeration. Since M is recursively saturated, our set will be realized for a given choice of parameters a1,…,an, provided that every finite subset (with those parameters) is realized. But what does it mean to be realized by u=c? Just that the bits of the binary expansion for c agree with the truth values of “M⊧ψi(a1,…,an)” at the required places. Obviously we can find a c that’s good for any finite number of i’s. By recursive saturation, there is a c that works for all i∈ℕ.

Apply this to the back-and-forth condition. We want to add an a at the front of the list of ai’s, but this doesn’t affect the reasoning. For any a,a1,…,anM we have a code cM for the type of a,a1,…,an, in the sense that

M⊧[c]i =1 ⇔ M⊧ψi(a,a1,…,an)

Say S is the set {i∈ℕ : [c]i =1}. Since SSy(M)=SSy(N), S also belongs to SSy(N), and so there is a dN that codes it.

We want to show that the set

{[d]i =1 ↔ ψi(x,b1,…,bn) : i∈ℕ}

is realized in N by some x=b. In other words, N⊧ψi(b,b1,…,bn) ⇔ N⊧[d]i =1. This will insure that the types of (a,a1,…,an) in M and (b,b1,…,bn) in N are the same. Since N is recursively saturated, and the set {⌜[u]i =1 ↔ ψi(x,x1,…,xn)⌝ : i∈ℕ} is recursive, it’s enough to show that the set is finitely satisfiable. In other words, for any finite set I⊂ℕ, there is a bN such that

N ⊧ ⋀iI ( [d]i =1 ↔ ψi(b,b1,…,bn) )

Or in other words,

N ⊧ ∃xiI ( [d]i =1 ↔ ψi(x,b1,…,bn) )

Or splitting I up into the positions where [d]i =1 and where [d]i =0, say I=JK:

N ⊧ ∃x ( ⋀iJ ψi(x,b1,…,bn) ∧  ⋀iK ¬ψi(x,b1,…,bn) )

But the n-type of (b1,…,bn) records the truth or falsity of this ∃x (foo) sentence. And the n-type of (b1,…,bn) is inductively assumed to equal the n-type of (a1,…,an). So the corresponding assertion about M,

M ⊧ ∃x ( ⋀iJ ψi(x,a1,…,an) ∧  ⋀iK ¬ψi(x,a1,…,an) )

is true by the way c was obtained. So our set {[d]i =1 ↔ ψi(x,b1,…,bn) : i∈ℕ} is finitely satisfiable—done, Done, and DONE!

(The ‘done’ is for finite satisfiability, the ‘Done’ is for the result of this section, and the ‘DONE’ is for Enayat’s Theorem 7.)

It’s been a long road.

JB: Hurrah! I apologize for being so quiet, much like Socrates’ partners in Plato’s later dialogues It will take me a while to catch up. But congratulations: this whole series will be go-to reading for anyone who wants to understand nonstandard models of arithmetic.

Prev TOC Next

Leave a comment

Filed under Conversations, Peano Arithmetic

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.