# Category Archives: Conversations

## Nonstandard Arithmetic: A Long Comment Thread

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

Filed under Conversations, 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

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.

1 Comment

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 17

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.

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 16

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

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 15

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.

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 14

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.

Filed under Conversations, Peano arithmetic

## Non-standard Models of Arithmetic 13

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

Filed under Conversations, Peano arithmetic

## First-Order Categorical Logic 6

MW: An addendum to the last post. I do have an employment opportunity for one of those pathological scaffolds: the one where B(0) is the 2-element boolean algebra, and all the B(n)’s with n>0 are trivial. It’s perfect for the semantics of a structure with an empty domain.

The empty structure has a vexed history in model theory. Traditionally, authors excluded it from the get-go, but more recently some have rescued it from the outer darkness. (Two data points: Hodges’ A Shorter Model Theory allows it, but Marker’s Model Theory: An Introduction forbids it.)