Category Archives: Peano arithmetic

Nonstandard Arithmetic: A Long Comment Thread

TOC Post 7 Post 8

Posts 7 and 8 developed an extensive comment thread, mainly between Bruce Smith and John Baez. It was hard to follow in that format, so I converted it to a separate webpage.

Topics: (a) Why do standard models of ZF have standard ω’s? (b) Interactions between the 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 post 8).

TOC Post 7 Post 8

Leave a comment

Filed under Conversations, Peano arithmetic

Topics in Nonstandard Arithmetic 1: Table Setting

TOC Next

John Baez and I have been having a conversation about nonstandard models of Peano arithmetic (PA). It started with “John’s dream”, as I’ll call it, which begat a goal: understand a paper by Enayat. For more on the dream and the goal, check out the second post.

Many aspects of nonstandard arithmetic (NSA) don’t lie along our itinerary. This series of posts will be a home for them (or at least the ones that strike my fancy). Other posts may serve as footnotes or appendices to the conversation—stuff that doesn’t lend itself to the dialog format. Neither series is a prerequisite for the other. For convenience, I’ll refer to the other series as “the Conversation” here, and the two series will share a TOC.

One more bit of throat-clearing (or table-setting, pick your favorite metaphor) before I get down to business in the next post. I will mostly write in the Platonic style, where we pretend that there really is a great big universe of sets out there. The “real”, “actual”, “true” universe. It means I can say, for example, “ℕ denotes the system of the actual natural numbers”, or “true arithmetic is the set of formulas that hold in the standard model of Peano arithmetic”. Locutions like this litter the standard literature. For that matter, Platonic style licenses “The actual value of 20”, though I doubt I’ll be writing anything like that.

This looks like philosophy, but it’s really just style. People tend to ask questions like, “Where is this reasoning taking place? In what system is there supposed to be this complete theory/model of ZFC/notion of truth…”. It’s nice to answer, “Why, in the actual universe of sets!” Now, people (like me) who talk this way don’t need an actual universe that really exists and is the one and only true universe. We just need an outermost universe we can talk about.

What is that outermost universe? We don’t really care, so long as it obeys a reasonable bunch of axioms. (Usually ZFC. Which is why you won’t hear me talking about “the actual value of 20”.) This suggests “Hilbert’s gambit”, aka the formalist turn: all that matters is what we can formally prove from the axioms. I’m sure you’ve heard the motto, “Math is a game with symbols.” (Apparently Hilbert never said this, and it misstates his position. I thought I should note that.) All this blather about the actual universe of sets is “merely corroborative detail, intended to give artistic verisimilitude to an otherwise bald and unconvincing narrative.” (W.S.Gilbert)

Philosophically, I’m ok (or at least equally ok) with both Platonism and formalism. (Not that those are the only two choices!) I don’t know that Cantor and Gödel and Cohen were wrong—maybe there really is “one true universe” out there! But I don’t know that the formalists are wrong, either, and maybe it is just a symbol game! Or maybe one of my old professors was right, and some kind of “mathematical multiverse” best describes the state of affairs.

When discussing this stuff, it’s nearly always way more pleasant to talk as if the ZFC universe really exists, than to be formal. “Naive set theory” gets the job done. That’s what I mean by the Platonist style. I’ve been doing this long enough so I know how to stay safely inside the ZFC boundary—and I’m not enough of a masochist to try actually formalizing stuff (at least fully).

A warning: this is a blog, not a textbook; the order of topics will be driven by whim, not careful organization. If I use a term before defining it, Wikipedia and search engines lie at your fingertips. Sometimes I’ll provide a link, and sometimes I’ll be lazy.

TOC Next

Leave a comment

Filed under Peano arithmetic

Non-standard Models of Arithmetic 19

Prev TOC Next

JB: Before we get into any proofs, I’d just like to marvel at Enayat’s Prop. 6, and see if I understand it correctly. I tried to state it in my own words on my own blog:

Every ZF-standard model of PA that is not V-standard is recursively saturated.

I said ‘V-standard’ to mean what you and Enayat call ‘standard’. I wanted to emphasize that the models of PA being considered live inside models of ZF, which in turn live in some universe of sets V. I get confused if I don’t see this three-layer structure, since this (as far as I can tell) is what permits the difference between ‘ZF-standardness’ and what Enayat calls ‘standardness’.

