Category Archives: Peano arithmetic

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!

Here’s what I mean. Remove the axiom of infinity from ZF. The minimal model of this is V_ω, the set of all hereditarily finite sets. A set is hereditarily finite if it’s finite, and all of its elements are finite sets, and all of their elements are finite sets, and so on down.

To show that ZF − infinity (let’s call it ZF^−∞) is “basically the same” as PA, you have to code things in both directions. We know how the integers are coded: von Neumann’s finite ordinals. (Logicians often just say “integers” when they really mean “non-negative integers”; does this drive number theorists crazy?)

JB: If any number theorists actually talked to logicians, it might.

(Just kidding: there are actually lots of cool interactions between number theory and logic, with ideas flowing both ways.)

MW: In the reverse direction, suppose we’ve already coded the all the elements of {a₁,…,a_n} as integers {i₁,…,i_n}. We just need a way to code finite sets of integers as single integers. Lots of choices here, say bitstrings, or using a product of primes:

{i₁,…,i_n} ↔ p_i1…p_in

(Here p_i is the i-th prime, naturally.)

Coding between and V_ω is just the appetizer. Next comes translating the formal statements between L(PA) (the language of PA) and L(ZF) (the language of ZF). This calls for another trick—something called Gödel’s lemma, which uses the Chinese remainder theorem in a clever way. (Turns out you need this just to show that the “i-th prime” function can be expressed in L(PA).) And after that the main course: showing that PA can prove all the (translated) axioms of ZF⁻, and vice versa. Kaye devotes a chapter to spelling out some of the details, off-loading the rest to exercises.

The point of all this? Just that you can do finite combinatorics in V_ω without much gnashing of teeth. The Paris-Harrington principle is a variant of the finite Ramsey theorem; the Paris-Harrington theorem says that the Paris-Harrington principle is unprovable in PA (assuming, of course, that PA is consistent!) People like to call this the first “natural” unprovable statement—“natural” because combinatorialists might give a darn, not just logicians.

JB: I understand Goodstein’s theorem a million times better than the Paris-Harrington principle, and I can easily see how the natural proof uses induction up to ε₀, though I don’t know the Kirby-Paris proof that it’s unprovable in PA. I thought this came before the Paris-Harrington theorem?

MW: Goodstein proved his theorem way back in 1944. Kirby and Paris proved its unprovability (in PA) in 1982, in the paper that also introduced the Hydra game. Although I don’t know that you can rely on publication dates for who knew what when. Anyway, Goodstein, Hydra, and the Paris-Harrington principle hang out together like the Three Musketeers. Or the Four Horsemen of Unprovability, if you include Gentzen’s result about induction up to ε₀, and how it’s the precise “proof strength” of PA.

Jan van Plato wrote a historical article with the delightful title Gödel, Gentzen, Goodstein: The Magic Sound of a G-String. He says:

Goodstein had no proof of the independence of his theorem from PA, but it is clear to a careful reader of his paper that he indeed was convinced of the said independence. … part of the reason for the early neglect of Goodstein’s theorem lies in a false modesty. … The same attitude is well displayed by Goodstein’s subservient acceptance of each and every comment and criticism of Bernays. The latter persuaded him to suppress the claims to independence from the final version, and one can only speculate what effect a clear-cut conjecture of independence could have had on future research.

Getting back to the Paris-Harrington theorem: the original proof used non-standard models of PA. (Kanamori and McAloon soon simplified it; the treatment in the recent book by Katz and Reimann is particularly easy to follow.) That’s the one I want to look at here.

But since you had such fun with ordinals here (and here and here), I better add that Ketonen and Solovay later gave a proof based on the ε₀ stuff and the hierarchy of fast-growing functions. (The variation due to Loebl and Nešetřil is nice and short.) We should talk about this sometime! I wish I understood all the connections better. (Stillwell’s Roads to Infinity offers a nice entry point, though he does like to gloss over details.)

