by | June 22, 2019 · 11:28 pm

First-Order Categorical Logic 3

Prev TOC Next

JB: Okay, let’s talk more about how to do first-order classical logic using some category theory. We’ve already got the scaffolding set up: we’re looking at functors

B:FinSet→BoolAlg.

You can think of B(S) as a set of predicates whose free variables are chosen from the set S. The fact that B is a functor captures our ability to substitute variables, or in other words rename them.

But now we want to get existential and universal quantifiers into the game. And we do this using a great idea of Lawvere: quantifiers are adjoints to substitution.

Continue reading →

1 Comment

Filed under Categories, Conversations, Logic

by | June 22, 2019 · 9:38 am

Non-standard Models of Arithmetic 11

Prev TOC Next

MW: Time to start on Enayat’s paper in earnest. First let’s review his notation. M is a model of T, a recursively axiomatizable extension of ZF. He writes \mathbb{N}^M for the ω of M equipped with addition and multiplication, defined in the usual way as operations on finite ordinals. So \mathbb{N}^M is what he calls a T-standard model of PA.

Continue reading →

4 Comments

Filed under Conversations, Peano Arithmetic

by | June 12, 2019 · 1:00 pm

Non-Standard Models of Arithmetic 10

Prev TOC Next

JB: So, last time you sketched the proof of the Paris–Harrington theorem. Your description is packed with interesting ideas, which will take me a long time to absorb. Someday I should ask some questions about them. But for now I’d like to revert to an earlier theme: how questions about the universe of sets cast their shadows down on the world of Peano arithmetic.

Continue reading →

1 Comment

Filed under Conversations, Peano Arithmetic

by | June 12, 2019 · 12:03 pm

First-Order Categorical Logic 2

Prev TOC Next

MW: So let’s see. Last time we talked about the functor B from the category FinSet to the category BoolAlg of boolean algebras. Liberal infusions of coffee convinced you that B is covariant; I accidentally suggested it was contravariant. I think I’ve come round to your position, but I still have a couple of things I want to say on the matter. If it won’t be too confusing for our readers.

JB: Okay.  If we’re planning to talk more about the variance, it’s probably good to start out by getting the reader a bit confused.  I used to always be confused about it myself.  Then I finally felt I had it all straightened out.  Then you shocked me by arguing that it worked the opposite way.  Your argument was very sneaky.

Continue reading →

2 Comments

Filed under Categories, Conversations, Logic

by | June 2, 2019 · 1:04 pm

First-Order Categorical Logic 1

TOC Next

(A conversation between John Baez and Michael Weiss.)

JB: Okay, maybe it’s a good time for me to unleash some of my crazy thoughts about logic. They’ve been refined a lot recently, thanks to all the education I’ve been getting from you and folks on the n-Category Café. So, I can actually start with stuff that’s not crazy at all… although it may seem crazy if you’re not used to it.

I’ll start with some generalities about first-order classical logic. (I don’t want to get into higher-order logic or intuitionistic logic here!) The first idea is this. In the traditional approach, syntax and semantics start out living in different worlds. In categorical logic, we merge those worlds.

Continue reading →

Leave a comment

Filed under Categories, Conversations, Logic

by | May 29, 2019 · 3:38 pm

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

by | May 28, 2019 · 6:38 pm

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

by | May 27, 2019 · 12:36 am

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

by | May 17, 2019 · 4:53 pm

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

by | May 17, 2019 · 4:00 pm

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 →

6 Comments

Filed under Conversations, Peano Arithmetic