**MW:** OK! So, we’re trying to show that *M*, the downward closure of *B* in *N*, is a structure for L(PA). In other words, *M* is closed under successor, plus, and times. I’m going to say, *M* is a *supercut* of *N*. The term *cut* means an initial segment closed under successor (although some authors use it just to mean initial segment).

**BS:** Wong uses the term *multiplicative cut*, since closure under multiplication implies the other two, at least if 2 belongs to the initial segment.

**MW:** Yup. On further thought, maybe *initial sub**structure* is the most descriptive, even though I like the ring of *supercut*.

Anyway, we’re given that *B* is a set of *diagonal indiscernibles* in *N* for the Δ_{0} formulas of L(PA). As we said last time, this means:

For every Δ

_{0}formula φ(x_{1},…,x_{h, }y_{1},…,y) and for every tuple of elements_{n}c_{1},…,cin_{h}Nand for everyb,b_{1},…,b,_{n}e_{1},…,e∈_{n}B, if

c_{1},…,c<_{h}b<b_{1}<…<band_{n}c_{1},…,c<_{h}b<e_{1}<…<e_{n}then

N⊧φ(c_{1},…,c,_{h}b_{1},…,b_{n}) ⇔N⊧φ(c_{1},…,c,_{h}e_{1},…,e_{n}).We call

bthebarrier, and thec_{i}’s theparameters. Theb_{i}’s are arbitrary increasing sequences of elements ofB, not necessarily consecutive inB={r_{1},r_{2},r_{3},…}. Likewise thee_{i}’s.

You said you had some ideas about how to prove that *M* is an initial substructure of *N*. Why don’t you give it a try?

**BS:** Will do!

First, if *B* has a maximal element, so will *M*, so *M* won’t even be closed under successor. (I mean, as seen from outside *N—*unless I say otherwise, I’m working entirely outside *N* here.) So in addition to the rules for *B* you just spelled out, we need it to have no maximum, which means it has an infinite number of elements.

**MW:** Yes, that’s right. I didn’t mention it above, but in *B*={*r*_{1}, *r*_{2}, *r*_{3},…}, we have *r*_{1}<*r*_{2}<*r*_{3}<… . So *B* has no maximum element.

**BS: **That makes things easier for the arguments I’m thinking of, since some of them only work if there are some “unused elements of *B*” beyond the ones we’re considering.

Another preliminary: each formula φ has its own *h* (number of “parameters” less than the barrier *b*) and *n* (number of “arguments” from *B*). If *n*=0, our condition on φ is trivial, so we can assume *n*>0.

Now for the first result: for any definable total function *f*(*x*), consider φ(*c*, *r*) := (*f*(*c*+1) = *r*).

Given any 0<*b*_{1}<*b*_{2}<*b*_{3}, we can choose the parameter *c*=*b*_{1}−1, the barrier *b*=*b*_{1}, and *r*=*b*_{2} or *r*=*b*_{3}. So we get *f*(*b*_{1})=*b*_{2} ⇔ *f*(*b*_{1})=*b*_{3}.

But since *b*_{2}<*b*_{3}, those can’t both be true, so they are both false. Thus, we obtain:

(4) for any definable total function *f*(*x*), and any 0<*b*_{1}<*b*_{2}, *f*(*b*_{1}) ≠ *b*_{2}.

(That was the first place we implicitly assumed *B* had elements larger than *b*_{2}*—*since it always does, I’ll stop pointing this out. I numbered this (4), since we still have subgoals (1)–(3) outstanding from Post 22.)

**MW: **Nice! Two points: *f*(*x*)=*y* has to be defined by a Δ_{0} formula, and the conclusion *f*(*b*_{1})≠*b*_{2} holds provided *b*_{1} is greater than any parameters occurring in the Δ_{0} definition of *f*. Otherwise we can’t use *b*_{1} as the barrier. So:

(4) for any Δ_{0} definable total function *f*(*x*), and any 0<*b*_{1}<*b*_{2}, with *b*_{1} greater than any parameters appearing in the definition of *f*, *f*(*b*_{1}) ≠ *b*_{2}.