I figured you must have written about Ramsey’s theorem at some point, but I couldn’t find anything.

JB: No, I’ve never really understood Ramsey theory. More precisely, I never understood its appeal. So whenever I try to read about it, I become bored and quit. “In any party of six people either at least three of them are mutual strangers or at least three of them are mutual acquaintances.” I’m sure there’s something interesting about this. I just haven’t gotten interested in it.

MW:But you do know, right, it comes in finite and infinite flavors?

JB: Yes.

MW: Ramsey was doing logic when he discovered his most famous result: he solved a special case of Hilbert’s Entscheidungsproblem.

You can think of Ramsey’s theorem as a supercharged pigeonhole principle. If you color an infinite set of points with a finite number of colors, at least one color paints an infinite number of points. OK, now color instead the edges of the complete graph on an infinity of points. Then there’s an infinite subset of the points, such that the complete graph on that subset is monochromatic. That’s not so obvious! Next step: again start with an infinite set of points, but this time color all the triangles (unordered triples of points). Then there’s an infinite subset of points with all its triangles the same color. And so on.

For the finite version, we start with a large finite set of points, and look for a subset of a given size such that all its points, or edges, or triangles (etc.) have the same color. You’ll find it if the original set of points is sufficiently large. How large equals “sufficiently”? That depends on (a) the cardinality of the things you’re coloring (points, edges, triangles, etc.); (b) the number of colors; and (c) how big you want your monochromatic set to be.

Now here’s an interesting fact. The finite version of Ramsey’s theorem follows from the infinite one by a routine compactness argument. (Or you can use Kőnig’s infinity lemma.) Ramsey himself gave a direct inductive proof for both versions—so the finite version is a theorem of PA. Paris and Harrington made just a small tweak to the finite version. The compactness argument barely notices the change—the tweaked version (the Paris-Harrington principle) still follows from the infinite Ramsey theorem. But the direct inductive proof comes to a crashing halt!

ZF can prove the Paris-Harrington principle, an assertion purely about V_ω, but ZF^−∞ can’t! Does this count as the infinite casting its shadow on the finite?

(Hmmm, I’ve spent so much time table-setting that now it’s time to walk the dog. We’ll have to get to the (model-based) proof of the Paris-Harrington theorem in the next post.)

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

Enayat leads off with what TV critics like to call table setting. Although some critics sniff contemptuously at this, table setting is an Excellent Thing in a math paper—I wish everyone did it as well as Enayat does here. For me, it’s instantly obvious why you’d care about which models of PA can be the “standard” in a model of ZF. But Enayat doesn’t take that for granted. He also explains why PA^ZF—statements that are true in all such models—is recursively axiomatizable.

Let’s get some terminology and notation out of the way first. Enayat doesn’t want to tie himself down to ZF in particular; you might want to add some other axioms, like AC, or Con(ZF), or SM, or some large cardinal axioms. So he uses T to stand for some recursively axiomatizable extension of ZF (maybe ZF itself).

JB: What’s “SM”?

MW: SM is “there exists a model of ZF whose universe is a set (not a proper class), and whose elementhood relation is the “real” one in the “real” universe.” This is the so-called Standard Model axiom. It’s implied by the weakest of all large cardinal axioms, the existence of an inaccessible cardinal.

JB: Okay, interesting. We category theorists use Grothendieck universes now and then, like when studying the “category of all small categories”. I believe the existence of a Grothendieck universe is equivalent to the existence of an inaccessible cardinal (or to be precise, a strongly inaccessible cardinal). It sounds like the existence of a Grothendieck universe is precisely the Standard Model axiom. I’ll check that out sometime. Anyway, go on.

MW: Nowadays, inaccessible pretty much always means strongly inaccessible. You’re right about Grothendieck universes: see Shulman’s paper Set Theory for Category Theory, §8.

