Non-standard Models of Arithmetic 9

Prev TOC Next

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 argument 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 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 “\mathbb{N} 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: if all the quantifiers in φ are bounded—of the form \forall x\!<\!y or \exists 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. That is, if M is an initial segment of N!

We talked, briefly, about Δ0 formulas and absoluteness for ZF. There, the initial segment condition was called “transitivity”. A bounded quantifier looks like \forall x\!\in\! y or \exists x\!\in\! 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 (\forall x\!<\!\!y)\varphi(x) is too. Note that the free variable in (\forall x\!\!<\!\!y)\varphi(x) is y, so we have to show that M and N give the same truth-value to (\forall x\!<\!a)\varphi(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.

If φ(x) is Δ0, just say “absoluteness!” and you’re done. 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, \forall y\exists z\,\psi(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 \forall y\exists z\ldots, we can say

(\forall b_1)(\forall y < b_1)(\exists b_2 > b_1)(\exists z < b_2)\ldots

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:

……x……..←b1→……………………………y…………←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! We end up with this:

(\forall y<b_1)(\exists z<b_2)\ldots

That’s a Δ0 formula, so we cry “absoluteness!” and go home.

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 \forall y\exists z\ldots as (\forall y<b_1)(\exists z<b_2)\ldots, 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 we’ll need the Paris-Harrington principle to get these—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 all the r‘s. (And of course that φ belongs to the given set Φ of formula—Δ0 formulas in this case.)

With the new requirement (all the c‘s less than all the r‘s) the proof that M is 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 conditions 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.

Prev TOC Next

3 Comments

Filed under Conversations, Peano arithmetic

3 responses to “Non-standard Models of Arithmetic 9

  1. Pingback: Nonstandard Models of Arithmetic | Azimuth

  2. g

    The formula where you introduce the indiscernibles has a mismatched tag, which breaks the formatting of the rest of the page.

Leave a Reply to Michael Weiss Cancel reply

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

WordPress.com Logo

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

Google photo

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

Twitter picture

You are commenting using your Twitter 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.