In the remainder of this book, we calculate the possible spectra for two classes. If T is a countable superstable theory we will give the possible functions. If T is a countable ω-stable theory we will give the possible functions. A number of the theorems extend to more general classes of theories or to different classes of models. We have tried to build a framework which handles these more general cases. Thus, there are theorems and exercises referring to them. Some of the extensions we touch on are for any uncountable k, uncountable T, and small countable superstable T.

The calculation proceeds by first classifying the theories and then computing the spectra in each class. We begin with the fact, proved in Section IX.6, that if T is not superstable then. (We gave the proof only for regular k). Although we did not prove it here, it is shown in Chapter VII of [Shelah 1978], that I(k,S) = 2kThis justifies our assumption in the remainder of this book that T is superstable. Chapter XIV collects some of the main tools used in the computation. In Chapter XV we distinguish the bounded from the unbounded, or multidimensional, theories. We classify the spectra of bounded theories and compute a lower bound for the spectrum of an unbounded theory. Thereafter, we need only analyze unbounded theories. We also introduce in Chapter XV the notion of an eventually nonisolated type which is crucial for the study of countable models.

In Chapter XVI we introduce a major dividing line, the dimensional order property (DOP). We prove that if T has the dimensional order property then T has 2k S-models in every power We also find a flaw in our classification of the classes of models to study. That is, we will prove that a theory T has the DOP for all of the classes K introduced earlier or for none of them. But there is another variant, the ENI-DOP which must be investigated to deal with countable models.

On Perspectives. Mathematical logic arose from a concern with the nature and the limits of rational or mathematical thought, and from a desire to systematise the modes of its expression. The pioneering investigations were diverse and largely autonomous. As time passed, and more particularly in the last two decades, interconnections between different lines of research and links with other branches of mathematics proliferated. The subject is now both rich and varied. It is the aim of the series to provide, as it were, maps of guides to this complex terrain. We shall not aim at encyclopaedic coverage; nor do we wish to prescribe, like Euclid, a definitive version of the elements of the subject. We are not committed to any particular philosophical programme. Nevertheless we have tried by critical discussion to ensure that each book represents a coherent line of thought; and that, by developing certain themes, it will be of greater interest than a mere assemblage of results and techniques.

The books in the series differ in level: some are introductory, some highly specialised. They also differ in scope: some offer a wide view of an area, others present a single line of thought. Each book is, at its own level, reasonably selfcontained. Although no book depends on another as prerequisite, we have encouraged authors to fit their book with other planned volumes, sometimes deliberately seeking coverage of the same material from different points of view. We have tried to attain a reasonable degree of uniformity of notation and arrangement. However, the books in the series are written by individual authors, not by the group. Plans for books are discussed and argued about at length. Later, encouragement is given and revisions suggested. But it is the authors who do the work; if, as we hope, the series proves of values, the credit will be theirs.

History of the Group. During 1968 the idea of an integrated series of monographs on mathematical logic was first mooted. Various discussions led to a meeting at Oberwolfach in the spring of 1969. Here the founding members of the group (R.O. Gandy, A. Levy, G.H. Muller, G. Sacks, D.S. Scott) discussed the project in earnest and decided to go ahead with it. Professor F.K. Schmidt and Professor Hans Hermes gave us encouragement and support. Later Hans Hermes joined the group.

Viewed as a branch of model theory, finite model theory is concerned with finite structures and their properties under logical, combinatorial, algorithmic and complexity theoretic aspects. The connection of classical concerns of logic and model theory with issues in complexity theory has contributed very much and complexity theoretic aspects. The connection of classical concerns of logic and model theory with issues in complexity theory has contributed very much to the development of finite model theory into a field with its own specific flavour.

I like to think of this monograph as a study which — with a particular theme of its own — exemplifies and reflects some central ideas and lines of research in finite model theory. The particular theme is that of bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and corresponding fragments of PTIME. The relations with PTIME exhibit that fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory and, more specifically, of the research programme of descriptive complexity.

Among the main particular topics and techniques I would emphasize:

1. — the importance of games as a fundamental tool from classical logic; their use in the analysis of finite structures also with respect to algorithmic and complexity theoretic concerns is amply illustrated.

2. - the role of cardinality phenomena, which clearly are amongst the most fundamental guidelines in the analysis of finite structures.

3. - the importance of combinatorial techniques, and of dealing with concrete combinatorial problems over finite domains. Examples here range from applications of the stable colouring technique in the formation of structural invariants to certain colourings of squares that come up in canonization for logics with two variables.

In order that this study may be useful also as an introduction to some of the important concepts in the field, I have tried to treat the particular theme in a detailed and mostly self-contained manner. On the other hand this treatment leads up to specific results of a more technical nature, and I welcome the opportunity to present some contributions in a broader context.

We have already remarked that it is clear that every recursive function is computable. The statement that every computable function is recursive is known as Church's Thesis. It was proposed by Church about 1934 and has since come to be accepted by almost all logicians. We shall discuss the reasons for this.

Since the notion of a computable function has not been defined precisely, it may seem that it is impossible to give a proof of Church's Thesis. However, this is not necessarily the case. We understand the notion of a computable function well enough to make some statements about it. In other words, we can write down some axioms about computable functions which most people would agree are evidently true. It might be possible to prove Church's Thesis from such axioms. However, despite strenuous efforts, no one has succeeded in doing this (although some interesting partial results have been obtained).

We are thus reduced to trying to give arguments for Church's Thesis which seem to be convincing. We shall briefly examine these arguments.

The first argument is that all the computable functions which have been produced have been shown to be recursive, using, for the most part, the techniques which we have already described. Moreover, all the known techniques for producing new computable functions from old ones (such as definition by induction or by cases) have been shown to lead from recursive functions to recursive functions.

Another argument comes from various attempts to define computable precisely. We have seen two of these: the definition by means of the basic machine and the definition by means of recursively closed classes (see Proposition 8.3). There are many others, some similar to these two and some quite different. In every case, it has been proved that the class of functions so defined is exactly the class of recursive functions. This at least shows that the class of recursive functions is a very natural class; and it is hard to see why this should be so unless it is indeed the class of computable functions.