Enayat on Nonstandard Numbers

Michael Weiss and I have been carrying on a dialog on nonstandard models of arithmetic, and after a long break we’re continuing, here:

• Michael Weiss and John Baez, Non-standard models of arithmetic (Part 18).

In this part we reach a goal we’ve been heading toward for a long time! We’ve been reading this paper:

• Ali Enayat, Standard models of arithmetic.

and we’ve finally gone through the main theorems and explained what they say. We’ll talk about the proofs later.

The simplest one is this:

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

What does this theorem mean, roughly? Let me be very sketchy here, to keep things simple and give just a flavor of what’s going on.

Peano arithmetic is a well-known axiomatic theory of the natural numbers. People study different models of Peano arithmetic in some universe of sets, say U. If we fix our universe U there is typically one ‘standard’ model of Peano arithmetic, built using the set

or in other words

All models of Peano arithmetic not isomorphic to this one are called ‘nonstandard’. You can show that any model of Peano arithmetic contains an isomorphic copy of standard model as an initial segment. This uniquely characterizes the standard model.

But different axioms for set theory give different concepts of U, the universe of sets. So the uniqueness of the standard model of Peano arithmetic is relative to that choice!

Let’s fix a choice of axioms for set theory: the Zermelo–Fraenkel or ‘ZF’ axioms are a popular choice. For the sake of discussion I’ll assume these axioms are consistent. (If they turn out not to be, I’ll correct this post.)

We can say the universe U is just what ZF is talking about, and only theorems of ZF count as things we know about U. Or, we can take a different attitude. After all, there are a couple of senses in which the ZF axioms don’t completely pin down the universe of sets.

First, there are statements in set theory that are neither provable nor disprovable from the ZF axioms. For any of these statements we’re free to assume it holds, or it doesn’t hold. We can add either it or its negation to the ZF axioms, and still get a consistent theory.

Second, a closely related sense in which the ZF axioms don’t uniquely pin down U is this: there are many different models of the ZF axioms.

Here I’m talking about models in some universe of sets, say V. This may seem circular! But it’s not really: first we choose some way to deal with set theory, and then we study models of the ZF axioms in this context. It’s a useful thing to do.

So fix this picture in mind. We start with a universe of sets V. Then we look at different models of ZF in V, each of which gives a universe U. U is sitting inside V, but from inside it looks like ‘the universe of all sets’.

Now, for each of these universes U we can study models of Peano arithmetic in U. And as I already explained, inside each U there will be a standard model of Peano arithmetic. But of course this depends on U.

So, we get lots of standard models of Peano arithmetic, one for each choice of U. Enayat calls these ZF-standard models of Peano arithmetic.

But there is one very special model of ZF in V, namely V itself. In other words, one choice of U is to take U = V. There’s a standard model of Peano arithmetic in V itself. This is an example of a ZF-standard model, but this is a very special one. Let’s call any model of Peano arithmetic isomorphic to this one V-standard.

Enayat’s theorem is about ZF-standard models of Peano arithmetic that aren’t V-standard. He shows that any ZF-standard model that’s not V-standard is ‘recursively saturated’.

What does it mean for a model M of Peano arithmetic to be ‘recursively saturated’? The idea is very roughly that ‘anything that can happen in any model, happens in M’.

Let me be a bit more precise. It means that if you write any computer program that prints out an infinite list of properties of an n-tuple of natural numbers, and there’s some model of Peano arithmetic that has an n-tuple with all these properties, then there’s an n-tuple of natural numbers in the model M with all these properties.

For example, there are models of Peano arithmetic that have a number x such that

0 < x
1 < x
2 < x
3 < x

and so on, ad infinitum. These are the nonstandard models. So a recursively saturated model must have such a number x. So it must be nonstandard.

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.

I am probably almost as confused about this as you are. But Michael and I will dig into this more in our series of posts.

In fact we’ve been at this a while already. Here is a description of the whole series of posts so far:

Posts 1–10 are available as pdf files, formatted for small and medium screens.

Non-standard Models of Arithmetic 1: John kicks off the series by asking about recursively saturated models, and Michael says a bit about n-types and the overspill lemma. He also mentions the arithmetical hierarchy.

Non-standard Models of Arithmetic 2: John mention some references, and sets a goal: to understand this paper:

• Ali Enayat, Standard models of arithmetic.

John describes his dream: to show that “the” standard model is a much more nebulous notion than many seem to believe. He says a bit about the overspill lemma, and Joel David Hamkins gives a quick overview of saturation.

Non-standard Models of Arithmetic 3: A few remarks on the ultrafinitists Alexander Yessenin-Volpin and Edward Nelson; also Michael’s grad-school friend who used to argue that 7 might be nonstandard.

