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!

This entry was posted on Tuesday, October 13th, 2020 at 5:38 am and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to Recursive Saturation

  1. hmflogic says:
    13 October, 2020 at 7:09 am

    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.

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

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