## Recursive Saturation

Woo-hoo! Michael Weiss is teaching me about ‘recursively saturated’ models of Peano arithmetic:

• John Baez and Michael Weiss, Non-standard models of arithmetic 20, 12 October 2020.

Suppose you have a model of Peano arithemetic. Suppose you have an infinite list of predicates in Peano arithmetic: $\phi_1(x), \phi_2(x), \dots.$ Suppose that for any finite subset of these, your model of PA has an element $x$ making them true. Is there an element $x$ making all these predicates true?

Of course this doesn’t hold in the standard model of PA. Consider this example:

$x > 0, x > 1, x > 2, \dots$

For any finite collection of these inequalities, we can find a standard natural number $x$ large enough to make them true. But there’s no standard natural number that makes all these inequalities true.

On the other hand, for any nonstandard model of PA we can find an element x that obeys all of these:

$x > 0, x > 1, x > 2, \dots$

In fact this is the defining feature of a nonstandard model. (To be clear, I mean $x > n$ where $n$ ranges over standard natural numbers. A model of PA is nonstandard iff it contains an element greater than all the standard natural numbers.)

For a more interesting example, consider these predicates:

$2|n, 3|n, 5|n, 7|n, 11|n, \dots$

For any finite set of primes we can find a natural number divisible by all the primes in this set. We can’t find a standard natural number divisible by every prime, of course. But remarkably, in any nonstandard model of PA there is an element divisible by every prime—or more precisely, every standard prime.

In fact, suppose we have a model of PA, and an infinite list of predicates $\phi_i$ in PA, and for any finite subset of these our model has an element $x$ obeying the predicates in that subset. Then there is an element $x$ obeying all the predicates $\phi_i$ if:

1. the model is nonstandard,
2. you can write a computer program that lists all these predicates $\phi_1(x), \phi_2(x), \dots,$
3. there’s an upper bound on the number of alternating quantifiers $\forall \exists \forall \exists \cdots$ in the predicates $\phi_i.$

Intuitively, this result says that nonstandard models are very ‘fat’, containing nonstandard numbers with a wide range of properties. More technically, 2. says the predicates can be ‘recursively enumerated’, and this remarkable result is summarized by saying every nonstandard model of PA is ‘$recursively \Sigma_n$-saturated’.

In our conversation, Michael led me through the proof of this result. To do this, we used the fact that despite Tarski’s theorem on the undefinability of truth, truth is arithmetically definable for statements with any fixed upper bound on their number of alternating quantifiers! Michael had explained this end run around the undefinability of truth earlier, in Part 15 and Part 16 of our conversation.

Next we’ll show that if our nonstandard model is ‘ZF-standard’—that is, if it’s the $\omega$ in some model of ZF—we can drop condition 3. above. So, in technical jargon, we’ll show that any nonstandard but ZF-standard model is ‘recursively saturated’.

I’m really enjoying these explorations of logic!

### 3 Responses to Recursive Saturation

1. hmflogic says:

There is a countable nonstandard model of PA that is not recursively saturated. The problem is that there may not be an upper bound on the number of quantifiers used in your set of formulas.

• John forgot to mention the third condition:

3) The model is the omega of a model of ZF.

Enayat calls this a ZF-standard model of PA.

When there is an upper bound, (3) isn’t needed.

• John Baez says:

Whoops. I was getting ahead of myself and screwed up. I fixed the post so it mainly talks about what we’ve actually done so far.

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