If M is a model of T, Enayat says that is a T-standard model of PA. I used to call these “omegas”, since the domain of is the ω of the model M. Note that if M is a “standard” model (in the sense I just explained), then is just the standard .

JB: Hmmm. Though you say “just the standard ”, even under the assumptions you’re making, this seems to depend on T and on a choice of standard model M of T. Are you trying to tell me that it doesn’t really depend on either of these choices?

Since I’m trying to sift through all these dependencies, let me start by reminding myself, and everyone else, that we’re getting by first choosing a recursively axiomatizable extension T of ZF, and then choosing a model M of T. Then we define the natural numbers in the usual way in the theory T, and see what set, with successor operation and zero, it corresponds to in our model. That’s .

MW: Exactly. We get the same ω no matter which T and which M, so long as M is a standard transitive model. Set-theorists would say that’s because ω is absolute for standard transitive models. Let me unpack that.

A structure for ZF is a pair (K, ε), where K is a subclass of V (the “actual universe of all sets”), and ε is a binary relation on K (“elementhood”).  If ε is the “actual” elementhood relation , then we’ve got a so-called standard structure. So you get a standard structure just by looking at all the sets of V, and deciding which ones deserve to be in the club! is a standard model iff it satisfies all the ZF axioms, natch.

Now, the sets of K could still be deceiving us, even with a standard model. Say s belongs to K, but none of its elements do. Even though s has elements in the “real universe” V, s looks just like the empty set inside K. To ward off discombobulations of this ilk, we demand that K be transitive. This means that if s belongs to K, so do all of its “real world” elements (i.e., implies ), and so on down for elements of elements of s, etc.

Incidentally, the transitivity requirement for models of ZF is much like the initial segment requirement for models of PA. M is an initial segment of N (with models of PA) iff whenever , we have . In PA land, people tend to talk about end extensions: N is an end extension of M iff M is an initial segment of N. So I guess you could say that K is transitive iff V is an end extension of it. But set theorists don’t typically talk that way.

JB: Thanks! I need to learn a lot more about absoluteness. I get the basic idea, but I don’t know any of the theorems that say which things are absolute. This was borne in on me when at some point in Enayat’s paper he says “routine absoluteness considerations show…”. I thought “Hey, wait a minute!”

I guess it’s sort of obvious that concepts are more likely to be absolute when they don’t refer too much to the big wide world around them. But anyway, as Yogi Berra would say, we can burn that bridge when we get to it. Continue as you see fit!

MW: Good intuition. As I put it in my Smullyan notes, to verify that a set w is really ω, we just need to crawl around inside it. We don’t need to climb outside it and wander around the entire class K. Not so for the power set of ω, where we have to search high and low to make sure we’ve gathered all the subsets.

Logicians (specifically, Azriel Lévy) have developed a machinery to help determine absoluteness in set theory. Basically, peruse the quantifiers. If you hear the terms Δ₀, Δ₁, or Σ₁ being tossed around, that’s what’s going on.

As a side note, late in life Paul J. Cohen reminisced about his discovery of forcing. Here’s a bit of what he said about his first encounter with Gödel’s monograph on the consistency of AC and CH:

… it had an exaggerated emphasis on relatively minor points, in particular, the notion of absoluteness, which somehow seemed to be a new philosophical concept. From general impressions I had of the proof, there was a finality to it, an impression that somehow Gödel had mathematicized a philosophical concept, i.e., constructibility, and there seemed no possibility of doing this again…

But this is a bit of a detour for us, since Enayat’s paper concerns itself with the non-standard models of ZF.

“As above, so below.” (A quote from the Emerald Tablet of Hermes Trismegistus, a alchemical sacred text.)  seems so cozy and familiar; the “real universe” V by contrast an enormous, almost mythological mystery. Was Hermes right? Do the goings-on in the upper reaches of V leave their tell-tale traces in ?

