next up previous


An Incompleteness Theorem for $\beta _n$-Models

Carl Mummert1
Stephen G. Simpson2

Department of Mathematics
Pennsylvania State University
State College, PA 16802, USA

March 23, 2004

Submitted for JSL December 16, 2003
Accepted February 13, 2004

Abstract:

Let n be a positive integer. By a $\beta _n$-model we mean an $\omega$-model which is elementary with respect to $\Sigma^1_n$ formulas. We prove the following $\beta _n$-model version of Gödel's Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a $\beta _n$-model of S, then there exists a $\beta _n$-model of S+``there is no countable $\beta _n$-model of S.'' We also prove a $\beta _n$-model version of Löb's Theorem. As a corollary, we obtain a $\beta _n$-model which is not a $\beta_{n+1}$-model.

Introduction

Let $\omega$ denote the set of natural numbers $\{0,1,2,\ldots\}$. Let $P(\omega)$ denote the set of all subsets of $\omega$. An $\omega$-model is a nonempty set $M\subseteq P(\omega)$, viewed as a model for the language of second order arithmetic. Here the number variables range over $\omega$, the set variables range over M, and the arithmetical operations are standard. For n a positive integer, a $\beta _n$-model is an $\omega$-model which is an elementary submodel of $P(\omega)$ with respect to $\Sigma^1_n$formulas of the language of second order arithmetic.

Recently Engström [3] posed the following question: Does there exist a $\beta _n$-model which is not a $\beta_{n+1}$-model? To our amazement, there seems to be no answer to this question in the literature.

Previous research has focused on minimum $\beta _n$-models. A minimum $\beta _n$-model is a $\beta _n$-model which is included in all $\beta _n$-models. If a minimum $\beta _n$-model exists, then obviously it is unique, and it is not a $\beta_{n+1}$-model. However, the existence of minimum $\beta _n$-models is problematic, to say the least. Simpson [10, Corollary VIII.6.9] proves that there is no minimum $\beta_1$-model. Shilleto [8] proves the existence of a minimum $\beta_2$-model. Enderton and Friedman [2] prove the existence of minimum $\beta _n$-models, $n\ge3$, assuming a basis property which follows from V=L but which is not provable in $\mathsf{ZFC}$. We conjecture that the existence of a minimum $\beta _n$-model is not provable in $\mathsf{ZFC}$, for $n\ge3$. We have verified this conjecture for $n\ge4$. Simpson's book [10, Sections VII.1-VII.7 and VIII.6] contains further results concerning minimum $\beta_1$- and $\beta_2$-models of specific subsystems of second order arithmetic, as well as $\beta _n$-models for $n\ge3$. See also Remark 3.6 below.

In this paper we answer Engström's question affirmatively. We prove that, for each $n\ge1$, there exists a $\beta _n$-model which is not a $\beta_{n+1}$-model (Corollary 3.7). Our proof is based on a $\beta _n$-model version of Gödel's Second Incompleteness Theorem (Theorem 2.1). We draw corollaries concerning $\beta _n$-models of specific true theories (Corollary 3.3, Remark 3.5). We also obtain a $\beta _n$-model version of Löb's Theorem (Theorem 2.3).

Preliminaries

Our results are formulated in terms of L2, the language of second order arithmetic. L2 has variables of two sorts: first order (number) variables, denoted $i,j,k,m,n,\ldots$ and intended to range over $\omega$, and second order (set) variables, denoted $X,Y,Z,\ldots$ and intended to range over $P(\omega)$. The variables of both sorts are quantified. We also have addition, multiplication, equality, and order for numbers, denoted $+,\cdot,=,<$, as well as set membership, denoted $\in$. Recall that an $\omega$-model is a nonempty subset of $P(\omega)$. For M an $\omega$-model and $\Phi$an L2-sentence with parameters from M, we define $M\models\Phi$to mean that M satisfies $\Phi$, i.e., $\Phi$ is true in the L2-model $\left(\omega,M,+,\cdot,=,<,\in\right)$. If S is a set of L2-sentences, we define $M\models S$ to mean that $M\models\Phi$for all $\Phi\in S$.

An L2-formula is said to be arithmetical if it contains no set quantifiers. An L2-formula is said to be $\Sigma^1_n$ if it is equivalent to a formula of the form

\begin{displaymath}\exists X_1 \forall X_2 \exists X_3 \cdots X_n\, \Theta
\end{displaymath}

