# An Incompleteness Theorem for -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 -model we mean an -model which is elementary with respect to formulas. We prove the following -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 -model of S, then there exists a -model of S+there is no countable -model of S.'' We also prove a -model version of Löb's Theorem. As a corollary, we obtain a -model which is not a -model.

# Introduction

Let denote the set of natural numbers . Let denote the set of all subsets of . An -model is a nonempty set , viewed as a model for the language of second order arithmetic. Here the number variables range over , the set variables range over M, and the arithmetical operations are standard. For n a positive integer, a -model is an -model which is an elementary submodel of with respect to formulas of the language of second order arithmetic.

Recently Engström [3] posed the following question: Does there exist a -model which is not a -model? To our amazement, there seems to be no answer to this question in the literature.

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

In this paper we answer Engström's question affirmatively. We prove that, for each , there exists a -model which is not a -model (Corollary 3.7). Our proof is based on a -model version of Gödel's Second Incompleteness Theorem (Theorem 2.1). We draw corollaries concerning -models of specific true theories (Corollary 3.3, Remark 3.5). We also obtain a -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 and intended to range over , and second order (set) variables, denoted and intended to range over . The variables of both sorts are quantified. We also have addition, multiplication, equality, and order for numbers, denoted , as well as set membership, denoted . Recall that an -model is a nonempty subset of . For M an -model and an L2-sentence with parameters from M, we define to mean that M satisfies , i.e., is true in the L2-model . If S is a set of L2-sentences, we define to mean that for all .

An L2-formula is said to be arithmetical if it contains no set quantifiers. An L2-formula is said to be if it is equivalent to a formula of the form

with n alternating set quantifiers, where is arithmetical. An L2-formula is said to be if its negation is . A -model is an -model M such that, for all formulas with exactly the free variables displayed, and for all ,

If X is a subset of , then X can be viewed as coding a countable -model , where . Moreover, every countable -model can be coded in this way. Therefore we define a countable coded -model to be simply a subset of . A countable coded -model is then a countable coded -model X such that is a -model.

# A -model version of Gödel's Theorem

We now present the main theorem of this paper. Our theorem is a -model version of Gödel's Second Incompleteness Theorem [6]. It was inspired by the -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 , if there exists a -model of S, then there exists a -model of S+there is no countable coded -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 . Actually we could replace throughout this paper by the weaker theory the nth Turing jump of X exists).

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

Theorem 2.3   Let S be a recursively axiomatized L2-theory. Let be an L2-sentence. For each , if every -model of S satisfies
every countable coded -model of S satisfies '' ,
then every -model of S satisfies .

# Some corollaries of Theorem 2.1

In this section we draw corollaries concerning -models which are not -models. In order to do so, we need the following lemmas, which are well known.

Lemma 3.1   For each , the formula Bn(X,S) is equivalent to a formula. The equivalence is provable in .

Lemma 3.2   Let S be a recursively axiomatized L2-theory. Assume the existence of a -model of S. Let M be an -model of there is no countable coded -model of S.'' Then M is not a -model.

We now present our corollaries.

Corollary 3.3   Let S be a recursively axiomatized L2-theory. For each , if there exists a -model of S, then there exists a -model of S+there is no countable coded -model of S.'' Such a -model is not a -model.

Corollary 3.4   Let S be a recursively axiomatized L2-theory which is true, i.e., which holds in . Then for each there exists a -model of S+there is no countable coded -model of S.'' Such a -model is not a -model.

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]: comprehension, transfinite recursion, choice, dependent choice, strong dependent choice, , or any union of these, e.g., comprehension, choice, dependent choice. Note that 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 choice and dependent choice. By a minimum -model of S we mean a -model of S which is included in all -models of S. For n=1,2 a minimum -model of S can be obtained by methods of Simpson [10, Chapter VII] and Shilleto [8] respectively. For a minimum -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 there exists a -model which is not a -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 , 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.

An Incompleteness Theorem for -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.

Stephen G Simpson
2004-03-23