Set theorists have known for quite some time that this holds for the second-order theory of (aka analysis). That’s a way-station between PA and ZF: you’re allowed to quantify over arbitrary subsets of ω, but not over subsets of the power set of ω.

The very first thing Cohen did with forcing was manufacture a model of ZF with a non-constructible set of integers—that is, a subset of ω that’s not in Gödel’s class L. But you can also get this from a large cardinal axiom. Silver and Solovay (independently) showed that if a specific so-called Ramsey cardinal exists, then so does a subset of ω with certain properties—properties precluding constructibility. Solovay dubbed this subset 0^#. (0^# would make a nice day-trip, maybe after we’ve talked about truth and satisfaction.)

In a way, Cohen’s result also made use of a large cardinal. He relied on axiom SM; perhaps the most natural justification for SM comes from assuming there’s an inaccessible cardinal. At the time, this met with some resistance from the community, so Cohen also showed how to convert his proof into a purely syntactic relative consistency argument. (Also you can circumvent SM in another way.)

What about the first-order theory PA? Now in a sense, anytime you assert anything about any recursively axiomatized theory, you’re stepping into PA’s jurisdiction. I don’t mean that PA will always be able to settle the question (prove or disprove it), just that it can be expressed in the language of PA. That’s what’s going on with Con(ZF), Con(ZFI), etc.

ZF makes its “gravitational field” felt in PA in other ways, too. Topic for the next post.

JB: Good! That’s one thing I really want to know about. I was going to mention that “as above, so below” quote from the Emerald Tablet when I first mentioned the ramifications of large cardinal axioms on arithmetic in Part 6. I decided it was too obscure! But I love the idea that the “microcosm” of the natural numbers may mirror the “macrocosm” of the set-theoretic universe. So let’s get into that!

MW: Too obscure!? Wasn’t it an Oprah Book Club Selection?

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

but this is probably a ridiculous underestimate. We know

which means , where the tower of threes is very tall. How tall? It has threes in it, where this tower has 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.

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

Maybe being nebulous isn’t so bad! It doesn’t wipe out your ontological creds. Look at that cloud over there:

HAMLET: Do you see yonder cloud that’s almost in shape of a camel?

POLONIUS: By the mass, and ’tis like a camel, indeed.

HAMLET: Methinks it is like a weasel.

POLONIUS: It is backed like a weasel.

HAMLET: Or like a whale?

POLONIUS: Very like a whale.

No one’s saying there’s no cloud. Or that you can only talk about the cloud if you do so in the language of ZF set theory!

JB: I don’t mind nebulous philosophy. But if you’re going to say “true arithmetic” and “the standard model ” in mathematical discourse, I think you need to define them. (That’s for the “hard core” of mathematical discourse, where one is stating theorems and conjectures, and proving them.  It’s fine, indeed essential, to say a lot of vaguer stuff while doing mathematics.)

Imagine this:

POLONIUS: Let G be a Lie group. If G is connected and simply connected, it’s determined up to isomorphism by its Lie algebra.

HAMLET: Sorry, could you remind me—what’s a “Lie group”?

POLONIUS: What?? Every mathematician worthy of the name has a clear intuitive concept of a Lie group! How can you possibly ask such a question?

MW: That reminds me of an incident from grad school. My friend Mark and I went to ask one of our favorite profs, Bert Walsh, something about Riemann surfaces. He began by saying, “Well, you take your Dolbeault complex…” At the time, neither Mark nor I knew a Dolbeault complex from a dollhouse. So Mark asked him, “What’s a Dolbeault complex?” To which Prof. Walsh replied, “Mark, it’s exactly what you think it is!”

Since this is a Philosophy-with-a-capital-P post, let me sling the jargon: do you mean that is nebulous epistemically, or ontologically?

