Recursive Saturation

Azimuth 2020-10-13

Woo-hoo! Michael Weiss almost taught me how to prove every nonstandard model of PA is ‘recursively saturated’:

• 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$ obeying the predicates in that subset. Is there an element $x$ obeying all these predicates?

Of course this isn’t true for 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 of them. 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:

the model is nonstandard,
you can write a computer program that lists all these predicates $\phi_1(x), \phi_2(x), \dots,$

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 saturated’.

In our conversation, Michael has so far only led me through the proof of this result in the special case when there’s an upper bound on the number of alternating quantifiers $\forall \exists \forall \exists \cdots$ in the predicates $\phi_i.$ 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.

I’m really enjoying these explorations of logic!