Nonstandard Models of Arithmetic 32

Prev TOC Next
Previous Paris-Harrington post

[Ed. note: This post was essentially ready two years ago, but I got distracted with other matters. If you’re seeing this for the first time, or want to refresh your memory, posts 8 and 9 introduced the Paris-Harrington theorem. Posts 21 through 24 continued the discussion, in a dialog with Bruce Smith. MW]

MW: After that interlude with indicators, I think we’re ready to return to our main plotline: showing that M is a model of PA. Recall the setup: B⊆M⊆N, with N a model of PA, B a set of diagonal indiscernibles for Δ₀ formulas in N, and M the downward closure of B in N. So B is cofinal in M.

We showed already that M was an initial substructure of N, and that M satisfied all the axioms of PA except for the Induction Scheme. So that’s our topic for today.

First, it makes things nicer if we replace the Induction Scheme with the Least Number Principle (LNP). Informally, the LNP says that any nonempty definable set has a least element. Here’s the formal statement:

For any formula ψ(x,y₁,…,y_n) of L(PA), we have

∀y₁…∀y_n [ ∃x ψ(x,y₁,…,y_n) → ∃x ( ψ(x,y₁,…,y_n) ∧ ∀w<x ¬ψ(w,y₁,…,y_n) ) ]

Like Induction, this is a scheme, and not a single axiom. It’s a “five-finger exercise” to show that Induction for ψ follows from the LNP for ¬ψ, and that the LNP for ψ(x) follows from Induction for ∀y≤x¬ψ(y). (That’s with all the other axioms of PA assumed.)

BS: Right—if induction failed for ψ (say because it managed to “define a cut”), then the complement of the set it defined would be nonempty, but have no least element. But (as your formula says), to get a similar proof in the other direction, we need the complement of the “upward closure” of the set defined by ψ (not just of the set itself), since the set might have “gaps”, preventing its complement from satisfying the requirements for induction. (Example of such a set: the even nonstandard numbers.)

MW: Yes. One last bit of table-setting. At the end of post 21, we discussed how we need a transfer principle between M and N that’s weaker than ‘elementary extension‘, but strong enough to prove M⊧PA. We want the PHP to hold in N but not in M, so M≼N is too strong. On the other hand, we’d like to transfer the LNP from N to M. Finally, since N is an end extension of M (M⊆_eN), we have M≼_Δ0N.

BS: Ok—let’s proceed!

MW: Without further ado, here’s the transfer principle, which I’ll label (¤). Or rather, a special case:

M ⊧ ∀x ∃y δ(x,y,c)       ⇔       N ⊧ ∀x<b₁ ∃y<b₂ δ(x,y,c)         (¤)

where δ(x,y,c) is Δ₀, c∈M, and b₁ and b₂ are any two elements of B subject to the condition c<b<b₁<b₂ for some b∈B.

In the general case, we can have n alternating blocks of quantifiers, and the parameter c and the variables x, y,… can all be tuples. (Then means that every component of the tuple is less than b₁.) Compared with our special case, the general case calls for no new ideas, just more fiddling with notation.

BS: Ok—that looks promising, since I can see how it’s related to the properties of diagonal indiscernibles. Let’s see how far I can get in proving it, using hints from the recent Topic post.

First, suppose M ⊧ ∀x ∃y δ(x,y,c). We’d like to translate that to a statement about N, which means bounding x and y to restrict them to be “in M”. We can effectively do that like this (abusing notation slightly):

N ⊧ ∀b₁∈B ∀x<b₁ ∃(b₂∈B,b₂>b₁) ∃y<b₂ δ(x,y,c)

(I think we discussed something essentially identical to that transformation in a recent post.) That is not actually a formally meaningful statement, since I’m requiring b₁ and b₂ ∈ B, but B is not definable in N. Fortunately I can use the “definition of truth” for ∀ and ∃ to understand that what I really mean is this:

∀b₁∈B ∃(b₂∈B,b₂>b₁)  N ⊧ ∀x<b₁ ∃y<b₂ δ(x,y,c)

except for one problem—I swapped the order of ∀x<b₁ and ∃(b₂∈B,b₂>b₁). Does it matter? I suspect I can prove it doesn’t (and then continue in this vein, ultimately using indiscernibility), but maybe this is a good time to pause for feedback.

