Non-standard Models of Arithmetic 19

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.

1 Comment

Filed under Conversations, Peano Arithmetic

One response to “Non-standard Models of Arithmetic 19”

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