# Nonstandard Models of Arithmetic 29

MW: We’re still going through Enayat’s proof of his Theorem 7:

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

We’ve already done step (1). We obtained a model U of whose ω is both an end-extension of N and elementarily equivalent to it: ωUeN and Th(ωU)=Th(N). Now it’s time for the next two steps:

1. Proposition 6 applies to ωU, so it’s recursively saturated.
2. Since ωUeN, their standard systems are the same: SSy(ωU)=SSy(N). The standard system of a nonstandard model of PA is the family of subsets of ℕ that can be coded by elements of the model.

(2) is like falling off a log. Prop 6 says that if the omega of a model of ZF is nonstandard, then it’s recursively saturated. U is a model T, which extends ZF. N is nonstandard (it’s recursively saturated), and ωUeN, so ωU is nonstandard. Kaboom! Done!

I like that this step uses the converse of Theorem 7 to help prove Theorem 7. (Technically Prop. 6 is stronger than the converse to Theorem 7, because the countability condition is dropped.) I can’t think of another case where you use the converse of a theorem in proving the theorem.

Step (3) is not hard, but perhaps I should first clear away some preliminaries. What do we mean by coded? We have several options. I prefer using bitstrings: if (say) [n]i stands for the i-th bit of n, regarded as a bitstring, then n codes {i : [n]i=1}. Kaye prefers to use the coding of arbitrary length sequences. He uses (n)i  to denote the i-th item in a sequence coded by n, using the Gödel β-function coding. Then he says that n codes {i : (n)i≠0}. These details don’t matter: the key is that both [n]i=1 and (n)i≠0 are Δ1 formulas. (As it happens, they are even Δ0. Δ1 is clear, since they’re both recursive, but Δ0 is not at all obvious.) Another property, also shared by the two formulas, will be important. I’ll use my preferred bitstrings below.

Claim: if M and N are models of PA, and MeN, then SSy(M)=SSy(N). One direction is really easy. Say mM codes S={i∈ℕ : M⊧[m]i=1}. Since MeN we have MΔ1N (see Topics 8). Thus M⊧[m]i=1 iff N⊧[m]i=1. So m codes the same subset of ℕ in both M and N, and so SSy(M)⊆SSy(N).

In the other direction, say nN codes S={i∈ℕ : N⊧[n]i=1}. We need to find an mM also coding S. Now, n represents a non-standard length bitstring, but we care only about the initial segment of “length” ℕ. All we need, then, is for m and n to agree as bitstrings up to some nonstandard position; a fortiori they will agree at each i-th position for i∈ℕ. But we have, as a theorem of PA, that the bitstring n can be truncated to any desired length:

k<length(n) ∃m (length(m)=k ∧ ∀i<k [m]i=[n]i)

(This is the additional important property.) Pick a nonstandard kM and truncate n to k bits, computing inside N. Call the result m. Now, m belongs to M because m<2k and MeN. Summing up, for all i<k, N⊧[n]i=1 iff N⊧[m]i=1 iff M⊧[m]i=1. Therefore any set coded in N is also coded in M, and SSy(N)⊆SSy(M).