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

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” \mathbb{N} in a model of ZF. But Enayat doesn’t take that for granted. He also explains why PAZF—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 \mathbb{N}^M is a T-standard model of PA. I used to call these “omegas”, since the domain of \mathbb{N}^M is the ω of the model M. Note that if M is a “standard” model (in the sense I just explained), then \mathbb{N}^M is just the standard \mathbb{N}.

JB: Hmmm. Though you say “just the standard \mathbb{N}”, even under the assumptions you’re making, this \mathbb{N}^M 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 \mathbb{N}^M 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 \mathbb{N}^M.

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 \in, 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! (K,\in) 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., x\in s\in K implies x\in K), 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. If M and N are models of PA, we say M is an initial segment of N iff MN and whenever n<mM we have nM. 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 Δ0, Δ1, or Σ1 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.) \mathbb{N} 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 \mathbb{N}?

Set theorists have known for quite some time that this holds for the second-order theory of \mathbb{N} (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?

[This post and the next one acquired a long comment thread, mainly between Bruce Smith and John Baez. It was difficult to follow in that format, so I have converted it to a separate webpage. Topics: (a) Why do standard models of ZF have standard ω’s? (b) Interactions between the Axiom of Infinity Axiom and the Foundation Axiom (aka Regularity). (c) The compactness theorem. (d) The correspondence between PA and “ZF with infinity negated”: nonstandard numbers vs. ill-founded sets, and the Kaye-Wong paper (cited in the next post). –MW]

Prev TOC Next


Filed under Conversations, Peano Arithmetic

6 responses to “Non-standard Models of Arithmetic 7

  1. There must be something wrong in this:

    M is an initial segment of N (with models of PA) iff whenever m < nN, we have mN

    because the definition never mentions M. Also I’m not sure I understand what you meant by the parenthetical comment “(with models of PA)”.

    Let me guess a corrected definition: “M is an initial segment of N, iff: M is a subset of N, and whenever mM, and nN, and n < m, we have nM.” (But this leaves out the parenthetical comment.)

  2. (I now guess that by “(with models of PA)” you meant “(this definition is for when we are talking about models of PA)”. That’s why we can say “n < m” as if it means something.)

    • Yes. I’m going to take the liberty of change Michael’s sentence to something a bit more precise, if perhaps also more plodding:

      If M and N are models of PA, we say M is an initial segment of N iff MN and whenever n<mM we have nM.

  3. A long comment thread, mainly between Bruce Smith and John Baez, has been converted to a separate webpage.

  4. Nice posst thanks for sharing

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.