# 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.)

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

Filed under Conversations, Peano Arithmetic

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