And of course my ulterior motive, which I revealed way back in Part 2, is to understand ‘standardness’ as a relative concept. I think we’re seeing this here. The model of PA in Proposition 6 thinks it’s perfectly standard in its universe U: the universe of sets described by some model of ZF. It’s smugly confident of its standardness. But look out the window! It turns out U is living in some larger universe V—and in here our model of PA is not standard. It’s merely ZF-standard, not V-standard.

Please correct me if I’ve got this wrong. But please be merciful: I’m being a bit poetic here; my blog article aims to be a bit more precise.

MW: Looks pretty good. So good, that I want to use this U, V notation consistently. (To that end, I modified the previous post, post-publication. I think this is called retconning by the cognoscenti.) I will usually leave ‘V’ implicit. (I’m one of those fish who don’t realize they’re swimming in water.)

I would say that U is smugly confident of ωU’s standardness, not the other way around.

JB: I meant that ωU was smugly confident of its own standardness, since it’s ‘standard in U‘. But your formulation is probably better.

MW: It’s good you describe this three-decker sandwich, as it gives me the perfect segue to another issue. I rushed things at the end of the last post. Bringing up the Foundation Axiom wasn’t incorrect, per se, but it doesn’t cut to the heart of the matter. After all, a nonstandard (U,ε) also must satisfy the Foundation Axiom!

The real issue pops up in a simpler two-level form, for any nonstandard model N of PA. As people always put it, seen from outsideN has an infinite descending sequence n–1 > n–2 > … , for some nonstandard n. But the Least Number Principle (LNP) manages to survive in N, because the set {n, n–1, n–2, …} is not definable, and so invisible inside N. (The LNP is just the contrapositive form of the Induction Axiom.)

The three-decker sandwich looks much the same. With our (U,ε) glasses on, the infinite descending sequence {n, n–1, n–2, …} isn’t visible—it’s not one of the sets of U. But viewed from outside, from V, we can see the violation of the LNP.

Natural question: why can’t this situation arise if ε is “the true” ∈? In that case, the infinite descending sequence turns out to be an infinite sequence of sets snsn–1∋… outside in the “real world” (pardon the expression). This is forbidden by the Foundation Axiom. If ε is just any old binary relation, we can’t make that argument.

JB: Great. I want to get into this sort of thing a bit more deeply, so I can start building up an intuitive sense for Enayat’s Proposition 6. But first, please tell me what Enayat means by ΦT, so we’ll be done with the ‘review’.

MW: OK! Main point, as I mentioned last time: Enayat’s Theorem 4. This says that PA+ΦT  recursively axiomatizes PAT, which is the set of sentences (in L(PA)) that hold in all T-standard models. The poster-child for a member of PAT: Con(PA). But waiting in the wings we have many other instances, e.g., Con(PA+Con(PA)), or all sorts of stuff about countable ordinals that can be coded into PA, and proven in T.

Here are two equivalent formal definitions of ΦT :

\Phi_T=\{\varphi \rightarrow\text{Con}(T_n+\varphi^\mathbb{N}):\varphi\in\text{L(PA)},n\in\omega\}
\Phi_T=\{\text{``}T_n\vdash\varphi^\mathbb{N}\text{''}\rightarrow\varphi : \varphi\in\text{L(PA)},n\in\omega\}

Posts 13 and 14 delved into the proof of Theorem 4. In post 14, I offered a summary of the second definition. Let me repeat that, plus an informal phrasing for the first. ΦT say that:

Adding a true statement about ω to T can’t introduce an inconsistency.

Trust what T says about ω: If T proves it, then it’s true.

I agree that Enayat’s Prop. 6 is pretty nifty, but I really start marvelling at Cor. 8. What does it take for a nonstandard model N of PA to gain entry into the exclusive club of T-omegas? (I still don’t like T-standard, as a term.) By the very definition of PAT, N must satisfy it. Since PA+ΦT  is an equivalent axiomatization, N must satisfy that too. But that’s not enough! Enayat identifies the exact missing ingredient, at least for countable models: N must be recursively saturated.

The countability restriction is somewhat annoying. In general, uncountable models of PA are less well understood than countable models. Enayat chips away at the uncountable case in the rest of the paper. I must confess, that part doesn’t interest me as much. Were I a grad student looking for a thesis topic, I might feel different.

