**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 *M*≅*N*.

Thanks to the previous parts of the proof, we have a model *U* of *T* with SSy(ω* ^{U}*)=SSy(

*N*) and Th(ω

*)=Th(*

^{U}*N*), and with ω

*countable and recursively saturated. So set*

^{U}*M*=ω

*, and QED!*

^{U}(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 {*a*_{1},*a*_{2},…} and {*b*_{1},*b*_{2},…} be enumerations of the two orderings. We inductively match up elements, obtaining an order-preserving bijection I’ll denote {*c*_{1}↔*d*_{1},*c*_{2}↔*d*_{2}…}. (So *c*_{1}* *is one of the *a _{i}*’s,

*d*

_{1}is one of the

*b*’s, and so on.) Begin by choosing

_{i}*c*

_{1}and

*d*

_{1}arbitrarily. Inductively for even

*n*we let

*c*be the first unmatched

_{n}*a*and look for a suitable mate

_{i}*d*; for odd

_{n}*n*we go in the other direction, letting

*d*be the first unmatched

_{n}*b*and looking for a suitable

_{i}*c*. How do we know what’s suitable? Well, in the case of even

_{n}*n*, the previous

*c*’s (

_{i}*c*

_{1}to

*c*

_{n−1}) have divided the

*a-*ordering up into

*n*intervals (including the “half-infinite” leftmost and rightmost intervals). Their counterparts

*d*

_{1}to

*d*

_{n−1}likewise divide up the

*b-*ordering. Find out which

*a*-interval

*c*falls into, and pick a

_{n}*d*in the corresponding

_{n}*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 *L _{M}* by throwing in names for all the elements of

*M*. Then the 1-type of

*c*with parameters

*a*

_{1},…,

*a*∈

_{k}*M*is the set of all closed formulas φ(

*c*,

*a*

_{1},…,

*a*) that hold in

_{k}*M*. For DLOs, it turns out that we need to worry only about very simple formulas: conjunctions that tell us for each

*a*whether

_{i}*c*is larger than, smaller than, or equal to

*a*. Every other fact about

_{i}*c*, vis-a-vis the

*a*’s, can be deduced from this, using the theory of DLOs.

_{i}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 *a*_{1},…,*a _{n}*∈

*M*and corresponding elements

*b*

_{1},…,

*b*∈

_{n}*N*, if the (parameter-free)

*n*-types are the same:

{φ(*x*_{1},…,*x _{n}*)∈

*L*:

*M*⊧φ(

*a*

_{1},…,

*a*)} = {φ(

_{n}*x*

_{1},…,

*x*)∈

_{n}*L*:

*N*⊧φ(

*b*

_{1},…,

*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*) are the same:

_{i}{φ(*x*,*x*_{1},…,*x _{n}*)∈

*L*:

*M*⊧φ(

*a*,

*a*

_{1},…,

*a*)} = {φ(

_{n}*x,*

*x*

_{1},…,

*x*)∈

_{n}*L*:

*N*⊧φ(

*b*,

*b*

_{1},…,

*b*)}

_{n}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: *M*≡*N*. 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.