with n alternating set quantifiers, where $\Theta$ is arithmetical. An L2-formula is said to be $\Pi^1_n$ if its negation is $\Sigma^1_n$. A $\beta _n$-model is an $\omega$-model M such that, for all $\Sigma^1_n$ formulas $\Phi(X_1,\ldots,X_k)$ with exactly the free variables displayed, and for all $A_1,\ldots,A_k\in
M$,

\begin{displaymath}P(\omega) \models \Phi(A_1, \ldots, A_k)\quad\Leftrightarrow\quad M \models
\Phi(A_1, \ldots , A_k).
\end{displaymath}

If X is a subset of $\omega$, then X can be viewed as coding a countable $\omega$-model $\{ (X)_i : i \in \omega\}$, where $(X)_i =
\{ j : 2^i3^j \in X\}$. Moreover, every countable $\omega$-model can be coded in this way. Therefore we define a countable coded $\omega$-model to be simply a subset of $\omega$. A countable coded $\beta _n$-model is then a countable coded $\omega$-model X such that $\{ (X)_i : i \in \omega\}$ is a $\beta _n$-model.

A $\beta _n$-model version of Gödel's Theorem

We now present the main theorem of this paper. Our theorem is a $\beta _n$-model version of Gödel's Second Incompleteness Theorem [6]. It was inspired by the $\omega$-model version, due to Friedman [4, Chapter II], as expounded in Simpson [10, Theorem VIII.5.6]. See also Steel [11] and Friedman [5].

Theorem 2.1   Let S be a recursively axiomatized theory in the language of second order arithmetic. For each $n\ge1$, if there exists a $\beta _n$-model of S, then there exists a $\beta _n$-model of S+``there is no countable coded $\beta _n$-model of S.''


\begin{proof}% latex2html id marker 90
We use the subsystem $\mathsf{ACA}_0^{+}$...
...model of $S$ . This completes the proof of Theorem
\ref{thm:godel}.
\end{proof}

Remark 2.2   In proving Theorem 2.1, we have actually proved more. Namely, we have proved that Theorem 2.1 is provable in $\mathsf{ACA}_0^{+}$. Actually we could replace $\mathsf{ACA}_0^{+}$ throughout this paper by the weaker theory $\mathsf{ACA}_0^{\ast}=\mathsf{ACA}_0+\forall n\,\forall X\,($the nth Turing jump of X exists).

Our $\beta _n$-model version of Löb's Theorem [7] is as follows.

Theorem 2.3   Let S be a recursively axiomatized L2-theory. Let $\Phi$ be an L2-sentence. For each $n\ge1$, if every $\beta _n$-model of S satisfies
``every countable coded $\beta _n$-model of S satisfies $\Phi$'' $\,\,\Rightarrow\Phi$,
then every $\beta _n$-model of S satisfies $\Phi$.


\begin{proof}% latex2html id marker 111
This is a reformulation of Theorem \ref{thm:godel} with $S$\space replaced
by $S+\neg\,\Phi$ .
\end{proof}

Some corollaries of Theorem 2.1

In this section we draw corollaries concerning $\beta _n$-models which are not $\beta_{n+1}$-models. In order to do so, we need the following lemmas, which are well known.

Lemma 3.1   For each $n\ge1$, the formula Bn(X,S) is equivalent to a $\Pi^1_n$ formula. The equivalence is provable in $\mathsf{ACA}_0^{+}$.


\begin{proof}Note that an $\omega$ -model $M$\space is a $\beta_n$ -model if and...
...\Pi^1_1$ . We now see that $\mathrm{B}_n(X,S)$\space is
$\Pi^1_n$ .
\end{proof}

Lemma 3.2   Let S be a recursively axiomatized L2-theory. Assume the existence of a $\beta _n$-model of S. Let M be an $\omega$-model of $\mathsf{ACA}_0^{+}+{}$``there is no countable coded $\beta _n$-model of S.'' Then M is not a $\beta_{n+1}$-model.


\begin{proof}% latex2html id marker 131
Lemma \ref{lem:BnXS} implies that the se...
...pace but not in $M$ . Thus $M$\space is not a
$\beta_{n+1}$ -model.
\end{proof}

We now present our corollaries.

Corollary 3.3   Let S be a recursively axiomatized L2-theory. For each $n\ge1$, if there exists a $\beta _n$-model of S, then there exists a $\beta _n$-model of S+``there is no countable coded $\beta _n$-model of S.'' Such a $\beta _n$-model is not a $\beta_{n+1}$-model.