Non-standard Models of Arithmetic 4: Some back-and-forth on Enayat’s term “standard model” (or “ZF-standard model”) for the omega of a model of ZF. Philosophy starts to rear its head.

Non-standard Models of Arithmetic 5: Hamlet and Polonius talk math, and Michael holds forth on his philosophies of mathematics.

Non-standard Models of Arithmetic 6: John weighs in with why he finds “the standard model of Peano arithmetic” a problematic phrase. The Busy Beaver function is mentioned.

Non-standard Models of Arithmetic 7: We start on Enayat’s paper in earnest. Some throat-clearing about Axiom SM, standard models of ZF, inaccessible cardinals, and absoluteness. “As above, so below”: how ZF makes its “gravitational field” felt in PA.

Non-standard Models of Arithmetic 8: A bit about the Paris-Harrington and Goodstein theorems. In preparation, the equivalence (of sorts) between PA and ZF¬∞. The universe V_ω of hereditarily finite sets and its correspondence with . A bit about Ramsey’s theorem (needed for Paris-Harrington). Finally, we touch on the different ways theories can be “equivalent”, thanks to a comment by Jeffrey Ketland.

Non-standard Models of Arithmetic 9: Michael sketches the proof of the Paris-Harrington theorem.

Non-Standard Models of Arithmetic 10: Ordinal analysis, the function growth hierarchies, and some fragments of PA. Some questions that neither of us knows how to answer.

Non-standard Models of Arithmetic 11: Back to Enayat’s paper: his definition of PA^T for a recursive extension T of ZF. This uses the translation of formulas of PA into formulas of ZF, . Craig’s trick and Rosser’s trick.

Non-standard Models of Arithmetic 12: The strength of PA^T for various T‘s. PA^ZF is equivalent to PA^ZFC+GCH, but PA^ZFI is strictly stronger than PA^ZF. (ZFI = ZF + “there exists an inaccessible cardinal”.)

Non-standard Models of Arithmetic 13: Enayat’s “natural” axiomatization of PA^T, and his proof that this works. A digression into Tarski’s theorem on the undefinability of truth, and how to work around it. For example, while truth is not definable, we can define truth for statements with at most a fixed number of quantifiers.

Non-standard Models of Arithmetic 14: The previous post showed that PA^T implies Φ_T, where Φ_T is Enayat’s “natural” axiomatization of PA^T. Here we show the converse. We also interpret Φ_T as saying, “Trust T”.

Non-standard Models of Arithmetic 15: We start to look at Truth (aka Satisfaction). Tarski gave a definition of Truth, and showed that Truth is undefinable. Less enigmatically put, there is no formula True(x) in the language of Peano arithmetic (L(PA)) that holds exactly for the Gödel numbers of true sentences of Peano arithmetic. On the other hand, Truth for Peano arithmetic can be formalized in the language of set theory (L(ZF)), and there are other work-arounds. We give an analogy with the Cantor diagonal argument.

Non-standard Models of Arithmetic 16: We look at the nitty-gritty of True_d(x), the formula in L(PA) that expresses truth in PA for formulas with parse-tree depth at most d. We see how the quantifiers “bleed through”, and why this prevents us from combining the whole series of True_d(x)’s into a single formula True(x). We also look at the variant Sat_Σn(x,y).

Non-standard Models of Arithmetic 17: More about how True_d evades Tarski’s undefinability theorem. The difference between True_d and Sat_Σn, and how it doesn’t matter for us. How True_d captures Truth for models of arithmetic: PA ⊢ True_d(⌜φ⌝) ↔ φ, for any φ of parse-tree depth at most d. Sketch of why this holds.

• Non-standard Models of Arithmetic 18: The heart of Enayat’s paper: characterizing countable nonstandard T-standard models of PA (Prop. 6, Thm. 7, Cor. 8). Refresher on types. Meaning of ‘recursively saturated’. Standard meaning of ‘nonstandard’; standard and nonstandard meanings of ‘standard’.

• Non-standard Models of Arithmetic 19: We marvel a bit over Enayat’s Prop. 6, and especially Cor. 8. The triple-decker sandwich, aka three-layer cake: ω^U⊂U⊂V. More about why the omegas of standard models of ZF are standard. Refresher on Φ_T. The smug confidence of a ZF-standard model.

• Non-standard Models of Arithmetic 20: We start to develop the proof of Enayat’s Prop. 6. We get as far as a related result: any nonstandard model of PA is recursively d-saturated. (‘Recursively d-saturated’ is our user-friendly version of the professional-grade concept: recursively Σ_n-saturated.)