Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely:

Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.

It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].

κ-saturation [SL] is probably the single most useful property of nonstandard models of analysis. For some applications, however, stronger saturation hypotheses seem necessary. Henson formulated his elegant κ-isomorphism property (see [H1], and §2 below) to address this need. This property, though well-suited to certain situations (notably those arising in Banach space theory), is often difficult to apply in practice (see [SL, §7.7]).

In this paper I describe an alternative to κ-isomorphism which is much easier to use; in particular, a proof which assumes that the nonstandard model is fully saturated can usually be converted directly to one using this special model axiom.

Precise definitions of both these axioms appear in §2. In §3 I prove some simple properties of the special model axiom, one of which is that it is at least as strong as κ-isomorphism. In §§4, 5, and 6 the axiom is used to construct a few examples, many of which are pathological, or at the very least counterintuitive. (These examples are given primarily to illustrate use of the axiom; the only one of independent interest is Theorem 5.5.) In §7 some alternative axioms and open problems are discussed.

Many of the results in this paper grew out of discussion and correspondence with C. Ward Henson, to whom I am consequently most grateful.

We show that the structure (C, +, ·) has no proper non locally modular reducts which contain +. In other words, if X ⊂ Cn is constructible and not definable in the module structure (C, +, λa)a Є C (where λa denotes multiplication by a) then multiplication is definable in (C, +, X).

Recursion theory has been dominated by one example. The notion of a dominical category was introduced (see [2] and [3]) at least in part in the hope of subverting this dominance. The structures of number theory, freed from this original context, led to much of modern algebra with a consequent enrichment of number theory itself: it seemed not unreasonable to attempt to contribute, however modestly, to a similar development of recursion theory. Thus (in the loosest sort of analogy) recursion categories are intended to stand in relation to the class of partial recursive functions as rings do to the rational integers.

But if such a generalization is to serve its intended purpose, it ought to allow examples substantially different in spirit from the prototype. Recursion categories are, of course, the proper generalization of classical recursion theory. As a novice in this formidable field I am incapable of encompassing its full extent and must rely on the advice of others (I thank in particular R. DiPaola) in concluding that most of these earlier generalizations are not of this character. Indeed, the examples of recursion categories so far adduced (cf., in addition to the references above, [1] and [4]) are themselves closely tied to the classical one.

We attempt here to open the door to radically disparate examples by proving an existence theorem allowing the construction of recursion categories in a wide, and so far unexplored, variety of contexts very distant from that of the natural or ordinal numbers and their subsets, the locus of the traditional theory.

In order to do this, it has been necessary to introduce a number of unfamiliar notions—unfamiliar, that is, even in the context of the earlier discussion of dominical categories. This novelty is perhaps mitigated by the fact that, however unfamiliar, they cannot be said to be unusual, as the discussion later will show. We mention in particular those of a “formally free semigroup”, which retains the indexation function of a free semigroup, while giving up the characteristic universal property and that of “uniform generation”, which generalizes finite generation in the fashion assorted to our argument.

Church's simple theory of types is a system of higher-order logic in which functions are assumed to be total. We present in this paper a version of Church's system called PF in which functions may be partial. The semantics of PF, which is based on Henkin's general-models semantics, allows terms to be nondenoting but requires formulas to always denote a standard truth value. We prove that PF is complete with respect to its semantics. The reasoning mechanism in PF for partial functions corresponds closely to mathematical practice, and the formulation of PF adheres tightly to the framework of Church's system.

We define a rich model to be one which contains a proper elementary substructure isomorphic to itself. Existence, nonstructure, and categoricity theorems for rich models are proved. A theory T which has fewer than min(2λ, ℶ2) rich models of cardinality λ (λ > ∣T∣) is totally transcendental. We show that a countable theory with a unique rich model in some uncountable cardinal is categorical in ℵ1 and also has a unique countable rich model. We also consider a stronger notion of richness, and use it to characterize superstable theories.