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 a₁,…,a_n∈M and corresponding elements b₁,…,b_n∈N, if the (parameter-free) n-types are the same:

{φ(x₁,…,x_n)∈L : M⊧φ(a₁,…,a_n)} = {φ(x₁,…,x_n)∈L : N⊧φ(b₁,…,b_n)}

then for any a∈M there is a b∈N so the 1-types of a and b with corresponding parameters (a_i) and (b_i) are the same:

{φ(x,x₁,…,x_n)∈L : M⊧φ(a,a₁,…,a_n)} = {φ(x,x₁,…,x_n)∈L : N⊧φ(b,b₁,…,b_n)}

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(x₁,…,x_n,e₁,…,e_k) : i∈ℕ} with parameters e₁,…,e_k is recursive if the set of Gödel numbers {⌜φ_i(x₁,…,x_n,y₁,…,y_k)⌝ : i∈ℕ} is recursive (with the y variables replacing the e parameters).

The n-type of elements a₁,…,a_n (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

{φ(x₁,…,x_n) : M ⊧ φ(a₁,…,a_n)}

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

{[u]_i =1 ↔ ψ_i(a₁,…,a_n) : 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(x₁,…,x_n)⌝ : 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 a₁,…,a_n, 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(a₁,…,a_n)” 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 a_i’s, but this doesn’t affect the reasoning. For any a,a₁,…,a_n∈M we have a code c∈M for the type of a,a₁,…,a_n, in the sense that

M⊧[c]_i =1 ⇔ M⊧ψ_i(a,a₁,…,a_n)

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 d∈N that codes it.

We want to show that the set

{[d]_i =1 ↔ ψ_i(x,b₁,…,b_n) : i∈ℕ}

is realized in N by some x=b. In other words, N⊧ψ_i(b,b₁,…,b_n) ⇔ N⊧[d]_i =1. This will insure that the types of (a,a₁,…,a_n) in M and (b,b₁,…,b_n) in N are the same. Since N is recursively saturated, and the set {⌜[u]_i =1 ↔ ψ_i(x,x₁,…,x_n)⌝ : 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 b∈N such that

N ⊧ ⋀_i∈I ( [d]_i =1 ↔ ψ_i(b,b₁,…,b_n) )

Or in other words,

N ⊧ ∃x ⋀_i∈I ( [d]_i =1 ↔ ψ_i(x,b₁,…,b_n) )

Or splitting I up into the positions where [d]_i =1 and where [d]_i =0, say I=J⊔K:

N ⊧ ∃x ( ⋀_i∈J ψ_i(x,b₁,…,b_n) ∧  ⋀_i∈K ¬ψ_i(x,b₁,…,b_n) )

But the n-type of (b₁,…,b_n) records the truth or falsity of this ∃x (foo) sentence. And the n-type of (b₁,…,b_n) is inductively assumed to equal the n-type of (a₁,…,a_n). So the corresponding assertion about M,

M ⊧ ∃x ( ⋀_i∈J ψ_i(x,a₁,…,a_n) ∧  ⋀_i∈K ¬ψ_i(x,a₁,…,a_n) )

is true by the way c was obtained. So our set {[d]_i =1 ↔ ψ_i(x,b₁,…,b_n) : 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