An Incompleteness Theorem for $\beta _n$-Models

Carl Mummert¹
Stephen G. Simpson²

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 L₂, the language of second order arithmetic. L₂ 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 L₂-sentence with parameters from M, we define $M\models\Phi$to mean that M satisfies $\Phi$, i.e., $\Phi$ is true in the L₂-model $\left(\omega,M,+,\cdot,=,<,\in\right)$. If S is a set of L₂-sentences, we define $M\models S$ to mean that $M\models\Phi$for all $\Phi\in S$.

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

$$\exists X_1 \forall X_2 \exists X_3 \cdots X_n\, \Theta$$

with n alternating set quantifiers, where $\Theta$ is arithmetical. An L₂-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$,

$$P(\omega) \models \Phi(A_1, \ldots, A_k)\quad\Leftrightarrow\quad M \models \Phi(A_1, \ldots , A_k).$$

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.''

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 L₂-theory. Let $\Phi$ be an L₂-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$.

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 B_n(X,S) is equivalent to a $\Pi^1_n$ formula. The equivalence is provable in $\mathsf{ACA}_0^{+}$.

Lemma 3.2   Let S be a recursively axiomatized L₂-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.

We now present our corollaries.

Corollary 3.3   Let S be a recursively axiomatized L₂-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.

Corollary 3.4   Let S be a recursively axiomatized L₂-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.

Remark 3.5   In Corollary 3.4, S can be any true recursively axiomatized L₂-theory. For example, we may take S to be any of the following specific L₂-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 Z₂ in [10].

Remark 3.6   Let S be any of the specific L₂-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.

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

... Mummert¹

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

... Simpson²

http://www.math.psu.edu/simpson/. Simpson's research was partially supported by NSF Grant DMS-0070718.