Nonstandard Models of Arithmetic 30

Prev TOC Next

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(ω^U)=Th(N), and with ω^U countable and recursively saturated. So set M=ω^U, 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 {a₁,a₂,…} and {b₁,b₂,…} be enumerations of the two orderings. We inductively match up elements, obtaining an order-preserving bijection I’ll denote {c₁↔d₁,c₂↔d₂…}. (So c₁ is one of the a_i’s, d₁ is one of the b_i’s, and so on.) Begin by choosing c₁ and d₁ arbitrarily. Inductively for even n we let c_n be the first unmatched a_i and look for a suitable mate d_n; for odd n we go in the other direction, letting d_n be the first unmatched b_i and looking for a suitable c_n. How do we know what’s suitable? Well, in the case of even n, the previous c_i’s (c₁ to c_n−1) have divided the a-ordering up into n intervals (including the “half-infinite” leftmost and rightmost intervals). Their counterparts d₁ to d_n−1 likewise divide up the b-ordering. Find out which a-interval c_n falls into, and pick a d_n 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 L_M by throwing in names for all the elements of M. Then the 1-type of c with parameters a₁,…,a_k∈M is the set of all closed formulas φ(c,a₁,…,a_k) 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 a_i whether c is larger than, smaller than, or equal to a_i. Every other fact about c, vis-a-vis the a_i’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 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. 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.

Prev TOC Next