We investigate various strong notions of rigidity for Souslin trees, separating them under ⟡ into a hierarchy. Applying our methods to the automorphism tower problem in group theory, we show under ⟡ that there is a group whose automorphism tower is highly malleable by forcing.

Let PA be the theory of first order Peano arithmetic, in the language L with binary operation symbols + and ·. Let N be the theory of the standard model of PA. We consider countable models M of PA such that the universe ∣M∣ is ω. The degree of such a model M, denoted by deg(M), is the (Turing) degree of the atomic diagram of M. The results of this paper concern the degrees of models of N, but here in the Introduction, we shall give a brief survey of results about degrees of models of PA.

Let D0 denote the set of degrees d such that there is a nonstandard model of M of PA with deg(M) = d. Here are some of the more easily stated results about D0.

(1) There is no recursive nonstandard model of PA; i.e., 0 ∈ D0.

This is a result of Tennenbaum [T].

(2) There existsd ∈ D0such thatd ≤ 0′.

This follows from the standard Henkin argument.

(3) There existsd ∈ D0such thatd < 0′.

Shoenfield [Sh1] proved this, using the Kreisel-Shoenfield basis theorem.

(4) There existsd ∈ D0such thatd′ = 0′.

Jockusch and Soare [JS] improved the Kreisel-Shoenfield basis theorem and obtained (4).

(5) D0 = Dc = De, where Dc denotes the set of degrees of completions of PA and De the set of degrees d such that d separates a pair of effectively inseparable r.e. sets.

Solovay noted (5) in a letter to Soare in which in answer to a question posed in [JS] he showed that Dc is upward closed.

If L is a first-order language, then an L-structure A is called quantifier-eliminable (QE) if every L-formula is equivalent in A to a formula without quantifiers.

