Elementary Induction on Abstract Structures

INTRODUCTION

One of the chief concerns of logic is the study of those relations on an abstract structure which are explicitly definable in the first order language of . We study here the relations on which are inductively definable in the same language.

Consider first a typical example of the kind of inductive definition we have in mind.

Let be a group and b1, . . ., bk fixed members of G, and take

H = [b1, . . ., bk] = the subgroup generated by b1 , . . ., bk.

There are two traditional ways of defining this notion in an algebra course.

One is to say that H is the least subset of G which satisfies

Putting

we have the explicit definition

The other method is to define by induction the sets ,

and put

It is an easy exercise to show that both definitions yield the same set. The advantage of the first method is that it yields an explicit definition for H—but notice that this is in the second order language over the group structure . The second approach makes clear that there is an induction involved in the definition and appears to be more constructive.

From our point of view the significant observation is that with either explication the clauses (1), (2) of the induction are in the first order language over . Equivalently, the formula φ(x, S) is elementary over . Moreover, the relation variable S occurs positively in φ(x, S); it is not hard to see that whenever we have clauses like (1), (2) then the formula that combines them will be positive in the relation variable of the induction.

In the most general case we will study, there will be a formula

in the first order language of a structure , with n free variables and only positive occurrences of the n-ary relation variable S. The set built up by φ is defined explicitly by

The second approach of the example may lead to a transfinite induction in the general case,

but as in the example, the two methods lead to the same set,

These sets of the form Iφ that come directly from inductions are the fixed points of the structure . We will call a relation R on A inductive on if there is a fixed point Iφ and constants ā = a1, . . ., ak in A such that

i.e., the inductive relations are those reducible to fixed points. Finally the hyperelementary relations will be those which are inductive and have inductive complements.

One meets inductive and hyperelementary relations in practically every field of mathematics. The examples in algebra are rather obvious, e.g. the algebraically closed subfield of F generated by b1, . . ., bk is inductive in the field structure of an algebraically closed field F.

In logic, perhaps the typical example is the truth set for arithmetic,

which is hyperelementary.

In set theory we can cast all transfinite recursions in this form; for example, if

is the Gödel function enumerating the constructible sets of order less than the infinite cardinal λ, then the relation

is hyperelementary on the structure .

Finally in recursion theory, the basic definitions in the theories of constructive ordinals and recursion in higher types are the most obvious important examples, but of course inductive definitions of various types pervade the whole subject.

It is perhaps amusing that a notion which appears to be fundamental and widely applicable has not been explicitly isolated in any published paper that we can find. The very recent papers Grilliot [1971], Barwise–Gandy–Moschovakis [1971], Moschovakis [1970] and [1971a] come close to an abstract approach, but they only study rather special structures. In fact, in Barwise–Gandy–Moschovakis [1971] we read "given a set A equipped with some recursion theoretic structure, one can attempt to formulate. . .". Before these, the most general attack on the problem is Spector’s fundamental [1961] where he defines and studies extensively the inductive relations on the structure of arithmetic.

But the preceding paragraph is very bad history. Specifically for the structure of arithmetic, long before Spector’s [1961] Kleene had obtained all the key results in the pioneering papers [1944], [1955a], [1955b], [1955c]. In these, Kleene is consciously studying inductive definitions, even though he explicitly draws back from considering all of them in [1944]. But the special cases he studies are so general, that Spector credits to Kleene the fact that the inductive sets on the integers are precisely the sets. This means that the hyperelementary sets are the sets which Kleene had already identified with the hyperarithmetical sets and which he had studied exhaustively.

Thus for the special case of the structure of the integers our subject specializes to the fully developed and justly acclaimed theory of and hyperarithmetical sets. The approach to this theory through inductive definitions was not made explicit until Spector’s [1961] and was not followed up very much after that, simply because Kleene and his students and followers looked at the subject as recursion theorists and chose to formulate their results in recursion theoretic rather than model theoretic terms.

The theory was extended to almost arbitrary structures in Moschovakis [1969a], [1969b], [1969c]. Here again the approach was entirely recursion theoretic in form, so much so that the identification of semihyperprojective relations with the inductive relations of the appropriate structure was only added as an afterthought in Remark 21 of the revised version of [1969b]. Nevertheless, the introduction to [1969a] says the main technical contribution of this paper is the introduction and systematic exploitation of existential, nondeterministic clauses in inductive definitions, i.e. again the results were mostly about inductive definability even though they were cast in recursion theoretic terms.

