**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

## Non-standard Models of Arithmetic 9

Filed under Conversations, Peano arithmetic

## 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!

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 7

**MW:** Our goal for the next few posts is to understand Enayat’s paper

• Ali Enayat, Standard models of arithmetic.

**JB:** Yee-hah!

**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?”

Filed under Conversations, Peano arithmetic

## Friedberg’s Enumeration without Duplication

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*.

Filed under Logic

## Non-standard Models of Arithmetic 5

**MW:** John, you wrote:

Roughly, my dream is to show that “the” standard model is a much more nebulous notion than many seem to believe.

and you gave a good elucidation in post 2 and post 4. But I’d like to defend my right to “true arithmetic” and “the standard model “.

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 4

**MW: **I wrote: “I don’t like calling the omega of a model of ZF a *standard model*, for philosophical reasons I won’t get into.”

**JB:** I like it, because I don’t like the idea of “the” standard model of arithmetic, so I’m happy to see that “the” turned into an “a”.

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 3

[Reminder: JB=John Baez, MW=Michael Weiss.]

**MW:** Besides Kaye and Kossak & Schmerl., I should mention the book by Hájek and Pudlák, but I don’t have a copy of that. Thanks muchly for the Enayat paper, which looks fascinating.

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.

Filed under Conversations, Peano arithmetic