An incompleteness theorem for βn models

My first paper was “An incompleteness theorem for $\beta_n$ models” with Stephen Simpson [1]. It’s a short paper, but the idea is very pretty. We know that the incompleteness theorem implies there are strange models of arithmetic, but these models often seem mysterious, and it’s hard to see what useful properties they can have. But now suppose that a theory of the form $A+B$ meets the hypotheses of the incompleteness theorem, and moreover this theory proves its own consistency, so that $A+B$ is inconsistent. It follows that if $A$ is true (that is, true in the standard model) then $B$ must be false. In this way, we can use the incompleteness theorem to prove facts about the standard model rather than about nonstandard ones. The idea is originally due to Harvey Friedman in his thesis, I believe.

We use this idea to prove a specific fact:

Theorem. For every $n > 0$ there is a $\beta_{n}$ model that is not a $\beta_{n+1}$ model.

Here a $\beta_n$ model is an $\omega$ model $M$ that satisfies every true $\Sigma^1_n$ formula with parameters from $M$. (It’s typical to just say “a $\beta_n$ model” rather than “a $\beta_n$ model of …”, but every $\beta_1$ model already satisfies ACA). A countable coded $\beta_n$ model is a countable $\beta_n$ model that has been encoded into a single subset of $\omega$.

Previous work of Friedman and Herbert Enderton [2] implies our theorem under the additional assumption of $V = L$. With the constructibility hypothesis, there is a minimum $\beta_n$ model for each $n > 0$, and this model is not a $\beta_{n+1}$ model.

Simpson and I proved the more general result without assuming $V=L$ by showing there is a $\beta_n$ model that does not satisfy “there exists a countable coded $\beta_n$ model”. Because the quoted phrase is given by a true $\Sigma^1_{n+1}$ sentence, it will be true in any $\beta_{n+1}$ model.

How do we show there is a $\beta_n$ model that does not contain a countable coded $\beta_n$ model? We begin with a sufficiently strong theory $T$ of second order arithmetic and consider the theory $T$ + “there is a countable coded $\beta_n$ model of $T$” + “every countable coded $\beta_n$ model of $T$ contains a countable coded $\beta_n$ model of $T$”. It is not hard to show that this theory proves its own consistency, and so is inconsistent. But because $T$ + “there is a countable coded $\beta_n$ model of $T$” is true, the final axiom of the stronger theory is false, which gives the result.

1. Carl Mummert and Stephen G. Simpson, “An incompleteness theorem for βn models”, Journal of Symbolic Logic v. 29 n. 2, 2004, pp. 612–616. DOI 10.2178/jsl/1082418545. Preprint: ps pdf
2. Herbert B. Enderton and Harvey Friedman, “Approximating the standard model of analysis”, Fundamenta Mathematicae, vol. 72, 1971, pp. 175–188.
This entry was posted in Papers, Research. Bookmark the permalink.

2 Responses to An incompleteness theorem for βn models

1. François says:

This is a very neat trick!

When I teach set theory, I like to show my students how every true axiomatizable extension T of ZFC either has no well-founded model, or it has a well-founded model that believes that there are no well-founded models of T. The argument is pretty simple. Suppose there is a well-founded model of T, “every well-founded model of T contains a well-founded model of T” is false since it implies the existence of a sequence of transitive models $M_i$ of T such that $M_0 \ni M_1 \ni M_2 \ni \cdots,$ and this sequence violates foundation.

The trick you illustrate strengthens this to show that every true axiomatizable extension T of ZFC either has no $\omega$-model, or it has an $\omega$-model that believes that there are no $\omega$-models of T. Indeed, it’s not difficult to see that T + “there is an $\omega$-model of T” + “every $\omega$-model of T contains an $\omega$-model of T” proves its own consistency. (Note that if $M$ is an $\omega$-model of T that contains an $\omega$-model of T, the smaller model can be pulled back out of $M$ to an $\omega$-model of T in the real world.) Therefore, one of “there is an $\omega$-model of T” and “every $\omega$-model of T contains an $\omega$-model of T” must be false in the standard model of set theory.

• Carl Mummert says:

I’m glad you pointed out the set theoretic side. I am usually only thinking about second-order arithmetic, but many of these results work equally well there and in set theory (which would be a nice subject for another post).

The result of your second paragraph is essentially Friedman’s result, although that result is in the context of second-order arithmetic, using countable coded $omega$-models. It’s Theorem VIII.5.6 in Simpson’s SOSOA. There is an interesting twist: the base theory has to include ACA0 in order for the result to go through. Every countable $omega$-model of WKL0 does contain a countable coded (omega)-model satisfying WKL0, notwithstanding the incompleteness theorem. The difference is that ACA0 is able to form the satisfaction predicate for a countable coded $omega$ model.

By the way, I have enabled a comment editing plugin on this blog – please try it out. There is a long delay when it starts, in my browser at least, and I noticed that it removes backslashes from comments when they are saved, so I will need to look into that.