Epistemology—what we know—sure that’s nebulous! There’s a heck of lot we don’t know about . Are there odd perfect numbers? An infinite number of prime pairs? The ABC conjecture! Even something like the Riemann ζ hypothesis can be “coded” into the language of arithmetic with a little work. (Or a lot of work, if you really mean “written” and not just “convince yourself it could be written”.)

But ontologically—are there lots of different ‘s, or just one? The very term “non-standard models of arithmetic” has a double-edged tinge to it. If there are non-standard models, then there must be a standard model!

You gave a sort-of justification for the phrase, “the standard model”, in post 4:

If I pick a set theory, say ZFC or whatever, I can prove in there that’s there’s an initial model of PA (one with a unique embedding in any other), and I’m happy to call that the “standard model of PA in ZFC”. Then I can talk about the theory consisting of all closed sentences in this model. All that’s fine with me.

But do we have to “pick a set theory, say ZFC or whatever”, to give the proof?

I said my philosophy of math was an incoherent mish-mash of intuitionism, formalism, and platonism. Let’s start with intuitionism. I think I read somewhere that the taproot of Brouwer’s philosophy (or maybe Poincaré’s) consists in this: mathematical intuition comes first, axioms later.

That’s all I’m taking from those guys. But it’s important. I’m betting you saw the proof that there is, up to isomorphism, only one model of Peano’s axioms, long before you learned about first-order theories and non-standard models and all that. (It’s basically in Dedekind’s famous essay, “Was sind und was sollen die Zahlen?”, paragraph 79.)

Of course, “Peano’s axioms” here isn’t the same as “PA”. The induction scheme is a single axiom quantifying over all subsets of , or as logicians like to say, it’s formulated in second-order arithmetic. (Or you can go all the way to ZFC, if you like.)

Here’s another way to put it: when you say, “pick a set theory”, I say, “OK, what if I pick the intuitive set theory of Dedekind and Cantor?”

I know what you’re thinking. “Has he totally forgotten about Russell’s paradox? Has he even studied axiomatic set theory? Does he really believe that has a single correct value, even if we may never know what it is?”

I’ll admit that oxygen can get a little scarce far up in V.  Do I believe that Woodin cardinals really exist? When the air becomes hard to breathe, I might want to take refuge in Hilbert’s gambit, and just claim it’s all a game with symbols. (*)(That’s my formalism ingredient. Again, a very small part of Hilbert’s program, but important.)

(*) Added later: I should have mentioned that Hilbert didn’t actually say this, and it’s a (common) misinterpretation of his program to summarize it this way. “We note at once that there is no evidence in Hilbert’s writings of the kind of formalist view suggested by Brouwer when he called Hilbert’s approach ‘formalism’.” —Kreisel, “Hilbert’s Programme”

The Hilbert gambit may be philosophically unimpeachable, but you know, it just isn’t that much fun! G. H. Hardy famously refused to accept that Hilbert really believed it. When watching Game of Thrones, do you tell yourself the whole time, “Those aren’t real dragons, they’re just CGI.”?

Let’s take the “existence” of non-standard models of PA in the first place. From a strictly formalist standpoint, we’d have to say: “here’s a proof in ZFC that “, where the ellipsis is a formalization of “N is a model of the PA axioms that is not isomorphic to ω”. Of course nobody does that. We carry out the proof that such beasties exist in an informal set theory, convinced (with good reason!) that it could (under duress) be turned into a ZFC proof.

And that’s the platonism part of my philosophy. The outermost layer will always be raw mathematical intuition. But when I’m swimming inside ZFC, it’s just easier, and more fun, to imagine that the ZF universe really exists. I pretend that the axioms are laws of this universe. The laws tell me there’s a unique ω, and (equipped with the usual paraphenalia), that’s what I mean by “the standard model”. Who knows, maybe it’s really true.

(Does The Matrix have any scenes of someone playing video games? Or Greg Egan’s Permutation City? Can’t remember.)

