[In Post 21, Bruce Smith and I discuss the proof of the Paris-Harrington theorem.]
MW: Time to talk about the Paris-Harrington theorem. Originally I thought I’d give a “broad strokes” proof, but then I remembered what you once wrote: keep it fun, not a textbook. Anyway, Katz and Reimann do a nice job for someone who wants to dive into the details, without signing up for a full-bore grad course in model theory. So I’ll say a bit about the “cast of characters” (i.e., central ideas), and why I think they merit our attention.
The Paris-Harrington theorem says that the Paris-Harrington principle can’t be proved in PA. The principle is a small tweak to the finite Ramsey theorem. Let’s recall the Ramsey theorem, briefly. Begin with a finite set of points. Color the n-element subsets with a finite set of colors. A subset of the points is monochromatic if all its n-element subsets have the same color. The Ramsey theorem says we will always have a monochromatic set of points of any given size, no matter what n is or how many colors we use, provided we start with a sufficiently large set of points. “Sufficiently” depends, of course, on n and the number of colors and how large a monochromatic subset we insist on.
Ramsey first proved his theorem in a quest for indiscernibles—we’ll hear more about those shortly.
Now for the Paris-Harrington principle: let the points be numbers. Demand in addition that the size of the monochromatic subset be greater than its least element. (So if the smallest element is 5, we insist on at least 6 elements.)
Paris and Harrington gave two slightly different model-based arguments that their principle can’t be proved in PA. Approach 1: show that PA proves “(Paris-Harrington principle) implies Con(PA)”. So by Gödel’s incompleteness theorem, PA can’t prove the Paris-Harrington principle. Approach 2: show that there’s a model of PA + not-(Paris-Harrington principle). Any theory with a model is consistent, so QED.
I’ll concentrate on Approach 2. Before we get started, let me say just a bit about the model. Let N be a nonstandard model of PA. If N does not satisfy the Paris-Harrington principle, good, we’re done! Otherwise, we acquire (somehow!) an infinite set B of indiscernibles, a subset of N. Then we let M be the initial segment determined by B: all the elements of N that are less than some element of B. It turns out that M is a model of PA, but does not satisfy the Paris-Harrington principle. So now we know the role the indiscernibles play, even if we don’t know what they are yet.
Cast of characters:
- Types.
- Indiscernibles.
- Overspill.
- Truth and satisfaction.
- Δ0, bounded search, and absoluteness.
- Parameters, aka names.
Types. We talked about these in Posts 1 and 2. Or rather, we talked about complete n-types in a structure M, for an n-tuple of elements: all the formulas φ(x1,…,xn) that are satisfied (in M) by the tuple (r1,…,rn). Here we’ll be dealing with partial types—just some of the formulas.
Indiscernibles. If two elements have the same complete 1-type, then they’re “interchangeable”, identical twins, doppelgängers—much like two roots in an extension field with the same irreducible polynomial. Two n-tuples with the same complete n-type—same idea.
Because PA structures are linearly ordered by <, an n-tuple (r1,…,rn) has a different type from any of its permutations. (At least if they’re all distinct, which we’ll assume for technical reasons.) It makes more sense to work with unordered n-tuples, {r1,…,rn}. We’ll say its type is the type of the ordered n-tuple, when the elements are ordered lowest to highest. So r1<…<rn.
A set B of indiscernibles has the property that any two n-element subsets have the same type. So B is like the Borg: these dozen Borg are just like those dozen Borg. Or bosons. (Except I guess you can’t order Borgs, or bosons.)
That last paragraph was a little vague. To be more specific, if we have set Φ of formulas, then B is (order) indiscernible with respect to Φ if for every φ(x1,…,xn) in Φ, the truth-value of φ(r1,…,rn) is the same for all sets {r1,…,rn}, provided only that {r1,…,rn} is a subset of B and r1<…<rn.
How do we get ahold of indiscernibles? Let’s start with a single formula φ(x1,…,xn). If φ(r1,…,rn) is true, we color {r1,…,rn} blue, otherwise red. (Remember that r1<…<rn.) So we’re coloring n-element sets with 2 colors, and Ramsey’s theorem kicks in. With k formulas voicing their opinions, the true/false results give us 2k colors. So we can get an infinite set B that is indiscernible with respect to any finite number of formulas. Stay tuned—the indiscernibles have a couple more plot twists coming up.
Overspill. You talked about this in Post 2. In a way, it’s what inspired my friend David to ask, “What if seven is non-standard?”
And it’s how we leap over the hurdle of the last section. We’re going to need indiscernibility with respect to an infinite number of formulas. OK, use the finite Ramsey theorem for a non-standard number of formulas. If we set things up right, this will include all the standard formulas we care about.
For example, we could look at all formulas with Gödel numbers less than a non-standard c. What’s a formula with a non-standard Gödel number? It’s just a non-standard number satisfying a certain first-order formula, namely the one that encodes the assertion “n is the Gödel number of a well-formed formula”. In other words, we use the codability of syntax into PA. We already know that PA is “basically the same” as ZF¬∞; doing syntax “inside PA” is a trivial corollary.
So do we now have all the indiscernibles we need? First we have to clear another hurdle. Our definition of indiscernibles talked about truth-values. Not just syntax, also semantics. That opens Pandora’s box.
Truth and satisfaction. Before I get into this, I have to make two observations.
- Gödel’s two most famous results: the completeness theorem, and the incompleteness theorem.
- Tarski’s two most famous results: the undefinability of truth, and the definition of truth.
How neat is that? (Of course, you know that neither of these antitheses are really contradictory.)
I am also obligated, by virtue of having taken a course in Western Civilization in college, to include this quotation:
What is Truth?
Kaye does me one better. After citing Tarski’s undefinability theorem, he says:
(thus: we can’t get any satisfaction!)
I was disappointed not find an index entry for Mick Jagger.
Anyway, although the property “ℕ satisfies the closed formula φ” cannot be expressed in L(PA), one can express satisfaction for formulas of “bounded complexity”. Complexity can be bounded in various ways. Here, we need the satisfaction predicate for so-called Δ0 formulas. Kaye spells out the tedious details (for this and much more) in a chapter that leads off with the words, “This is the chapter that no one wanted to have to write…”
Δ0, bounded search, and absoluteness. OK. Let’s say N is a model of PA. We aim eventually to construct an initial segment M of N that will also be a model of PA. “As above, so below”: when does truth in M reflect truth in N?
To state a precise question: suppose φ(x1,…,xn) is a formula in L(PA), and (a1,…,an) is an n-tuple in M. When does φ(a1,…,an) have the same truth-value in M and N? This is the issue of absoluteness.
Here’s an important special case which guarantees absoluteness when M is an initial segment of N (as we have here): if all the quantifiers in φ are bounded—of the form ∀x<y or ∃x<y—then we say φ is Δ0. In that case, φ(a1,…,an) will be absolute between M and N for any n-tuple (a1,…,an) belonging to M.
We talked, briefly, about Δ0 formulas and absoluteness for ZF. There, the initial segment condition was called “transitivity”. A bounded quantifier looks like ∀x∈y or ∃x∈y. I said something like, with bounded quantifiers you can just crawl around inside the sets under discussion, you don’t have to search high and low through the whole universe.
Well, it’s pretty much the same with PA. If φ(x) is already absolute between M and N, then ∀x<y φ(x) is too. Note that the free variable in ∀x<y φ(x) is y, so we have to show that M and N give the same truth-value to ∀x<a φ(x) , for any a in M. But we’ve bounded the search to elements of M! So what’s going on in the rest of N can’t make a difference.
So here’s how the construction almost goes. Using the tricks already mentioned, acquire a subset B of N that is indiscernible for all standard Δ0 formulas. Let M be the set of all elements of N that are less than some element of B. Why should we think that M might be a model of PA?
The heart of the matter: the Least Number Principle for M. That’s just induction in a fancy costume. Let’s say we have a formula φ(x); the Least Number Principle says that if there’s any a making φ(a) true, then there’s a least such a. As it happens, you can replace the Induction Axioms with the Least Number Principle: the Induction Axiom for ¬φ(x) implies the Least Number Principle for φ(x), and vice versa. Proving that M satisfies the Least Number Principle for all φ(x) is the core of proving that M is a model of PA. (It’s not the whole story; for one thing, you have to show that M is closed under addition and multiplication. I’ll leave that and the other axioms of PA for the textbooks, or another time.)
If φ(x) is Δ0, just say “absoluteness!” and you’re done. This is why: suppose there’s some a in M making φ(a) true, in M. By absoluteness, this same a makes φ(a) true in N. Since the Least Number Principle holds in N, there’s a least such a in N, which of course is no greater than the a in M we started with. Well, M is an initial segment of N, so this “least such a” is also in M, and it’s the least a making φ(a) true in M, again by absoluteness.
But what if φ(x) is more complicated? For example, ∀y∃z ψ(x,y,z)? (Assume ψ(x,y,z) is Δ0.)
The trick is to use the indiscernibles in B to bound the searches. B is unbounded in M (or to sling the lingo, cofinal). Instead of saying ∀y∃z…, we can say
∀b1 ∀y<b1 ∃b2>b1 ∃z<b2…
with b1, b2 in B. Take a moment to see why: if there’s a z, there’s a b2 greater than that z. Likewise, looking at all the y’s amounts to the same thing as looking at all pairs y<b1.
Now we use the indiscernibility of the b’s. I like to think of the indiscernibles as the “sliders” in this picture:
……y……..←b1→……………………………z…………←b2→………….
Not that you literally slide b1 and b2 left and right, but you can choose any two bi and bj with bi<bj to replace them.
So we can just pick two specific b’s, and not quantify over them at all!
In a little more detail (but not getting into all the nitty-gritties), we’ve assumed that ψ(x,y,z) is Δ0, and that the bi’s are indiscernible for Δ0 formulas. So the truth-value of ∀y<b1 ∃z<b2 ψ(x,y,z) stays the same as we slide b1 and b2 around. If the truth-value of a proposition doesn’t depend on a parameter, then quantifying on that parameter can’t change anything. If everyone in a class has the same hair color, then the propositions “∃x in the class(x has red hair)”, “∀x in the class(x has red hair)”, and “Saoirse has red hair”—these all have the same truth value (assuming Saoirse is in the class). Every element is representative. (Caveat: I am glossing over some subtleties here, regarding the alternation of quantifiers.)
We end up with this:
∀y<b1 ∃z<b2ψ(x,y,z)
That’s a Δ0 formula, so we cry “absoluteness!” and go home. (Since we’ve already shown that the Least Number Principle holds for Δ0 formulas, and we’ve just seen that ∀y ∃z ψ(x,y,z) is equivalent to a Δ0 formula.)
Perhaps you smell a rat. I’ve gotten all this way, without using the Paris-Harrington principle. Not just that: the whole idea was that even if N satisfied the Paris-Harrington principle, M wouldn’t. So far I’ve been giving reasons why M should reflect N. But the denouement depends on M not reflecting N in one crucial aspect. Time for the final plot twist.
Parameters, aka names. I’ve pulled a fast one. When I talked about a formula φ(x1,…,xn), I ignored the possibility that it might contain some constants as well as the variables x1 to xn. Let’s say we have some constants c1,…,ch. So φ really looks like this: φ(x1,…,xn,c1,…,ch).
Typically, when one talks about n-types, one permits constants. Not only that, but one usually enriches the language to include a constant for every element of the domain of the structure. People often call these sort of constants names, and when used in a formula, parameters. (You may recall that when your friend Joel David Hamkins gave a précis of ‘type in a model’ in Post 2, he allowed for parameters.)
You might have noticed I’ve already used parameters. When I rewrote ∀y∃z… as (∀y<b1)(∃z<b2)…, b1, b2 are parameters. Also, parameters are permitted in the induction axioms. That means that the argument I just gave doesn’t quite work. We need to strengthen our indiscernibles to so-called diagonal indiscernibles. And to obtain these, we need the Paris-Harrington principle—the plain old Ramsey theorem just won’t cut it.
For diagonal indiscernibles, the truth-value of φ(r1,…,rn,c1,…,ch) is the same no matter what the r’s, provided that {r1,…,rn} is a subset of B, that r1<…<rn, and that all the c’s are less than an indiscernible b which is less than all the r’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.
With the new requirement (all the c’s less than b less than all the r’s) the proof that M is a model of PA goes through without a hitch. The Paris-Harrington principle also has a new requirement: the number of indiscernibles must be greater than the least indiscernible. You can sort of see that the two requirements might be related. But I won’t lie: an intricate trusswork of combinatorics forms the bridge between the two demands.
Time to wrap things up. Say N is a non-standard model of PA satisfying the Paris-Harrington principle. Putting all the characters above into the same scene, they conjure up a new character—a nonstandard number w. This w is a “witness” to the Paris-Harrington principle; that is, the set of numbers less than w is sufficiently large to contain the indiscernibles we need, guaranteed! Not only that, w is the least such witness. And these indiscernibles call forth the model M. (Some parameters play a role, but I’m just giving the sense of the plot.) Most important: all elements of M are less than w. (Just review how we went from w to indiscernibles to M.)
Does M satisfy the Paris-Harrington principle? Nope—if it did, it would have its own w0, the least witness to the Paris-Harrington principle! And w0 would be strictly less than w. But an absoluteness argument shows that “the least witness to the Paris-Harrington principle” must describe the same number in both M and N. So M is a model of PA + not-(Paris-Harrington principle), and we can ring down the curtain.
[In Post 21, Bruce Smith and I discuss the proof of the Paris-Harrington theorem.]
Diagonal Argument 
Pingback: Nonstandard Models of Arithmetic | Azimuth
The formula where you introduce the indiscernibles has a mismatched tag, which breaks the formatting of the rest of the page.
Thanks!
Let’s see if I understand the logic there:
So far, so good. But this seems to also imply:
But if that’s correct, why does Wikipedia say PHP is true? (It goes on to say how it can be proven.)
That is, what is the sense in calling it true, if it’s not merely unprovable, but false (though presumably also not disprovable), in the standard model of PA?
Ah, good point! The answer is very simple: I should have phrased things correctly. I should have said, “Let N be a nonstandard model of PA”. And the post now does say that. The PHP is “true”, or at least provable in ZFC set theory, for the “standard model” of PA.
(Unfortunately, you will find that I often commit this sort of unforced error. Caveat lector! Luckily I have some readers, such as yourself, to spot the goofs. Your comment inspired me to re-proofread the entire post, turning up several more infelicities (now fixed). End mea culpa.)
I first use the assumption that N is nonstandard in the Overspill section.
Thanks for explaining that crucial point — my understanding is now able to move forward and encounter a few more things I don’t understand!
For some of them, I might wait til I read a fully detailed exposition… but I’ll ask the most basic one here.
You ask “Why should we think that M might be a model of PA?”, and then go on to say some interesting things about comparing certain formulas’ truth values in N and M, as if this would supply an answer, but without spelling out how it might answer that.
I can see how it might be related, but not enough to fill in the details; and thinking more, it seems like overkill for the question asked. [Except for one thing I just noticed before posting — see below — but this then leaves my original question, “how does it actually work”.]
Specifically:
By construction, M is an “initial segment” of N (in the sense of being “closed downwards” — that is, x < y and y in M implies x in M). If we also assume M contains 0, 1, and 2, I think this means the only PA axiom we still need to check is closure of M under multiplication: that is, for all x, for all y, there exists z such that x * y = z.
(Since using the presence of 0, 1, and 2, we can prove closure of multiplication implies closure of addition and of successor. The other axioms seem obvious to me, including induction [but on second thought, see below]. In thinking these things, I’m assuming various simple formulas are “absolute”, since that also seems obvious.)
Am I wrong about this, or did you have some additional reason to want M to be “similar to N” in more ways that just being a model of PA?
Thinking a bit more, I got a bit uncomfortable about induction, in case the involved predicate has an unbounded existential quantifier. Is that the issue that forces you to consider more formulas?
[Bruce and I went on to discuss these issues in Post 21. –MW]