**BS: **Good points! When I said “definable total function”, I meant “definable without parameters”, but I should have said that explicitly.

**MW:** Oh, we don’t need to be that restrictive. Usage isn’t uniform, but “definable” usually allows for parameters. People sometimes say “0-definable” if no parameters are allowed.

**BS:** Ok — but I’ll still try to make the parameters explicit, so we won’t forget to make sure they’re less than *b*_{1}.

For our next result: taking *f*(*x*) = *m*+*x* for any standard *m*, we get: for any 0<*b*_{1}<*b*_{2}, *b*_{1}+*m* ≠ *b*_{2}.

Since that holds for all standard *m*, we’ve shown:

(5) if *b*_{1}>0, *b*_{2}−*b*_{1} is nonstandard.

(I don’t know whether we need to know that, but it seems nice to know. And if *b*_{1}=0, I think we can get the same result in another way, or just drop *b*_{1} from *B* without harm.)

**MW:** Very good! It *is* nice to know. It’s an aspect of the “growth properties” of *B*. It means that each element of *B* is alone in its own “ℤ-patch”. We should revisit this when we see how to obtain a set of diagonal indiscernibles in the first place.

The formula *f*(*x*)=*m*+*x* is obviously Δ_{0}—in fact it’s quantifier-free! And we don’t need to make *m* a parameter, we can use a numeral for *m* instead: a term of the form 1+1+···+1.

Let’s just assume that *b*_{1}>0, “without loss of generality”, as math people like to say. In fact, let’s assume all elements of *B* are nonstandard—your argument shows that *B* can have at most one standard element.

Back to closure for addition*—*you need to prove that if *b*_{1}<*b*_{2}, then *b*_{2}≥2*b*_{1}. Do you see how to get a contradiction from *b*_{1}<*b*_{2}<2*b*_{1}, and diagonal indiscernibility?

**BS:** Hmm… not yet! Let me show you the argument I had in mind, and if it can be simplified, I’d like to hear about that.

So*—*now consider φ of the form

φ(*c*, *r*) := (*f*(*c*+1) > *r*)

Again we’ll choose *b*_{1}<*b*_{2}<*b*_{3} and set parameter *c*=*b*_{1}−1, barrier *b*=*b*_{1}, argument *r*=*b*_{2} or *b*_{3}, and conclude *f*(*b*_{1})>*b*_{2} ⇔ *f*(*b*_{1})>*b*_{3}.

This time, we can’t immediately rule out that they’re both true. But at least we’ve shown (for this function *f*):

for any *b*_{1}, either: (a) all of *B* is strictly upper bounded by *f*(*b*_{1}); or (b) none of *B* lies strictly between *b*_{1} and *f*(*b*_{1}) (assuming *f*(*b*_{1})>*b*_{1}).

Now take *f*(*x*) := 2*x*. Suppose option (a) holds. What would an upper bound like that imply? Certainly that whenever *b*_{2}>*b*_{1}, *b*_{2}−*b*_{1}<*b*_{1}. (Note that (4) rules out *b*_{2}=2*b*_{1}.)

Setting *d* := *b*_{2}−*b*_{1}, we’ll use it as a second parameter in yet another φ:

φ(*c*, *d*, *r*) := (*c*+1+*d* = *r*)

(We’ll continue to choose *c*=*b*_{1}−1 and use *b*_{1} as the barrier.)

But this reduces to *b*_{2}=*r*, which means, all *B* elements greater than *b*_{1} are equal to *b*_{2}. Since that’s not possible, we now know option (b) holds: both sides of 2*b*_{1}>*b*_{2} ⇔ 2*b*_{1}>*b*_{3} are false, so *b*_{1}<*b*_{2} ⇒ 2*b*_{1}<*b*_{2}, and *M* is closed under addition!

With a fancier φ, I can extend this to multiplication… but first, was that argument more complicated than necessary?

**MW:** Maybe. But you’re simultaneously proving stuff about any Δ_{0} 0-definable *f*.

