Nonstandard Models of Arithmetic 23

Prev TOC Next

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 substructure 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 φ(x1,…,xh, y1,…,yn) and for every tuple of elements c1,…,ch in N and for every b, b1,…,bn, e1,…,enB, if

c1,…,ch<b<b1<…<bn  and  c1,…,ch<b<e1<…<en


N⊧φ(c1,…,ch, b1,…,bn)    ⇔    N⊧φ(c1,…,ch, e1,…,en).

We call b the barrier, and the ci’s the parameters. The bi’s are arbitrary increasing sequences of elements of B, not necessarily consecutive in B={r1, r2, r3,…}. Likewise the ei’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={r1, r2, r3,…}, we have r1<r2<r3<… . 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<b1<b2<b3, we can choose the parameter c=b1−1, the barrier b=b1, and r=b2 or r=b3. So we get f(b1)=b2f(b1)=b3.

But since b2<b3, 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<b1<b2f(b1) ≠ b2.

(That was the first place we implicitly assumed B had elements larger than b2since 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(b1)≠b2 holds provided b1 is greater than any parameters occurring in the Δ0 definition of f. Otherwise we can’t use b1 as the barrier. So:

(4) for any Δ0 definable total function f(x), and any 0<b1<b2, with b1 greater than any parameters appearing in the definition of ff(b1) ≠ b2.

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 b1.

For our next result: taking f(x) = m+x for any standard m, we get: for any 0<b1<b2, b1+mb2.

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

(5) if b1>0, b2b1 is nonstandard.

(I don’t know whether we need to know that, but it seems nice to know. And if b1=0, I think we can get the same result in another way, or just drop b1 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 b1>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 additionyou need to prove that if b1<b2, then b2≥2b1. Do you see how to get a contradiction from b1<b2<2b1, 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.

Sonow consider φ of the form

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

Again we’ll choose b1<b2<b3 and set parameter c=b1−1, barrier b=b1, argument r=b2 or b3, and conclude f(b1)>b2f(b1)>b3.

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 b1, either: (a) all of B is strictly upper bounded by f(b1); or (b) none of B lies strictly between b1 and  f(b1) (assuming f(b1)>b1).

Now take f(x) := 2x. Suppose option (a) holds. What would an upper bound like that imply? Certainly that whenever b2>b1, b2b1<b1. (Note that (4) rules out b2=2b1.)

Setting d := b2b1, we’ll use it as a second parameter in yet another φ:

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

(We’ll continue to choose c=b1−1 and use b1 as the barrier.)

But this reduces to b2=r, which means, all B elements greater than b1 are equal to b2. Since that’s not possible, we now know option (b) holds: both sides of 2b1>b2 ⇔ 2b1>b3 are false, so b1<b2 ⇒ 2b1<b2, 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 b2≥2b1. Well, b2=(b1−1)+(b2b1)+1=c+d+1, say. So we have a quantifier-free formula pinning down b2, which can’t happen. So the parameters can’t both be less than the barrier b1. Therefore b2b1b1, so b2≥2b1.

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 b2b12, I accidentally proved b2≥2b1. 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 b1) either f(b1) upper bounds all of B, or lower bounds all b2 above b1. But this time, we’ll define f(x) = 2x. To rule out that upper bound, we’ll use φ(d, r) := (d+1 = ⌊log2 r⌋), that is, d+1 is the greatest x such that 2xr. (That’s Δ0, since we can define it with bounded quantifiers.)

MW: Yes, assuming y=2x 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=2x as a Σ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 = ⌊log2 r⌋ is the same as 2d+1r ∧ 2d+2>r, that’s also Δ0.

BS: I’m glad to hear that y=2x 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 2b1 upper-bounded B, ⌊log2 b2⌋ would be at most b1, so the parameter d would be less than b1, as required. So the same argument as before would force all b2 > b1 to have the same ⌊log2⌋ . 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={r1<r2<r3<…} 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 b2b12, so M is closed under multiplication. Here’s the argument I had in mind.

PA proves that b2=qb1+r for some q and some r<b1. If q<b1, then we have a quantifier-free formula pinning down b2, with parameters both less than b1. Impossible. So qb1, and b2 = qb1+rb12.

You might want to note that q=⌊b2/b1⌋, for comparison with your ⌊log2 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!

Prev TOC Next

Leave a comment

Filed under Conversations, Peano Arithmetic

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.