Now for the kicker. Say we  go with the Hilbert gambit. You need some raw intuition about the natural numbers just to make sense of it! Anyone who will swallow “well-formed formula” and “proof tree” as sufficiently clear concepts, but balks at “natural number”, has a strange perspective, IMO. The Hilbert gambit buys you something, philosophically, when we’re talking about full-bore set theory. Not so much with arithmetic.

Put it this way. You wrote:

for any sentence that’s not decidable in Peano Arithmetic, there are models where this sentence is satisfied and models where it’s not. In which camp does the standard model lie?…[By the Overspill Lemma] if our supposed “standard” model were actually nonstandard, we still couldn’t pick out the nonstandard numbers. The aliens could be among us, and we’d never know!

The results you appeal to (the Completeness Theorem and the Overspill Lemma) are themselves theorems of either ZFC, or of informal set theory. But so is the uniqueness (up to isomorphism) of . Why regard these results differently?

On the other hand, if you meant “nebulous” epistemically, well, just about all math is nebulous in that sense. There’s a lot we don’t know about—fill in the blank!

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

MW: Well, on second look, I see Enayat uses “ZF-standard” in the body of the paper. I’m fine with that.

Anyway, back when I was in grad school, I wondered whether there were models of true arithmetic that are not omegas. Answer: yes. I wrote up a short note, just for myself. I’m sure the result is well-known, maybe even in one of the three books we’ve mentioned. (Also, at this remove I no longer remember if I came up with the argument on my own, or if my advisor gets the credit.)

JB: What’s “true arithmetic”?

MW: Just the theory of the standard model, i.e., all closed formulas satisfied by . Now, if you don’t believe the term “the standard model” means anything, then I’d have to write a much longer and more confusing definition.

JB: What’s ? (Most of the time I act like I know, but when I’m doing logic I admit that there are lots of different things one could mean by it.)

I don’t think “the standard model” means anything unless it’s defined. So please give me your definition!

If I pick a set theory, say ZFC or whatever, I can prove in there that’s there’s an initial model of PA (one with a unique embedding in any other), and I’m happy to call that the “standard model of PA in ZFC”. Then I can talk about the theory consisting of all closed sentences in this model. All that’s fine with me.

MW: Hmmm… It looks like we’re not going to be able to avoid all philosophy. Fair warning: my philosophy of math is a mish-mash of intuitionism, formalism, and platonism. And I’m not using those terms in the usual way! But I think this is a topic for the next post. After that, I promise we’ll get back to Real Math.

