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.
Author Archives: Michael Weiss
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!
MW: Our goal for the next few posts is to understand Enayat’s paper
• Ali Enayat, Standard models of arithmetic.
MW: I’m going to take a leisurely approach, with “day trips” to nearby attractions (or Sehenswürdigkeiten, in the delightful German phrase), but still trying not to miss our return flight.
Also, I know you know a lot of this stuff. But unless we’re the only two reading this (in which case, why not just email?), I won’t worry about what you know. I’ll just pretend I’m explaining it to a younger version of myself—the one who often murmured, “Future MW, just what does this mean?”
Recursively enumerable (r.e.) sets are “semi-decidable”: if x belongs to an r.e. set W, then there’s a terminating computation proving that fact. But there may not be any way to verify that x does not belong to W. The founding theorem of recursion theory—the unsolvability of the Halting Problem—furnishes an r.e., non-recursive set. For this set, we have a program listing what’s in W, but no program listing what’s out.
[Reminder: JB=John Baez, MW=Michael Weiss.]
What you and Enayat are calling the “standard” model of arithmetic is what I used to call “an omega”, i.e., the omega of a model of ZF. Is that the new standard terminology for it? I don’t like it, for philosophical reasons I won’t get into. (Reminds me of the whole “interpretations of QM” that books have to skirt around, when they just want to shut up and calculate.)
Leaving ZF out of it, a friend in grad school used to go around arguing that 7 is non-standard. Try and give a proof that 7 is standard using fewer than seven symbols. And of course for any element of a non-standard model, there is a “proof” of non-standard length that the element is standard. I think he did this just to be provocative. Amusingly, he parlayed this line of thought into some real results and ultimately a thesis.