JB: Okay: if it’s mainly a matter of ‘uncountable models of PA are harder’, I don’t want to go there. I was thinking maybe there could be counterexamples that I should know about, showing Enayat needs countability for his results to hold.

MW: Enayat doesn’t need countability for Prop. 6, but it is crucial for Theorem 7. Every nonstandard ZF-standard model is recursively saturated, but there are uncountable recursively saturated models of PA+ΦT  that are not T-standard. See Enayat’s Remark 10. Our old friend the Tarski undefinability theorem provides the clincher. I guess we could look at that, once we’re finished with Prop. 6 and Theorem 7.

JB: Okay. I’d forgotten countability isn’t required for Prop. 6! I’d really like to dive into Prop. 6 next time. You’re more sophisticated so you’re excited about the more impressive Theorem 7, but I’m still awed by Prop. 6. In my blog I tried to dramatize it this way:

In short, Enayat has found that ZF-standard models of Peano arithmetic in the universe V come in two drastically different kinds. They are either ‘as standard as possible’, namely V-standard. Or, they are ‘extremely rich’, containing n-tuples with all possible lists of consistent properties that you can print out with a computer program: they are recursively saturated.

You know the British phrase ‘bog-standard’? It means “utterly basic, ordinary, unremarkable, unexceptional”. I found this phrase very mysterious at first: is England so soggy that bogs are the epitome of standardness? Anyway, whenever I hear ‘ZF-standard’ or ‘V-standard’ I think about this phrase. In a way, Enayat is saying ZF-standard models of arithmetic are either extremely rich or they’re bog-standard.

Prev TOC Next

1 Comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 18

Prev TOC Next

MW: To my mind, the heart of Enayat’s paper is Proposition 6 and Theorem 7, which combine to give Corollary 8.

Proposition 6: Every ZF-standard model of PA that is nonstandard is recursively saturated.

Theorem 7: Every countable recursively saturated model of PA+ΦT is a T-standard model of PA.

Corollary 8: The following statements are equivalent for a countable nonstandard model A of arithmetic:

  1. A is a T-standard model of PA.
  2. A is a recursively saturated model of PA+ΦT.

Continue reading

1 Comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 17

Prev TOC Next

MW: I’d like to chew a bit more on this matter of Trued versus True. This Janus-feature of the Tarski legacy fascinated me from the start, though I didn’t find it paradoxical. But now I’m getting an inkling of how it seems to you.

Continue reading

2 Comments

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 16

Prev TOC Next

MW: Ok, let’s plunge into the construction of Trued(x). The bedrock level: True0(x), truth for (closed) atomic formulas. Continue reading

Leave a comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 15

Prev TOC Next

The Truth about Truth

MW: A little while back, I noted something delicious about the history of mathematical logic:

  • Gödel’s two most famous results are the completeness theorem and the incompleteness theorem.
  • Tarski’s two most famous results are the undefinability of truth and the definition of truth.

Continue reading

Leave a comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 14

Prev TOC Next

MW: Recap: we showed that PAT implies ΦT, where ΦT is the set of all formulas

\{\varphi\rightarrow\text{Con}(T_n+\varphi^\mathbb{N}):\varphi\in\text{L(PA)},n\in\omega\}

Now we have to show the converse, that PA+ΦT  implies PAT. But first let’s wave our hands, hopefully shaking off some intuition, like a dog shaking off water.

Continue reading

Leave a comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 13

Prev TOC Next

MW: OK, back to the main plotline. Enayat asks for a “natural” axiomatization of PAT. Personally, I don’t find PAT all that “unnatural”, but he needs this for Theorem 7. (It’s been a while, so remember that Enayat’s T is a recursively axiomatizable extension of ZF.)

Continue reading

Leave a comment

Filed under Conversations, Peano arithmetic

Non-standard Models of Arithmetic 12

Prev TOC Next

JB: It’s been a long time since Part 11, so let me remind myself what we’re talking about in Enayat’s paper Standard models of arithmetic.

We’ve got a theory T that’s a recursively axiomatizable extension of ZF. We can define the ‘standard model’ of PA in any model of T, and we call this a ‘T-standard model’ of PA. Then, we let PAT to be all the closed formulas in the language of Peano arithmetic that hold in all T-standard models.

This is what Enayat wants to study: the stuff about arithmetic that’s true in all T-standard models of the natural numbers. So what does he do first?

Continue reading

Leave a comment

Filed under Conversations, Peano arithmetic