MW: All good points. When it comes to switching the quantifiers, that is a real problem—see the errata to p.180 of Katz and Reimann. There are a couple of ways around it. We’ll have to look at it closely when the time comes.

There are two ways to handle the logical issue that B is not definable in N. One is by expanding the language: add a new predicate letter B to L(PA), and interpret B(x) in both M and N as meaning x∈B. Or we could use turnstile jumping, as I called it in the Topics post. Like so:

     M ⊧ ∀x ∃y δ(x,y,c)     (1)
⇔ ∀p ∃q M ⊧ δ(p,q,c)     (2)
⇔ ∀b₁>b>c ∀p<b₁ ∃b₂>b₁ ∃q<b₂ M ⊧ δ(p,q,c)     (3)

I prefer to use the second approach here, although the other technique is good to know about. Just to reduce notation clutter, I like to treat b, b₁, b₂ etc. as variables that implicitly belong to B.

As for the quantifier “∀b₁>b>c”, here’s what I mean. The transfer principle (¤) is supposed to hold for any tuple c and barrier b∈B with c<b. So the quantifier is really “∀b₁>b”, and “b>c” is just informational, as a reminder. Alternately, just write it “∀b₁>b” and add “where b>c” afterwards.

I numbered the steps, so we can talk about them. (1)⇒(2) is turnstile jumping. (2)⇒(3) follows because B is cofinal in M, again using one of the quantifier tricks. Of course, we have several steps to go to justify (¤).

Your formula ∀b₁∃b₂>b₁N⊧∀x<b₁∃y<b₂δ(x,y,c) is on the right track, but you need to dot an i. Or maybe cross a t. Apart from switching quantifiers, as you noted, you also went from “M⊧” to “N⊧”. That is the next step:

⇔ ∀b₁>b>c ∀p<b₁ ∃b₂>b₁ ∃q<b₂ N ⊧ δ(p,q,c)     (4)

but we have to justify it.

BS: The “turnstile jumping” is exactly what I meant by “use the definition of truth for ∀ and ∃”—but I agree it’s helpful to spell out each step. As for going from “M⊧” to “N⊧”, I thought I justified that when I said “We’d like to translate that to a statement about N, which means bounding x and y to restrict them to be ‘in M’.” Should I spell that out more explicitly? I just meant that any quantification over all of M is equivalent to the same quantification over that part of N which is “upper-bounded by B” (i.e. less than something in B). (I think that’s exactly what you used to justify (2)⇒(3).)

But since I never did justify the quantifier switching, I’m happy to switch to your sequence of steps. To justify (3)⇒(4), we just observe that any p and q meeting the conditions (specifically p<b₁ and q<b₂) must be in M, and that all elements of M are covered that way.

MW: “Any quantification over all of M is equivalent to the same quantification over that part of N which is upper-bounded by B”—that’s nice. It explains both what we’re doing with the quantifiers ∀p ∃q, and why that rewriting is OK.

But we also need to know that M ⊧ δ(p,q,c) if and only if N ⊧ δ(p,q,c). That’s justified because δ(x,y,z) is, by hypothesis, a Δ₀ formula, and M≼_Δ0N because M⊆_eN, as mentioned above.

We haven’t yet switched quantifiers. Here’s what I had in mind for the next two steps. (I’ll also copy (4) to make them easier to compare.)

⇔ ∀b₁>b>c ∀p<b₁ ∃b₂>b₁ ∃q<b₂ N ⊧ δ(p,q,c)    (4)
⇔ ∀b₁>b>c ∀p<b₁ ∃b₂>b₁ N ⊧ ∃y<b₂ δ(p,y,c)    (5)
⇔ ∀b₁>b>c ∀p<b₁ ∀b₂>b₁ N ⊧ ∃y<b₂ δ(p,y,c)     (6)

(4)⇒(5) is just turnstile jumping, of course. For (5)⇒(6), we use indiscernibility, for the first time. Do you want me to say more, or do you want to think about it?

