Monthly Archives: May 2019

Simple Sets and the Recursion Theorem

These notes on Simple Sets are a grabbag about the simple sets of recursion theory. If you don’t know what those are, you probably are not interested, but the Wikipedia article is nice and short and gives the basics.

The last result uses the “shiny black box” (see below), which seems like cheating, but isn’t!

I wrote up the notes sometime in the 1980s based on two papers, and on a lecture by Michael Stob at MIT (reporting on joint work with Maas and Shore). They discuss effectively simple sets and promptly simple sets.

Continue reading

2 Comments

Filed under Logic

Why “atomic bomb” instead of “nuclear”?

Why do we (mostly) say atomic bomb instead of nuclear bomb, which is technically more correct? This was asked on the History of Science and Math stackexchange. Here’s my answer.

Continue reading

Leave a comment

Filed under History, Physics

Non-standard Models of Arithmetic 9

Prev TOC Next

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

Continue reading

6 Comments

Filed under Conversations, Peano Arithmetic

Non-standard Models of Arithmetic 8

Prev TOC Next

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!

Continue reading

11 Comments

Filed under Conversations, Peano Arithmetic

Non-standard Models of Arithmetic 7

Prev TOC Next

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

Continue reading

5 Comments

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.

Continue reading

Leave a comment

Filed under Logic

Non-standard Models of Arithmetic 6

Prev TOC Next

JB: It’s interesting to see how you deploy various philosophies of mathematics: Platonism, intuitionism, formalism, etc. For a long time I’ve been disgusted by how people set up battles between these, like Punch-and-Judy shows where little puppets whack each other, instead of trying to clarify what any of these philosophies might actually mean.

For example, some like to whack Platonism for its claim that numbers “really exist”, without investigating what it might mean for an abstraction—a Platonic form—to “really exist”. If you define “really exist” in such a way that abstractions don’t do this, that’s fine—but it doesn’t mean you’ve defeated Platonism, it merely means you’re committed to a different way of thinking and talking.

Continue reading

4 Comments

Filed under Conversations, Peano Arithmetic

Non-standard Models of Arithmetic 5

Prev TOC Next

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 \mathbb{N}“.

Continue reading

7 Comments

Filed under Conversations, Peano Arithmetic

Non-standard Models of Arithmetic 4

Prev TOC Next

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

Continue reading

1 Comment

Filed under Conversations, Peano Arithmetic

Non-standard Models of Arithmetic 3

Prev TOC Next

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

Continue reading

4 Comments

Filed under Conversations, Peano Arithmetic