[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 parleyed this line of thought into some real results and ultimately a thesis.

JB: Fun! It reminds me a bit of this:

I have seen some ultrafinitists go so far as to challenge the existence of 2¹⁰⁰ as a natural number, in the sense of there being a series of “points” of that length. There is the obvious “draw the line” objection, asking where in 2¹, 2², 2³,…, 2¹⁰⁰, do we stop having “Platonic reality”? Here this “…” is totally innocent, in that it can easily be replaced by 100 items (names) separated by commas. I raised just this objection with the (extreme) ultrafinitist Yessenin-Volpin during a lecture of his. He asked me to be more specific. I then proceeded to start with 2¹ and asked him if this was “real” or something to that effect. He virtually immediately said yes. Then I asked about 2² and he again said yes, but with a perceptible delay. Then 2³ and yes, but with more delay. This continued for a couple more times, till it was obvious how he was handling this objection. Sure, he was prepared to always answer yes, but he was going to take 2¹⁰⁰ times as long to answer yes to 2¹⁰⁰ as he would to answering 2¹. There is no way that I could get very far with this.

Harvey M. Friedman, “Philosophical Problems in Logic”

I had as rather distant acquaintances a couple of famous ultra-finitists, namely Alexander Yessenin-Volpin and Edward Nelson. I think they’re on to something but I think it’s quite hard to formalize.

Both of them were real characters. Yessenin-Volpin was a dissident in the Soviet Union, locked in a psychiatric hospital for what Vladimir Bukovsky jokingly called “pathological honesty”. Edward Nelson was another student of my Ph.D. advisor, Irving Segal. He did ground-breaking work on mathematically rigorous quantum field theory. Much later he wrote a fascinating paper on internal set theory, which I’d like to talk about sometime. In his final years he thought he had proved the inconsistency of Peano arithmetic! Terry Tao caught the mistake in the proof, and Nelson quickly admitted his error. That was an embarrassing incident, but he came out of it fine. Crackpots never admit they’re wrong; he was not like that!

JB: The only books I know on models of Peano arithmetic are Kaye’s Models of Peano Arithmetic and Kossack and Schmerl’s more demanding The Structure of Models of Peano Arithmetic, and I’m trying to read both. But I have a certain dream which is being aided and abetted by this paper:

• Ali Enayat, Standard Models of Arithmetic.

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

One first hint of this is the simple fact that for any sentence that’s not decidable in Peano Arithmetic, there are models where this sentence is satisfied and models where it’s not. In which camp does the standard model lie? We can only say: “one or the other”. And the same is true in any recursively enumerable consistent extension of PA. There are always undecidable sentences in any such extension, and there are always models—infinitely many, in fact—where the sentence is satisfied, and infinitely many where it is not!

So, choosing “the” standard model among all the pretenders—or even this lesser task: finding it up to elementary equivalence—is a herculean task, like finding ones way through an infinite labyrinth of branching paths, where at each branch deciding which way to go requires brand-new insights into mathematics, not captured by our existing axioms. I’m not convinced it makes sense to talk about the “right” decision in every case.

Another hint is the Overspill Lemma, used ubiquitously in the study of nonstandard models. Roughly:

Overspill Lemma: In a nonstandard model of Peano arithmetic, any predicate in the language of arithmetic that holds for infinitely many standard natural numbers also holds for infinitely many nonstandard ones.

Corollary: There is no way to write down a predicate in the language of arithmetic that singles out the standard natural numbers.

So, if our supposed “standard” model were actually nonstandard, we still couldn’t pick out the nonstandard numbers. The aliens could be among us, and we’d never know!

But you know all this stuff, and probably have different interpretations of what it means. I don’t mainly want to argue about that; I mainly want to learn more, so I can prove some interesting theorems.

So, thanks for your great introduction! I especially love the idea of types, which I just learned. Your explanation was great. Here’s more, in case anyone is reading:

• Types (model theory), Wikipedia.

You didn’t quite get to “recursively saturated models”, so I pestered Joel David Hamkins (a logician I know, now at Oxford) and got this nice explanation, which fits nicely with yours:

Dear John,

Saturation is about realizing types. The type of an element a in a model M is the set of all formulas such that M satisfies . You can allow parameters in a type. For example, if you consider the reals as an ordered field, then any two elements a and b have different types, since there is some rational between them, and a, say, will realize the formula , while b does not. This formula is expressible in the language of fields.

Does realize all types that it could? No, because you can write down a collection of formulas asserting that and . This is expressible in that language, and it is consistent with the diagram of the reals, meaning that this type could be realized in some elementary extension of . The type asserts that x is a positive infinitesimal number. So the reals are not saturated.

Indeed, since that type was very easy to describe, the reals are not even recursively saturated (I usually call it computably saturated). To be recursively saturated, a model M must realize every computable type (the formulas, as a set, are a computable set of formulas) that is consistent with its diagram.

In general, saturated models are very thick—they have lots of points of all the types that one could in principle have in a model of that theory. Usually, countable models are not saturated (except when the language is trivial in some way).  To get around this, the idea of recursive saturation works very well with countable models, and this is what is going on in Kaye’s book.

Hope this helps, and let me know if I can explain anything more about it…

Kind regards,

Joel

It’s so much easier to learn stuff by talking with people than by fighting through a thicket of logic symbols! But it’s also good for me to keep reading the books.