During UCLA’s Logic Year 1967–1968, Gandy argued repeatedly and forcefully that the key notion of abstract recursion theory should be that of an inductive definition. There is a counterargument to this, that recursion theory should have something to say about computations. Nevertheless, it was obvious that it would be useful to have a development of the theory in Moschovakis [1969a], [1969b], [1969c] from the point of view of inductive definability, as many of the recursion theoretic arguments and methods of these papers seemed somehow irrelevant to the main results. To do this is one of our aims here.

One of the important tools for an exposition of these results from a model theoretic, inductive definability approach is the introduction and systematic exploitation of open games. There was a glimpse of this idea in the last section of Moschovakis [1969b] titled A game theoretic characterization of semi-hyperprojective sets, but some of the missing tricks did not become available until Moschovakis [1970] and [1971a]. This allowed for a neat exposition of most of the first two papers [1969a] and [1969b].

The present work was motivated by some further extensions of these game theoretic ideas which yielded fairly comprehensible proofs of the rather delicate theorems in the third paper [1969c]—this was where we generalized Kleene’s deepest results on the hyperarithmetical sets in Kleene [1959a].

A byproduct of attempting to lecture on these matters in a seminar was the somewhat surprising discovery that a very substantial part of the theory of inductive and hyperelementary sets goes through for completely arbitrary structures. This comprises the first four chapters here. Afterwards we specialize to acceptable structures and then in Chapter 8 to countable acceptable structures, but even then the flavor is decidedly model theoretic and there are no explicit references to recursion theory. In Chapter 9 we prove a very general version of the main result of Barwise–Gandy–Moschovakis [1971] which is the key to many applications of the present methods to abstract recursion theory.

The exercises at the end of each chapter are an integral part of the text. They give a stock of examples to keep in mind as we develop the general theory, they outline extensions of this theory and they also establish a link between the abstract approach here and the more familiar development of the theory of hyperarithmetical and sets of integers.

The text is technically accessible to a student who is familiar with the basic notions of logic, model theory and set theory, the material usually covered in the first semester of a graduate or advanced undergraduate logic course. Some of the exercises require a deeper knowledge of set theory. However, the motivation and some of the implications of the results will be better understood by those students who have some acquaintance with the classical theory of recursive and hyperarithmetical sets, e.g. as developed in Rogers [1967] and Shoenfield [1967].

I have tried hard to attribute all results and ideas to the mathematicians who first discovered them, but the task is difficult and I am sure that there are both errors and omissions.

Much of the exciting current research in abstract recursion theory is concerned with very general inductions—nonmonotone inductive definitions and definitions in very restricted or very rich languages. We hope that this work will provide a point of reference by giving a neat exposition of the simplest and most developed part of the theory of inductive definability. We also have hopes that the model theorists may find something to interest them here, both in the results and in some of the methods.

CHAPTER 1

POSITIVE ELEMENTARY INDUCTIVE DEFINITIONS

In this first chapter we introduce the classes of inductive and hyperelementary relations on a structure, we prove some of their simple properties and we discuss briefly some important examples of the theory.

1A. Monotone operators

Let A be an infinite set. We use a, b, c, . . ., x, y, z, . . . to denote members of A and P, Q, R, . . . to denote relations on A of any (finite) number of arguments. Barred letters will denote finite sequences from A, e.g.

If P ⊆ An is an n-ary relation and an n-tuple, we write interchangeably

The cardinal number of a set X is |X|, so in particular for every n 1,

|An| = |A|,

since A is infinite. If λ is an ordinal number, then

λ+ = least cardinal number greater than λ.

An operator

Γ: Power (An) → Power (An)

is monotone if it preserves inclusion, i.e.

For each such monotone Γ and each ordinal ξ we define the set by the transfinite recursion

Of course each is an n-ary relation on A. We let

be the relation defined inductively by Γ, or simply the set built up by Γ.

It is also convenient to put

so that for each ξ,

1A.1. THEOREM. Let A be an infinite set, let Γ be a monotone operator on the n-ary relations on A, let , IΓ be defined as above.

(i) If .

(ii) For some ordinal κ of cardinality |A|,

