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 Δ₀ formulas of L(PA). As we said last time, this means:

For every Δ₀ formula φ(x₁,…,x_h, y₁,…,y_n) and for every tuple of elements c₁,…,c_h in N and for every b, b₁,…,b_n, e₁,…,e_n∈B, if

c₁,…,c_h<b<b₁<…<b_n  and  c₁,…,c_h<b<e₁<…<e_n

then

N⊧φ(c₁,…,c_h, b₁,…,b_n)    ⇔    N⊧φ(c₁,…,c_h, e₁,…,e_n).

We call b the barrier, and the c_i’s the parameters. The b_i’s are arbitrary increasing sequences of elements of B, not necessarily consecutive in B={r₁, r₂, r₃,…}. Likewise the e_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₁, r₂, r₃,…}, we have r₁<r₂<r₃<… . 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₁<b₂<b₃, we can choose the parameter c=b₁−1, the barrier b=b₁, and r=b₂ or r=b₃. So we get f(b₁)=b₂ ⇔ f(b₁)=b₃.

But since b₂<b₃, 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₁<b₂,  f(b₁) ≠ b₂.

(That was the first place we implicitly assumed B had elements larger than b₂—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 Δ₀ formula, and the conclusion f(b₁)≠b₂ holds provided b₁ is greater than any parameters occurring in the Δ₀ definition of f. Otherwise we can’t use b₁ as the barrier. So:

(4) for any Δ₀ definable total function f(x), and any 0<b₁<b₂, with b₁ greater than any parameters appearing in the definition of f,  f(b₁) ≠ b₂.

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

For our next result: taking f(x) = m+x for any standard m, we get: for any 0<b₁<b₂, b₁+m ≠ b₂.

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

(5) if b₁>0, b₂−b₁ is nonstandard.

(I don’t know whether we need to know that, but it seems nice to know. And if b₁=0, I think we can get the same result in another way, or just drop b₁ 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 Δ₀—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₁>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₁<b₂, then b₂≥2b₁. Do you see how to get a contradiction from b₁<b₂<2b₁, 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₁<b₂<b₃ and set parameter c=b₁−1, barrier b=b₁, argument r=b₂ or b₃, and conclude f(b₁)>b₂ ⇔ f(b₁)>b₃.

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

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

Setting d := b₂−b₁, 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 and use b₁ as the barrier.)

But this reduces to b₂=r, which means, all B elements greater than b₁ are equal to b₂. Since that’s not possible, we now know option (b) holds: both sides of 2b₁>b₂ ⇔ 2b₁>b₃ are false, so b₁<b₂ ⇒ 2b₁<b₂, 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-definable f.

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

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

MW: Yes, assuming y=2^x is Δ₀. And it is! As Wong puts it (in §2.2 of his “Model Theory of PA” notes),

…with some coding, one can express y=2^x as a Σ₁-formula. With more dirty work, one can actually make this Δ₀.

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₂ r⌋ is the same as 2^d+1≤r ∧ 2^d+2>r, that’s also Δ₀.

BS: I’m glad to hear that y=2^x is Δ₀, 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^b₁ upper-bounded B, ⌊log₂ b₂⌋ would be at most b₁, so the parameter d would be less than b₁, as required. So the same argument as before would force all b₂ > b₁ to have the same ⌊log₂⌋ . 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₁<r₂<r₃<…} 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₂≥b₁², so M is closed under multiplication. Here’s the argument I had in mind.

PA proves that b₂=qb₁+r for some q and some r<b₁. If q<b₁, then we have a quantifier-free formula pinning down b₂, with parameters both less than b₁. Impossible. So q≥b₁, and b₂ = qb₁+r ≥ b₁².

You might want to note that q=⌊b₂/b₁⌋, for comparison with your ⌊log₂ 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