In this part of the book we focus on ways to ‘generate’ a model of a theory. Of course, the most natural notion of generation is closure under functions. However, we are interested in constructing elementary submodels and it is easy to see that the addition of Skolem functions destroys many model theoretic properties including, in particular, the stability hierarchy. For example, there exist ω-stable theories with no complete ω-stable Skolemization. Thus we turn to more general notions. One such idea is known to model theorists as the ‘algebraic closure’ of a set A; it consists of those points which lie in finite sets defined by formulas with parameters from A. Except in the extreme case of a strongly minimal set, this notion lacks the exchange (symmetry) property of a good dependence relation. A next attempt is to adjoin those points which realize a principal type over A. Here too, the full symmetry property is lacking but a reasonable substitute (cf. Section IX.3) holds. However, the requirement that every set have a closure with respect to this relation which is a model of T is extremely strong. In fact, the only known nontrivial sufficient condition for every set to have a closure with respect to this relation is the assumption that the theory is countable and ω-stable. It is necessary to consider some further variants in order to find a notion of closure which is both strong enough to be useful and which applies to a wide class of theories. In this part of the book we give a general treatment of several such properties.

Introduction

In this chapter we present the First Main Theorem. This theorem gives a criterion for determining which processes in analysis and physics preserve computability and which do not. A major portion of this chapter is devoted to applications.

Here by the term “process” we mean a linear operator on a Banach space. The Banach space is endowed with a computability structure, as defined axiomatically in Chapter 2. Roughly speaking, the First Main Theorem asserts:

Although this already conveys the basic idea, it is useful to state the theorem with a bit more precision. The theorem involves a closed operator T from a Banach space X into a Banach space Y. We assume that Tacts effectively on an effective generating set {en} for X. Then the conclusion is: T maps every computable element of its domain onto a computable element of Y if and only if T is bounded.

We observe that there are three assumptions made in the above theorem: that T be closed, bounded or unbounded as the case may be, and that T acts effectively on an effective generating set. We now examine each of these assumptions in turn.

Consider first the assumption that T be bounded/unbounded. This assumption is viewed classically; it has no recursion-theoretic content. In this respect, the approach given here represents a generalization and unification of that followed in Chapters 0 and 1. In Chapters 0 and 1, we gave explicit recursion-theoretic codings —a different one for each theorem. The First Main Theorem also involves a coding, bujt this coding is embedded once and for all in the proof. In the applications of the Fitst Main Theorem, no such coding is necessary. Thus, in these applications, we are free to regard the boundedness or unboundedness of the operator as a classical fact, and the effective content of this fact becomes irrelevant.

Consider next the assumption that T be closed. The notion of a closed operator is standard in classical analysis. It is spelled out, with examples, in Section 1. However, if the reader is willing to assume the standard fact—that all of the basic operators of analysis and physics are closed—he or she could simply skip Section 1.

After having finished this book on the metamathematics of first order arithmetic, we consider the following aspects of it important: first, we pay much attention to subsystems (fragments) of the usual axiomatic system of first order arithmetic (called Peano arithmetic), including weak subsystems, i.e. so-called bounded arithmetic and related theories. Second, before discussing proper metamathematical questions (such as incompleteness) we pay considerable attention to positive results, i.e. we try to develop naturally important parts of mathematics (notably, some parts of set theory, logic and combi-natorics) in suitable fragments. Third, we investigate two notions of relative strength of theories: interpret ability and partial conservativity. Fourth, we offer a systematic presentation of relations of bounded arithmetic to problems of computational complexity.

The need for a monograph on metamathematics of first order arithmetic has been felt for a long time; at present, besides our book, at least two books on this topic are to be published, one written by R, Kaye and one written by C. Smorynski. We have been in contacts with both authors and are happy that the overlaps are reasonably small so that the books will complement each other.

This book consists of a section of preliminaries and of three parts: A -Positive results on fragments, B - Incompleteness, C - Bounded arithmetic. Preliminaries and parts A, B were written by P. H., part C by P. P. We have tried to keep all parts completely compatible.

The reader is assumed to be familiar with fundamentals of mathematical logic, including the completeness theorem and Herbrand's theorem; we survey the things assumed to be known in the Preliminaries, in order to fix notation and terminology.

Acknowledgements. Our first thanks go to the members of the 12-group for the possibility of publishing the book in the series Perspectives in mathematical logic and especially to Professor Gert H. Miiller, who invited P. H. to write a monograph with the present title, agreed with his wish to write the book jointly with P. P. and continuously offered every possible help. We are happy to recognize that we have been deeply influenced by Professor Jeff Paris.