we call the least such κ the closure ordinal of Γ, κ = ||Γ||.

(iii) The set built up by Γ is the smallest fixed point of Γ, i.e.

PROOF, (i) follows directly from the monotonicity of Г, since for ζ ξ,

To prove (ii) notice that if we had

for every ξ < |A|+, then we could choose some

for each ξ < |A|+ and then the set

would be a subset of An of cardinality which is absurd. Hence for some κ < |A|+ we have

from which an immediate transfinite induction shows that for every ξ κ, .

This argument also proves part of (iii), that IΓ is a fixed point of Γ, since if κ is the closure ordinal we have

On the other hand, if P is any fixed point, i.e.

Γ(P) = P,

we can show by transfinite induction on ξ that

because

using the induction hypothesis and the monotonicity of Γ. Hence .     

1B. Relative positive inductive definability

Again let A be an arbitrary set. We will be working with formulas of the lower predicate calculus with individual and relation constants from A, call it . More precisely, the language has an infinite list of individual variables x, y, z, . . ., a constant c for each element c of A, an infinite list S, T, U, . . . of n-ary relation variables for each n 1, a constant relation symbol P for each relation P on A, in particular the identity symbol =, and the usual logical symbols ¬, &, ∨, →, ∃, ∀. Formulas are defined as usual, with the quantifiers ∃, ∀ applied only to the individual variables—this is a first order language. Individual terms are the individual variables and constants and relation symbols are the relation variables and constants. Relation variables are always free. Formulas of with no free variables of either kind are called sentences; they are either true or false under the natural interpretation of this language.

We write

φ ≡ ψ

to indicate that "φ and ψ" are names of the same formula. This meta-mathematical convention is useful in defining formulas and establishing notation.

Let S be a relation symbol. The class of formulas in which S occurs positively, briefly S-positive formulas, is the smallest collection of formulas with the following properties:

(i) All formulas in which S does not occur are in .

(ii) If S is n-ary and is an n-tuple of individual terms, then the formula is in .

(iii) If φ, ψ are in and x is any variable, then φ & ψ, φ ∨ ψ, (∃x)φ, (∀x) are all in .

An easy induction on the length of formulas proves the following.

1B.1. MONOTONICITY PROPERTY OF POSITIVE FORMULAS. Suppose S is an n-ary variable which occurs positively in φ(S) and suppose no other variable of either kind occurs free in φ(S). If P, P′ are n-ary relations on A, then

if P ⊆ P′ and φ(P), then φ(P′)     

Here of course φ(P) is the result of substituting the relation constant P for the relation variable S in φ(S) and similarly for P′.

Suppose now that A is infinite. An operator

Γ: Power(An) → Power(An)

is positive elementary in Q1, . . ., Qm if there is a formula

such that the following conditions hold:

(i) The relation constants which occur in are among =, Q1, . . ., Qm and the only relation variable of is the n-ary variable S.

(ii) The symbols S, Q1, . . ., Qm all occur positively in .

(iii) The free individual variables of are among x1, . . ., xn.

(iv) The formula defines Γ, i.e. for each S ⊆ An,

Notice that we allow individual constants in as well as arbitrary occurrences of =, but we insist that all the other relation symbols occur positively.

It is immediate from the monotonicity property of positive formulas that if Γ is positive elementary, then Γ is monotone. If φ ≡ defines Γ in the sense of (i)–(iv) above, it is convenient to put

we then have for each ordinal ξ,

and

We call Iφ the set built up by φ.

An n-ary relation R on A is positive elementary inductively definable in Q1, . . ., Qm, or simply inductive in Q1, . . ., Qm, if there are constants ā = a1, . . ., ak in A and an operator

Γ: Power(Ak+n) → Power(Ak+n)

which is positive elementary in Q1 . . ., Qm, such that

By the definition above, we then have a formula

in which the only relation symbols that occur are those that show, and except for = they all occur positively, such that

The constants ā are called the parameters of the induction, but recall that there may be other individual constants occurring in φ.

We can picture the construction of the fixed point Iφ in the plane and the definition of R from Iφ by projection along the -axis as shown in Fig. 1.1.

Fig. 1.1.

We are mostly concerned in this book with inductive definability on a structure which is a bit different from the notion above and which we will define in Section 1D. However, the present notion is more