Author Archives: John Baez

About John Baez

I'm a mathematical physicist. I'm making a big career shift: I've been working on n-categories and fundamental physics, but now I'm visiting the Centre for Quantum Technologies for two years, and I'm thinking about technology and the global ecological crisis. I'll probably keep thinking about the old stuff a bit, too. If you're a scientist or engineer interested in saving the planet, I hope you join the Azimuth Project. Visit it here: http://www.azimuthproject.org/ or else check out my blog: http://johncarlosbaez.wordpress.com/

Non-standard Models of Arithmetic 6

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.

Indeed, I’m so tired of these Punch-and-Judy shows that I run, not walk, whenever I hear one roll into town. I like your approach better, where you seem to treat these different philosophies of mathematics, not as mutually exclusive factual claims, but as different attitudes toward mathematics. We can shift among attitudes and see things in different ways.

But still, I’d rather dodge all direct engagement with philosophy in this conversation, since that’s not why I’m interested in models of Peano arithmetic. Or rather, my interest in models of Peano arithmetic is a highly sublimated form of my youthful interest in philosophy. Instead of trying to tackle hard questions like “do the natural numbers really exist, what are they, and how do we know things about them?” I find it easier and more fun to learn and prove theorems.

But I have an ulterior motive, which I might as well disclose: I want to soften up the concept of “the standard model” of Peano arithmetic. I want to push toward some theorems that say something like this: “what you think is the standard model, may be nonstandard for me.”

This is pretty heretical. We’ve all seen this picture where the standard model is the smallest possible model, that only has the numbers it “needs to have”, and any nonstandard model has extra “infinitely big” numbers, after all the “finite” ones, coming in patches that look like copies of \mathbb{Z}. So if your standard model looks nonstandard to me, it means some number that seems perfectly standard to you seems “infinitely big” to me. To me, it lies one of these patches that come after all the standard numbers. No matter how many 1’s I subtract from it, I’ll never get down to 0… as long as the number of 1’s is standard for me.

What if for really big numbers, it’s hard to tell if they’re standard or nonstandard?

This sounds crazy, I admit. But have you ever seriously played the game of trying to name the largest natural number you can? If you do, you’ll probably wind up using the busy beaver function Σ(n), which tells us the most 1’s that can be printed by an n-state 2-symbol Turing machine that eventually halts. This function grows faster than any computable function, and makes it easy to name immensely large numbers. For example we know

\Sigma(7) \ge 10^{10^{10^{10^{18705353}}}}

but this is probably a ridiculous underestimate. We know

\Sigma(12) \ge 3 \uparrow\uparrow\uparrow\uparrow 3

which means 3^{3^{3^{\dots}}}, where the tower of threes is very tall. How tall? It has 3^{3^{3^{\dots}}} threes in it, where this tower has 3^{3^{3}} = 7625597484987 threes in it.

So Σ(12) is fairly large, but the Busy Beaver function quickly gets much larger, and rockets into the mists of the unknowable. For example, Aaronson and Yedida showed that Σ(7918) can’t be computed in ZFC if ZFC together with a certain large cardinal axiom is consistent:

• Scott Aaronson, The 8000th Busy Beaver number eludes ZF set theory, May 3, 2016, blog post at Shtetl-Optimized on a paper by Scott Aaronson and Adam Yedidia.

Even the game of naming really large computable numbers leads us into Turing machines and large cardinal axioms! In a thread on the xkcd blog, Eliezer Yudkowsky won such a game using an I0 cardinal. For readers not familiar with these, I recommend Cantor’s Attic, which invites us to study large cardinals as follows:

Welcome to the upper attic, the transfinite realm of large cardinals, the higher infinite, carrying us upward from the merely inaccessible and indescribable to the subtle and endlessly extendible concepts beyond, towards the calamity of inconsistency.

I find it remarkable how the simple quest to name very large natural numbers brings us up into this lofty realm! It suggests that something funny is going on, something I haven’t fully fathomed.

“But come on, John,” you may respond. “Just because there are very big, mysterious natural numbers doesn’t mean that they aren’t standard”.

And indeed I have to admit that’s true. I see no evidence that these numbers are nonstandard, and indeed I can prove—using suspiciously powerful logical principles, like large cardinal axioms—that they are standard. But that’s why this paper excites me:

• Ali Enayat, Standard Models of Arithmetic.

It excites me because it relativizes the notion of “the standard model” of PA. It gives a precise sense in which two people with two versions of set theory can have different standard models. And it points out that assuming a large cardinal axiom can affect which models count as standard!

Anyway, these are my crazy thoughts. But instead of discussing them now (and I’m afraid they go a lot further), I’d much rather talk about mathematical logic, and especially the math surrounding Enayat’s paper.

MW: Sounds good! We can save the philosophy (or at least what I call philosophy) for another day.

1 Comment

Filed under Conversations, Peano arithmetic