Here’s what I had in mind. We want to show *b*_{2}≥2*b*_{1}. Well, *b*_{2}=(*b*_{1}−1)+(*b*_{2}−*b*_{1})+1=*c*+*d*+1, say. So we have a quantifier-free formula pinning down *b*_{2}, which can’t happen. So the parameters can’t both be less than the barrier *b*_{1}. Therefore *b*_{2}−*b*_{1}≥*b*_{1}, so *b*_{2}≥2*b*_{1}.

**BS: **That looks like a much more compact version of basically the same argument! Also, combined with your earlier hint, I *think* I see what you are going to suggest for multiplication… but I’ll still show you what I thought of earlier, and then you can show me the compact way to do it!

So… wait a minute… looking at my notes, it looks like instead of the required *b*_{2}≥*b*_{1}^{2}, I accidentally proved *b*_{2}≥2^{b1}. Oops!

But that is good enough, and still interesting—and it’s worth checking whether I got it right! This is what I did:

We’ll return to our previous φ(*c*, *r*) := (*f*(*c*+1) > *r*), and our conclusion that (for any *b*_{1}) either *f*(*b*_{1}) upper bounds all of *B*, or lower bounds all *b*_{2} above *b*_{1}. But this time, we’ll define *f*(*x*) = 2* ^{x}*. To rule out

*that*upper bound, we’ll use φ(

*d*,

*r*) := (

*d*+1 = ⌊log

_{2}

*r*⌋), that is,

*d*+1 is the greatest

*x*such that 2

*≤*

^{x}*r*. (That’s Δ

_{0}, since we can define it with bounded quantifiers.)

**MW:** Yes, assuming *y*=2* ^{x}* is Δ

_{0}. And it is! As Wong puts it (in §2.2 of his “Model Theory of PA” notes),

…with some coding, one can express

y=2as a Σ^{x}_{1}-formula. With more dirty work, one can actually make this Δ_{0}.

Somehow I’ve always meant to read the proof of this, but I never get around to it. Anyway, the paper by Gaifman and Dimitracopoulous contains the proof. Since *d*+1 = ⌊log_{2} *r*⌋ is the same as 2^{d}^{+1}≤*r *∧ 2^{d}^{+2}>*r*, that’s also Δ_{0}.

**BS:** I’m glad to hear that *y*=2* ^{x}* is Δ

_{0}, since I did rely on that, but I realized later that I don’t actually know how to prove it—I just vaguely recall reading it somewhere. So thanks for those refs—I’ll check them out.

Back to the argument: if 2^{b1} upper-bounded *B, *⌊log_{2} *b*_{2}⌋ would be at most *b*_{1}, so the parameter *d* would be less than *b*_{1}, as required. So the same argument as before would force all *b*_{2} > *b*_{1} to have the same ⌊log_{2}⌋ . But that would place them too close together—within a factor of 2 from each other, which we just ruled out a moment ago!

So we’ve proved *M* is closed under not only multiplication but exponentiation! (At least with a base of 2.) And I’m starting to think this kind of thing could be generalized even more…

**MW:** Sure thing. As I mentioned (without justification), the sequence *B*={*r*_{1}<*r*_{2}<*r*_{3}<…} grows at a *very* fast clip. We’ll revisit this later, when we talk about indicators.

But our immediate goal is more modest: showing that *b*_{2}≥*b*_{1}^{2}, so *M* is closed under multiplication. Here’s the argument I had in mind.

PA proves that* b*_{2}=*q**b*_{1}+*r* for some *q* and some *r*<*b*_{1}. If *q*<*b*_{1}, then we have a quantifier-free formula pinning down *b*_{2}, with parameters both less than *b*_{1}. Impossible. So *q*≥*b*_{1}, and *b*_{2} = *q**b*_{1}+*r* ≥ *b*_{1}^{2}.

You might want to note that *q*=⌊*b*_{2}*/**b*_{1}⌋, for comparison with your ⌊log_{2} *r*⌋.

Anyway, good place to take a break.

**BS:** That is indeed much simpler, and it makes the general pattern even more clear. I’m looking forward to hearing about indicators!