# Nonstandard Models of Arithmetic 30

MW: Time to finish off Enayat’s Theorem 7:

Theorem 7: Every countable recursively saturated model N of PA+ΦT is a T-standard model of PA.

All that’s left is part 4 of the proof. This follows from this fact:

Any two countable recursively saturated models of PA are isomorphic if they have the same first-order theory and the same standard system. That is, if Th(M)=Th(N) and SSy(M)=SSy(N) and M and N are countable and recursively saturated, then MN.

Thanks to the previous parts of the proof, we have a model U of T with SSy(ωU)=SSy(N) and Th(ωU)=Th(N), and with ωU countable and recursively saturated. So set MU, and QED!

(Incidentally, this is the only part of the proof using the countability assumption.)

OK, how about that fact? Pretty interesting on its own account. While I won’t give a full-bore proof, I do have quite a bit to say about it.

For starters, the proof uses the back-and-forth method. Very likely you’ve seen this used to prove one of Cantor’s theorems: any two countable dense linear orderings without endpoints (DLOs) are isomorphic. It’s a beautifully simple argument. (Skip ahead if you’ve seen it.) Let {a1,a2,…} and {b1,b2,…} be enumerations of the two orderings. We inductively match up elements, obtaining an order-preserving bijection I’ll denote {c1d1,c2d2…}. (So c1 is one of the ai’s, d1 is one of the bi’s, and so on.) Begin by choosing c1 and d1 arbitrarily. Inductively for even n we let cn be the first unmatched ai and look for a suitable mate dn; for odd n we go in the other direction, letting dn be the first unmatched bi and looking for a suitable cn. How do we know what’s suitable? Well, in the case of even n, the previous ci’s (c1 to cn−1) have divided the a-ordering up into n intervals (including the “half-infinite” leftmost and rightmost intervals). Their counterparts d1 to dn−1 likewise divide up the b-ordering. Find out which a-interval cn falls into, and pick a dn in the corresponding b-interval. We can always do this because the b-ordering is dense and without endpoints.

(Historical side-note: I’d always assumed that Cantor came up with this argument, but it turns out that his proof of the theorem used a one-way argument, not the back-and-forth method! It turns out that the method was invented independently by E.V. Huntington and Felix Hausdorff. See Who invented Cantor’s back-and-forth argument?)

Logicians generalized the hell out of this method. We start by asking, what’s so special about countable DLOs? Turns out, they are saturated models for the theory of linear orderings. (Caveat: to state this properly, I’d have to make some noises about cardinalities.) Remember types: the 1-type of an element c of a structure M for some language L is “everything true about c“. We want to allow for parameters, so we expand L to LM by throwing in names for all the elements of M. Then the 1-type of c with parameters a1,…,akM is the set of all closed formulas φ(c,a1,…,ak) that hold in M. For DLOs, it turns out that we need to worry only about very simple formulas: conjunctions that tell us for each ai whether c is larger than, smaller than, or equal to ai. Every other fact about c, vis-a-vis the ai’s, can be deduced from this, using the theory of DLOs.

Let’s say now that M and N are two countable structures for a (countable) language L.  Suppose the following holds. 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. That’s all we need to do a back-and-forth between M and N, making them isomorphic!

Or at least if base case, n=0, holds. In that case the “0-types” are just Th(M) and Th(N). To get the induction ball rolling, M and N must be elementarily equivalent: MN. Which makes sense: if M and N are isomorphic, they are certainly elementarily equivalent.

All this leads to a bunch of results in classical model theory about isomorphisms for saturated structures. The result quoted above partakes of this cuisine, but with its own special flavor notes. On the one hand, we don’t have to fuss with cardinalities. On the other hand, we deal with recursive saturation, and we have to get the standard systems SSy(M) and SSy(N) into the act.

Whaddya think, good place for a break? (“Flavor notes” has made me hungry.) To be concluded next time.