\begin{proof}% latex2html id marker 141
This is immediate from Theorem \ref{thm:...
...}, noting that any $\beta_n$ -model satisfies $\mathsf{ACA}_0^{+}$ .
\end{proof}

Corollary 3.4   Let S be a recursively axiomatized L2-theory which is true, i.e., which holds in $P(\omega)$. Then for each $n\ge1$ there exists a $\beta _n$-model of S+``there is no countable coded $\beta _n$-model of S.'' Such a $\beta _n$-model is not a $\beta_{n+1}$-model.


\begin{proof}% latex2html id marker 150
This is immediate from Corollary \ref{cor:beta1}, since $P(\omega)$ is a $\beta_n$ -model.
\end{proof}

Remark 3.5   In Corollary 3.4, S can be any true recursively axiomatized L2-theory. For example, we may take S to be any of the following specific L2-theories, which have been discussed in Simpson [10]: $\Pi^1_m$ comprehension, $\Pi^1_m$ transfinite recursion, $\Sigma^1_m$ choice, $\Sigma^1_m$ dependent choice, strong $\Sigma^1_m$ dependent choice, $m\ge 1$, or any union of these, e.g., $\Pi^1_\infty$ comprehension, $\Sigma^1_\infty$ choice, $\Sigma^1_\infty$ dependent choice. Note that $\Pi^1_\infty$ comprehension is full second order arithmetic, called Z2 in [10].

Remark 3.6   Let S be any of the specific L2-theories mentioned in Remark 3.5, except $\Sigma^1_1$ choice and $\Sigma^1_1$ dependent choice. By a minimum $\beta _n$-model of S we mean a $\beta _n$-model of S which is included in all $\beta _n$-models of S. For n=1,2 a minimum $\beta _n$-model of S can be obtained by methods of Simpson [10, Chapter VII] and Shilleto [8] respectively. For $n\ge3$ a minimum $\beta _n$-model of S can be obtained by methods of Simpson [10, Chapter VII] and Enderton/Friedman [2] assuming V=L.

We answer Engström's question [3] affirmatively as follows.

Corollary 3.7   For each $n\ge1$ there exists a $\beta _n$-model which is not a $\beta_{n+1}$-model.


\begin{proof}% latex2html id marker 173
In Corollary \ref{cor:beta2} let $S$\space be the trivial $L_2$ -theory
with no axioms.
\end{proof}

Remark 3.8   Corollary 3.7 follows from the results of Enderton/Friedman [2] assuming V=L. We do not know of any proof of Corollary 3.7 in $\mathsf{ZFC}$, other than the proof which we have given here.

Bibliography

1
Andreas R. Blass, Jeffry L. Hirst, and Stephen G. Simpson.
Logical analysis of some theorems of combinatorics and topological dynamics.
In [9], pages 125-156, 1987.

2
Herbert B. Enderton and Harvey Friedman.
Approximating the standard model of analysis.
Fundamenta Mathematicae, 72(2):175-188, 1971.

3
Fredrik Engström, October 2003.
Private communication.

4
Harvey Friedman.
Subsystems of Set Theory and Analysis.
PhD thesis, Massachusetts Institute of Technology, 1967.
83 pages.

5
Harvey Friedman.
Uniformly defined descending sequences of degrees.
Journal of Symbolic Logic, 41:363-367, 1976.

6
Kurt Gödel.
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.
Monatshefte für Mathematik und Physik, 38:173-198, 1931.

7
M. H. Löb.
Solution of a problem of Leon Henkin.
Journal of Symbolic Logic, 20:115-118, 1955.

8
J. R. Shilleto.
Minimum models of analysis.
Journal of Symbolic Logic, 37:48-54, 1972.

9
S. G. Simpson, editor.
Logic and Combinatorics.
Contemporary Mathematics. American Mathematical Society, 1987.
XI + 394 pages.

10
Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

11
John R. Steel.
Descending sequences of degrees.
Journal of Symbolic Logic, 40:59-61, 1975.

About this document ...

An Incompleteness Theorem for $\beta _n$-Models

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 betan.tex.

The translation was initiated by Stephen G Simpson on 2004-03-23


Footnotes

... Mummert1
http://www.math.psu.edu/mummert/. Mummert's research was partially supported by a VIGRE graduate traineeship under NSF Grant DMS-9810759.
... Simpson2
http://www.personal.psu.edu/t20/. Simpson's research was partially supported by NSF Grant DMS-0070718.

next up previous
Stephen G Simpson
2004-03-23