BS: It looks pretty straightforward. Thinking of ∃y<b₂ δ(p,y,c) as a predicate of b₂, its parameters are c and p, which are both < b₁, so we can take b₁ as the barrier. Indiscernibility then tells us the choice of b₂ doesn’t matter (provided b₂>b₁, true in both ∃b₂>b₁ and ∀b₂>b₁). The implicit “b₁ ∈ B” and “b₂ ∈ B” are both to the left of ⊧, so B not being definable in N also seems like a non-problem.

MW: Exactly right. Notice that even if we didn’t have the parameters c in the statement of (¤), we’d still have p as a parameter. So our version of indiscernibility must allow for parameters.

Here’s the rest of the argument:

⇔ ∀b₁>b>c ∀p<b₁ ∀b₂>b₁ N ⊧ ∃y<b₂ δ(p,y,c)     (6)
⇔ ∀b₁>b>c  ∀b₂>b₁ ∀p<b₁ N ⊧ ∃y<b₂ δ(p,y,c)     (7)
⇔ ∀b₁>b>c  ∀b₂>b₁ N ⊧ ∀x<b₁ ∃y<b₂ δ(x,y,c)     (8)
⇔ N ⊧ ∀x<b₁ ∃y<b₂ δ(x,y,c),   provided b,b₁,b₂∈B, c<b<b₁<b₂    (9)

(6)⇒(7) is just switching two universal quantifiers. (7)⇒(8) is turnstile jumping. And (8)⇒(9) uses indiscernibility again. We no longer explicitly quantify over b₁ and b₂, but the equivalence (8)⇔(9) holds for any b,b₁,b₂ satisfying the proviso. We have the predicate ∀x<b₁ ∃y<b₂ δ(x,y,c) as a Δ₀ predicate in b₁ and b₂, with parameters c, and b as the barrier. So that’s (¤).

BS: Great!

MW: Now that we have the transfer principle, let’s see how it shows that the LNP holds in M, and why it doesn’t show that the PHP holds in M.

Although for the PHP, we haven’t spelled out what that is.  So all we can do is say why the PHP might not transfer from N to M. I will say that the PHP has the form ∀a∀b∃h φ(a,b,h), where φ is a recursive (i.e., Δ₁) predicate.

Let’s start with the LNP. Suppose φ(u) is a predicate and M⊧∃uφ(u). Let’s say M⊧φ(d) for some d∈M. Also let’s say φ(u) has the form ∀x∃y δ(x,y,c,u), where δ is Δ₀ and c are parameters. So M⊧∀x∃y δ(x,y,c,d). We can treat d as an additional parameter. Applying the transfer principle, we choose b<b₁<b₂∈B with b>c,d, and we have

N ⊧ ∀x<b₁ ∃y<b₂ δ(x,y,c,d)

Let’s write φ°(u) for the predicate ∀x<b₁∃y<b₂δ(x,y,c,u). So N⊧φ°(d). Since the LNP holds in N, there is an e∈N which is the least element satisfying φ°(u). So e≤d, which means that e∈M. We apply (¤) to N⊧φ°(e) to get M⊧φ(e). (This is OK because b>e.) There cannot be an f∈M with f<e and M⊧φ(f), because then we could use (¤) again to conclude that N⊧φ°(f), and e wouldn’t be the least element in N satisfying φ°(u). So e is the least element satisfying φ(u) in M. QED

This argument doesn’t work for the PHP. Do you want to take a crack at that?

BS: Let’s see. If it did work, it would be trying to justify this conclusion:

M ⊧ ∀a∀b∃h φ(a,b,h)       ⇔       N ⊧ ∀a∀b∃h φ(a,b,h)         (10)

where φ is Δ₁ as you mentioned above. There is no evident upper limit on h, or on whatever bound variables occur inside φ, or even on a and b in the right-hand side. But the arguments you gave for the LNP, and for the transfer principle itself, both depended crucially on all bound variables being ultimately upper-limited by some element of B (or something lower). So I would not even know how to begin “trying to justify (10) in a similar way”.

Is it that simple, or is there a “closer call” (regarding the near-success of an attempt to justify it) that I don’t yet see?

MW: You nailed it!

We’re ready now for the final piece of the puzzle: what does the PHP say exactly, and how does it furnish us with diagonal indiscernables? But I think here is a good place to break.

Prev TOC Next
Previous Paris-Harrington post