The classification problem for QE groups and rings has received attention in work by Berline, Boffa, Cherlin, Feigner, Macintyre, Point, Rose, the present authors, and others. In [1], Berline and Cherlin reduced the problem for rings of prime characteristic p to that for nilrings, but also constructed countable QE nilrings of characteristic p. Likewise, in [3], we constructed countable QE nil-2 groups. Both results can be viewed as “nonstructure theorems”, in that they provide negative evidence for any attempt at classification. In the present paper we show that the situation is equally bad (or rich, depending on one's point of view) for commutative rings:

Theorem 1. For any odd prime p, there existcountable QE commutative nilrings of characteristic p.

This solves a problem posed in [1]. We remark that the examples we produce are uniformly locally finite, hence ℵ0-categorical. A more algebraic description is that each of our rings R is uniformly locally finite (in fact, R3 = 0) and homogeneous, in the sense that any isomorphism of finitely generated subrings extends to an automorphism of R.

Theorem 1 does not cover the case p = 2, and we show that for commutative rings this case is in fact exceptional:

Theorem 2. There exist exactly two nonisomorphic countably infinite QE commutative nilrings of characteristic 2.

We define a quasi-order on Borel functions from a zero-dimensional Polish space into another that both refines the order induced by the Baire hierarchy of functions and generalises the embeddability order on Borel sets. We study the properties of this quasi-order on continuous functions, and we prove that the closed subsets of a zero-dimensional Polish space are well-quasi-ordered by bi-continuous embeddability.

As those of us who instruct him are well aware, customary accounts of validity and implication for quantificational logic often bewilder the novice. For his benefit, I present here an account of validity, due (in effect) to the late E. W. Beth, and two accounts of implication, one my own, the other Jaakko Hintikka's, which add up to what the better textbooks say, but, making no mention whatever of domains, say it far more simply.

In the first paper of the above main title, one of us has proved that any formula of the first order predicate calculus is equivalent (as to being satisfiable or not) to some binary first order formula having a prefix of the form (Ex1)(x2)(Ex3) … (xn) and containing a single predicate variable. This result is an improvement of a theorem of Ackermann stating that any first order formula is equivalent to another with a prefix of the above form but saying nothing about the number of predicate variables appearing therein. Hence the question arises if other theorems reducing the decision problem to the satisfiability question of the first order formulas with a prefix of a special form can be improved in like manner. In the present paper we shall answer this question concerning Gödel's reduction theorem stating that any first order formula is equivalent to another the prefix of which has the form

It is shown lhat no infinite group is interpretable in any structure which is homogeneous in a finite relational language. Related questions are discussed for other ω-categorical structures.

We are concerned in this paper with infinite binary sequences which are noncomplex in the sense that their minimal-program complexity (i.e., the lengths of shortest programs for computing their finite initial segments), as a function of the lengths of their initial segments, grows arbitrarily (in an effective sense) slowly. Indeed, the existence of such sequences which are also nonrecursive raises some interesting questions concerning the notion of computability itself. Our first task is to give a characterization of these sequences which does not directly involve the notions of complexity theory. Although these characterizations do involve the primitives of recursive function theory, they do not involve the types of properties which one usually encounters there. While a closer connection is still hoped for, the lack of one is not entirely unexpected. For example, except for the trivial case of degree 0, there is no general correlation between program complexity and degrees of unsolvability. The reason, roughly, is this: even though the inequality deg (f) ≤ deg (g) expresses the relative information between f and g (in the sense that if one knows g then one can compute f), it is a qualitative sort of information. The minimal-program complexity is used as a measure of algorithmic information content and as such is quantitative.

The second task of this paper is to present an example of one of these sequences which to its credit possesses a fairly long list of interesting properties, not the least attractive of which is that, though nonrecursive, it is very simple to describe. In fact this sequence has occurred previously in the literature. It is the characteristic sequence of the set of busy beaver numbers first studied by T. Rado [13]. Of particular interest to the discussion in the last section of this paper concerning the notion of computability is the fact that all the initial segments of this sequence are computable by arbitrarily short programs each of which is defined on all inputs and runs very quickly.

A first-order theory is companionable if it is mutually model-consistent with a model-complete theory. The latter theory is then called a model-companion for the former theory. For example, the theory of formally real fields is a companionable theory; its model-companion is the theory of real closed fields. If a companionable, inductive theory has the amalgamation property, then its model-companion is actually a model-completion. For example, the theory of fields is a companionable, inductive theory with the amalgamation property; its model-completion is the theory of algebraically closed fields.

The goal of this paper is the characterization, by “algebraic” or “structural” properties, of the companionable, universal theories which satisfy a certain finiteness condition. A theory is companionable precisely when the theory consisting of its universal consequences is companionable. Both theories have the same model-companion if either has one. Accordingly, nought is lost by the restriction to universal theories. The finiteness condition, finite presentation decompositions, is an analogue for an arbitrary theory of the decomposition of a radical ideal in a Noetherian, commutative ring into a finite intersection of prime ideals for the theory of integral domains. The companionable theories with finite presentation decompositions are characterized by two properties: a coherence property for finitely generated submodels of finitely presented models and a homomorphism lifting property for homomorphisms from submodels of finitely presented models.

Predicate-functor logic, as founded by W. V. Quine ([1960], [1971], [1976], [1981]), is first-order predicate logic without individual variables. Instead, adverbs or predicate functors make explicit the permutations and replications of argument-places familiarly indicated by shifting variables about. For the history of this approach, see Quine [1971, 309ff.]. With the evaporation of variables, individual constants naturally assimilate to singleton predicates or adverbs, leaving no logical subjects whatever of type 0. The orphaned “predicates” may then be taken simply as terms in the sense of traditional logic: class and relational terms on model-theoretic semantics, schematic terms on Quine's denotational or truth-of semantics. Predicate-functor logic thus stands forth as the pre-eminent first-order term logic, as distinct from propositional-quantificational logic. By the same token, it might with some justification qualify as “first-order combinatory logic”, with allowance for some categorization of the sort eschewed in general combinatory logic, the ultimate term logic.

Over the years, Quine has put forward various choices of primitive predicate functors for first-order logic with or without the full theory of identity. Moreover, he has provided translations of quantificational into predicate-functor notation and vice versa ([1971, 312f.], [1981, 651]). Such a translation does not of itself establish semantic completeness, however, in the absence of a proof that it preserves deducibility.

An axiomatization of predicate-functor logic was first published by Kuhn [1980], using primitives rather like Quine's. As Kuhn noted, “The axioms and rules have been chosen to facilitate the completeness proof” [1980, 153]. While this expedient simplifies the proof, however, it limits the depth of analysis afforded by the axioms and rules. Mindful of this problem, Kuhn ([1981] and [1983]) boils his axiom system down considerably, correcting certain minor slips in the original paper.

In this paper the existence or nonexistence of isomorphic mappings between graph models for the untyped lambda calculus is studied. It is shown that Engeler's is DA completely determined, up to isomorphism, by the cardinality of its ‘atom-set’ A. A similar characterization is given for a collection of graph models of the -type; from this some propositions regarding automorphisms are obtained. Also we give an indication of the complexity of the first-order theory of graph models by showing that the second-order theory of first-order definable elements of a graph model is first-order expressable in the model.

Let ZF denote Zermelo-Fraenkel set theory (without the axiom of choice), and let M be a countable transitive model of ZF. The method of forcing extends M to another model M[G] of ZF (a “generic extension”). If the axiom of choice holds in M it also holds in M[G], that is, the axiom of choice is preserved by generic extensions. We show that this is not true for many weak forms of the axiom of choice, and we derive an application to Boolean toposes.

In this paper, by a function of ordinals we understand a function which is defined for all ordinals and each of whose value is an ordinal. In [7] (also cf. [8] or [9]) we defined recursive functions and predicates of ordinals, following Kleene's definition on natural numbers. A predicate will be called arithmetical, if it is obtained from a recursive predicate by prefixing a sequence of alternating quantifiers. A function will be called arithmetical, if its representing predicate is arithmetical.

The cardinals are identified with those ordinals a which have larger power than all smaller ordinals than a. For any given ordinal a, we denote by the cardinal of a and by 2a the cardinal which is of the same power as the power set of a. Let χ be the function such that χ(a) is the least cardinal which is greater than a.

Now there are functions of ordinals such that they are easily defined in set theory, but it seems impossible to define them as arithmetical ones; χ is such a function. If we define χ in making use of only the language on ordinals, it seems necessary to use the notion of all the functions from ordinals, e.g., as in [6].

Let E be a equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0* exists or if V is a forcing extension of L, then there is a good well-ordering of the equivalence classes.

A generic computation of a subset A of ℕ is a computation which correctly computes most of the bits of A, but which potentially does not halt on all inputs. The motivation for this concept is derived from complexity theory, where it has been noticed that frequently, it is more important to know how difficult a type of problem is in the general case than how difficult it is in the worst case. When we study this concept from a recursion theoretic point of view, to create a transitive relationship, we are forced to consider oracles that sometimes fail to give answers when asked questions. Unfortunately, this makes working in the generic degrees quite difficult. Indeed, we show that generic reduction is $\Pi _1^1$―complete. To help avoid this difficulty, we work with the generic degrees of density-1 reals. We demonstrate how an understanding of these degrees leads to a greater understanding of the overall structure of the generic degrees, and we also use these density-1 sets to provide a new a characterization of the hyperartithmetical Turing degrees.

An initial segment of hyperdegrees is a set S of hyperdegrees such that whenever h ∈ S and k ≦ h then k ∈ S. The main results of this paper affirm the existence of initial segments having certain order types. In particular, if L is a finite distributive lattice then L is isomorphic to an initial segment of hyperdegrees [Theorem 1]; as a consequence the elementary theory of the ordering of hyperdegrees is recursively undecidable [Corollary 1].

This paper is a survey and a synthesis of the various approaches to defining algebraic elements. Most of it is devoted to proving the following result.

Let T be a universal theory with the Amalgamation Property. Then for T the notions of algebraic element introduced by Robinson, Jónsson, and Morley are identical. Furthermore, they extend in a natural way the notion of algebraic element introduced by Park, and used by Lachlan and Baldwin and by Kueker.

In the course of proving this we shall construct the algebraic closure as a suitable injective hull and prove a unique factorisation theorem for algebraic predicates.

We shall also show (in §3) that if T is closed under products then algebraic elements all have degree 1. Thus in algebra, algebraic elements reduce to epimorphisms.

To demonstrate the remarkable stability of the notion we shall show (at the end of §5) that defining algebraic elements by infinitary formulas yields no new ones.

Let L be a language. The cardinality of the set of formulas of L is denoted by ∣L∣. An L-theory is a deductively closed set of L-sentences. We let denote the category of models of T and (L-structure) homomorphisms between them. If A is a substructure of B we write A ≤ B. We call u: A → B an injection if u is an isomorphism of A with a substructure of B, and let denote the subcategory of consisting of all injections.

In this paper we investigate the possibility of extending Friedberg's enumeration of the recursively enumerable (r.e.) sets without duplication [1, p. 312] to meta-recursion theory. It turns out that all of our proposed extensions are impossible save one: the metarecursively enumerable (meta-r.e.) sets can be enumerated without duplication, but only if all the recursive ordinals are used as indices (Theorems 1 and 2). The sets cannot be so enumerated, even if the index set is all recursive ordinals (Theorems 3 and 4). As a corollary, one proves there is no predicate P(n, x) with the property that for each set A there is exactly one integer n for which A = {x ∣ P(n, x)}. We also discuss enumerations of nonempty, infinite, and coinfinite and meta-r.e. sets.

We use axioms of abstract ternary relations to define the notion of a free amalgamation theory. These form a subclass of first-order theories, without the strict order property, encompassing many prominent examples of countable structures in relational languages, in which the class of algebraically closed substructures is closed under free amalgamation. We show that any free amalgamation theory has elimination of hyperimaginaries and weak elimination of imaginaries. With this result, we use several families of well-known homogeneous structures to give new examples of rosy theories. We then prove that, for free amalgamation theories, simplicity coincides with NTP2 and, assuming modularity, with NSOP3 as well. We also show that any simple free amalgamation theory is 1-based. Finally, we prove a combinatorial characterization of simplicity for Fraïssé limits with free amalgamation, which provides new context for the fact that the generic Kn-free graphs are SOP3, while the higher arity generic $K_n^r$-free r-hypergraphs are simple.