Non-standard Models of Arithmetic 8

JB: So, you were going to tell me a bit how questions about the universe of sets cast their shadows down on the world of Peano arithmetic.

MW: Yup. There are few ways to approach this. Mainly I want to get to the Paris-Harrington theorem, which Enayat name-checks.

First though I should do some table setting of my own. There’s a really succinct way to compare ZF with PA: PA = ZF − infinity!

Here’s what I mean. Remove the axiom of infinity from ZF. The minimal model of this is Vω, the set of all hereditarily finite sets. A set is hereditarily finite if it’s finite, and all of its elements are finite sets, and all of their elements are finite sets, and so on down.

To show that ZF − infinity (let’s call it ZF−∞) is “basically the same” as PA, you have to code things in both directions. We know how the integers are coded: von Neumann’s finite ordinals. (Logicians often just say “integers” when they really mean “non-negative integers”; does this drive number theorists crazy?)

JB: If any number theorists actually talked to logicians, it might.

(Just kidding: there are actually lots of cool interactions between number theory and logic, with ideas flowing both ways.)

MW: In the reverse direction, suppose we’ve already coded the all the elements of {a1,…,an} as integers {i1,…,in}. We just need a way to code finite sets of integers as single integers. Lots of choices here, say bitstrings, or using a product of primes:

{i1,…,in} ↔ pi1pin

(Here pi is the i-th prime, naturally.)

Coding between \mathbb{N} and Vω is just the appetizer. Next comes translating the formal statements between L(PA) (the language of PA) and L(ZF) (the language of ZF). This calls for another trick—something called Gödel’s lemma, which uses the Chinese remainder theorem in a clever way. (Turns out you need this just to show that the “i-th prime” function can be expressed in L(PA).) And after that the main course: showing that PA can prove all the (translated) axioms of ZF, and vice versa. Kaye devotes a chapter to spelling out some of the details, off-loading the rest to exercises.

The point of all this? Just that you can do finite combinatorics in Vω without much gnashing of teeth. The Paris-Harrington principle is a variant of the finite Ramsey theorem; the Paris-Harrington theorem says that the Paris-Harrington principle is unprovable in PA (assuming, of course, that PA is consistent!) People like to call this the first “natural” unprovable statement—“natural” because combinatorialists might give a darn, not just logicians.

JB: I understand Goodstein’s theorem a million times better than the Paris-Harrington principle, and I can easily see how the natural proof uses induction up to ε0, though I don’t know the Kirby-Paris proof that it’s unprovable in PA. I thought this came before the Paris-Harrington theorem?

MW: Goodstein proved his theorem way back in 1944. Kirby and Paris proved its unprovability (in PA) in 1982, in the paper that also introduced the Hydra game. Although I don’t know that you can rely on publication dates for who knew what when. Anyway, Goodstein, Hydra, and the Paris-Harrington principle hang out together like the Three Musketeers. Or the Four Horsemen of Unprovability, if you include Gentzen’s result about induction up to ε0, and how it’s the precise “proof strength” of PA.

Jan van Plato wrote a historical article with the delightful title Gödel, Gentzen, Goodstein: The Magic Sound of a G-String. He says:

Goodstein had no proof of the independence of his theorem from PA, but it is clear to a careful reader of his paper that he indeed was convinced of the said independence. … part of the reason for the early neglect of Goodstein’s theorem lies in a false modesty. … The same attitude is well displayed by Goodstein’s subservient acceptance of each and every comment and criticism of Bernays. The latter persuaded him to suppress the claims to independence from the final version, and one can only speculate what effect a clear-cut conjecture of independence could have had on future research.

Getting back to the Paris-Harrington theorem: the original proof used non-standard models of PA. (Kanamori and McAloon soon simplified it; the treatment in the recent book by Katz and Reimann is particularly easy to follow.) That’s the one I want to look at here.

But since you had such fun with ordinals here (and here and here), I better add that Ketonen and Solovay later gave a proof based on the ε0 stuff and the hierarchy of fast-growing functions. (The variation due to Loebl and Nešetřil is nice and short.) We should talk about this sometime! I wish I understood all the connections better. (Stillwell’s Roads to Infinity offers a nice entry point, though he does like to gloss over details.)

I figured you must have written about Ramsey’s theorem at some point, but I couldn’t find anything.

JB: No, I’ve never really understood Ramsey theory. More precisely, I never understood its appeal. So whenever I try to read about it, I become bored and quit. “In any party of six people either at least three of them are mutual strangers or at least three of them are mutual acquaintances.” I’m sure there’s something interesting about this. I just haven’t gotten interested in it.

MW:But you do know, right, it comes in finite and infinite flavors?

JB: Yes.

MW: Ramsey was doing logic when he discovered his most famous result: he solved a special case of Hilbert’s Entscheidungsproblem.

You can think of Ramsey’s theorem as a supercharged pigeonhole principle. If you color an infinite set of points with a finite number of colors, at least one color paints an infinite number of points. OK, now color instead the edges of the complete graph on an infinity of points. Then there’s an infinite subset of the points, such that the complete graph on that subset is monochromatic. That’s not so obvious! Next step: again start with an infinite set of points, but this time color all the triangles (unordered triples of points). Then there’s an infinite subset of points with all its triangles the same color. And so on.

For the finite version, we start with a large finite set of points, and look for a subset of a given size such that all its points, or edges, or triangles (etc.) have the same color. You’ll find it if the original set of points is sufficiently large. How large equals “sufficiently”? That depends on (a) the cardinality of the things you’re coloring (points, edges, triangles, etc.); (b) the number of colors; and (c) how big you want your monochromatic set to be.

Now here’s an interesting fact. The finite version of Ramsey’s theorem follows from the infinite one by a routine compactness argument. (Or you can use Kőnig’s infinity lemma.) Ramsey himself gave a direct inductive proof for both versions—so the finite version is a theorem of PA. Paris and Harrington made just a small tweak to the finite version. The compactness argument barely notices the change—the tweaked version (the Paris-Harrington principle) still follows from the infinite Ramsey theorem. But the direct inductive proof comes to a crashing halt!

ZF can prove the Paris-Harrington principle, an assertion purely about Vω, but ZF−∞ can’t! Does this count as the infinite casting its shadow on the finite?

(Hmmm, I’ve spent so much time table-setting that now it’s time to walk the dog. We’ll have to get to the (model-based) proof of the Paris-Harrington theorem in the next post.)

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 )

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.