MW: So we have our setup: B⊆M⊆N, with N a model of PA, B a set of “diagonal indiscernibles” (whatever those are) in N, and M the downward closure of B in N. So B is cofinal in M, and M is an initial segment of N. I think we’re not going to go over the proof line by line; instead, we’ll zero in on interesting aspects. Where do you want to start?
BS: Let’s start with how we’ll end up proving M is a model of PA. As we do that, maybe you’ll need to bring in more about B, and/or about using the PHP in N—but since my “real” interest is more general, it would be fine if it turns out the technique only depends on a few aspects of those!
MW: Sounds good! Well, there are three parts to showing that M is a model of PA. (1) M is closed under + and ·. (2) M satisfies all the axioms other than the induction axioms. (3) M satisfies the induction axioms.
Parts (1) and (3) use the properties of diagonal indiscernibles. Part (2) turns out to be the easiest: it uses just the fact that M is an initial segment closed under + and ·. Incidentally, an initial segment closed under successor is called a cut, but there doesn’t seem to be a standard term for one closed under + and ·. A supercut?
Part (1) uses the “growth properties” of B. Part (3) uses that transfer principle I talked about last time, without explaining what it was. And Part (2) uses a simpler transfer principle.
It might make sense to start with Part (2), just assuming Part (1). It’s a nice warm-up.
BS: Ok—whatever order you think is best. But it seems to me that given (1) and that M is an initial segment containing 1, (2) is trivial. Am I missing something?
MW: Nope, it is pretty easy. A warm-up, like I said. I just posted the PA axioms (two equivalent versions, in fact). If you peruse them, you’ll see that apart from the induction axioms, all but one are ∀1 formulas: a block of universal quantifiers followed by a quantifier-free predicate. ∀1 formulas are persistent downwards. So (aside from that exceptional axiom) that takes care of Part (2) in one fell swoop!
Nothing specific to PA here—this is a general fact of model theory. If A is a substructure of B, and 
Our first transfer principle, nice and easy. We need Part (1), by the way, because without it we don’t know that M is a substructure of N.
BS: In hindsight, it’s well worth seeing that spelled out—it’s straightforward, but not as trivial as I thought. I do see how to take care of the “holdout”:
∀x∀y ( x<y ↔ ∃w x+(w+1)=y )
We have to prove that if x + w + 1 = y, then w < y, to make sure w is in M. As easy as that is, I hadn’t explicitly noticed the need to prove it, until you pointed out how that axiom differs from the others.
MW: Right. The trick is to break it into two axioms:
∀x∀y ( x<y → ∃w x+(w+1)=y )
∀x∀y ( ∃w x+(w+1)=y → x<y )
Because P→Q is the same as ¬P∨Q, the second half is also ∀1. For the first half, we have the key fact that you noted: for x,y∈M, the w given by the axiom is less than y, so it also belongs to M.
So another transfer principle handles the axiom: Π1 downwards persistence. Namely: say we have two structures for L(PA), A and B, with A⊆B. Suppose also that A is an initial segment of B. Then Δ0 formulas are absolute between A and B: persistent both upwards and downwards. And Π1 formulas are persistent downwards. The initial segment requirement has paid off by making more formulas persistent.
Now, “∀x∀y(x<y → ∃w x+(w+1)=y)” is ∀2, aka ∀∃. We can’t apply any of these transfer principles to it. But it’s implied by this formula: “∀x∀y(x<y → ∃w<y x+(w+1)=y)”. That’s a Π1 formula. It holds in N, so it holds in M.
BS: That’s interesting! I guess it is worth reformulating as many axioms as possible into Π1 form, to make it clearer that they transfer this way.
MW: More generally, this shows the insights afforded by knowing where formulas land in the arithmetic hierarchy.
OK, let’s backtrack to Part (1)—showing that M is closed under + and ·. A couple of observations first. Suppose r1<r2<…<rn<… is an infinite increasing sequence of elements of N, and M is the downward closure of this sequence. If rn+1≥2rn for all n, then M is closed under addition. If rn+1≥rn2 for all n, then M is closed under multiplication.
BS: Because everything in M has to be under some rn! Clever!
MW: Now we need the definition of a set of diagonal indiscernibles in the model N for a set Φ of formulas. Here’s what I said in post 9:
For diagonal indiscernibles, the truth-value of φ(r1,…,rn,c1,…,ch) is the same no matter what the ri’s, provided that {r1,…,rn} is a subset of B, that r1<…<rn, and that all the ci’s are less than an indiscernible b which is less than all the ri’s. (Think of b as a kind of barrier—or DMZ.) And of course that φ belongs to the given set Φ of formulas—Δ0 formulas in this case.
BS: I’m not sure I understand that correctly—is the following reformulation equivalent?
Given φ and c1,…,ch, let b be minimal in B such that c1,…,ch<b. Then for every r1<…<rn all greater than b, φ(c1,…,ch, r1,…,rn) has the same truth value. (I.e., given those conditions, its truth value depends only on φ and c1,…,ch. BTW, I listed the ci’s first within φ, since I find it easier to understand that way.)
MW: I prefer not to assume that the barrier is minimal. It’s enough that it separates the parameters from the other indiscernibles. Let me try another phrasing. I’ll also change notation just a bit, for later convenience.
B⊆N is a set of diagonal indiscernibles for Φ in N, if the following holds. For every formula φ(x1,…,xh, y1,…,yn) in Φ and for every tuple of elements c1,…,ch in N and for every b,b1,…,bn,e1,…,en∈B, if
c1,…,ch<b<b1<…<bn and c1,…,ch<b<e1<…<en
then
N⊧φ(c1,…,ch, b1,…,bn) ⇔ N⊧φ(c1,…,ch, e1,…,en).
I call b the barrier, and everyone calls the ci’s the parameters. I’m using the bi’s and ei’s for arbitrary increasing sequences of indiscernibles, unlike the ri’s: they’re supposed to be all the indiscernibles, so B={r1, r2, r3,…}.
The numbers h and n will depend on the formula φ. Notice that the bi’s and the ei’s must be in increasing order, but the ci’s don’t have to be. As for the order of bi’s and ei’s with respect to each other, nothing is assumed about that.
BS: Ok, that’s clear. How does the barrier end up helping us?
MW: The key fact is that the barrier must belong to B; it turns out that any increasing sequence of diagonal indiscernibles grows at a very rapid clip. So having an element of B in between the ci’s on one side, and the bi’s and the ei’s on the other, means the two sides must be separated by a pretty big gap! If I may speak metaphorically, the bi’s and the ei’s are so far over the horizon of the ci’s, that the ci’s can’t distinguish between them—they’re indiscernible to the ci’s!
The role of the barrier may become clearer when we go through the proof that rn+1≥2rn and rn+1≥rn2 for all n.
BS: Ok, I’m looking forward to that! (I might even think I can guess something about it, but I’ll wait and see.)
Diagonal Argument 