In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (Δ 0sets). To get the results we study properties of chains of finite automata.

A standard result about hyperdegrees is proved (under PD) for all Δ 2n+1 1-degrees.

This is the first of two papers based on Chapter V of the author's Ph.D. thesis [K1]. The second paper [K3] will deal with a specific application of the ideas presented here to the study of modules, mostly to questions concerning the complexity of injective modules over a commutative Noetherian ring.

In [D], R. Deissler introduced a “minimality rank” which I denote by “rk” here. This rank provides an ordinal measure on the difficulty of defining a given element b in a structure ℳ, allowing the use of parameters from definable subsets of ℳ. If A ⊂ M, rk(b, A, ℳ) = 0 if b is definable in ℳ by a formula with parameters from A. Roughly speaking, in the general case rk(b, A, ℳ) measures how hard we have to work at adding new parameters to A (from sets definable over A in ℳ) in order to be able to define b. “rk” is called a “minimality rank” because of the following: ℳ is a minimal model of the complete theory T = Th(ℳ) iff rk(b, Ø, ℳ) < ∞ for every b ∈ M. Deissler's rank was studied further by R. Woodrow and J. Knight [WK]. They improve on an example given by Deissler. The construction that they present illustrates well the difficulties and subtleties involved in exact calculations of rk.

The central concept underlying Deissler's rank is that of a definable set. In §1 I introduce the idea of a context for definability Φ(x). A set B is Φ-definable over A if for some formula and . For Deissler's rank, Φ is the set of all formulas; for rk+ used in the study of modules, Φ + is the set of all positive primitive formulas. Associated with each Φ is a relation ≺Φ between structures which says that Φ-definitions are preserved. In §1 I develop the basic properties of these two concepts and give a list of examples.

This is the second of two papers based on Chapter V of the author's Ph.D. thesis [K1]. For acknowledgements please refer to [K3]. In this paper I apply some of the ideas and techniques introduced in [K3] to the study of a very specific example. I obtain an upper bound for the positive Deissler rank of an injective module over a commutative Noetherian ring in terms of Krull dimension. The problem of finding lower bounds is vastly more difficult and is not addressed here, although I make a few comments and a conjecture at the end.

For notation, terminology and definitions, I refer the reader to [K3]. I also use material on ideals and injective modules from [N] and [Ma]. Deissler's rank was introduced in [D].

For the most part, in this paper all modules are unitary left modules over a commutative Noetherian ring Λ but in §1 I begin with a few useful results on totally transcendental modules and the relation between Deissler's rank rk and rk+.

Recall that if P is a prime ideal of Λ, then an ideal I of Λ is P-primary if I ⊂ P, λ ∈ P implies that λn ∈ I for some n and if λµ ∈ I, λ ∉ P, then µ ∈ I. The intersection of finitely many P-primary ideals is again P-primary, and any P-primary ideal can be written as the intersection of finitely many irreducible P-primary ideals since Λ is Noetherian. Every irreducible ideal is P-primary for some prime ideal P. In addition, it will be important to recall that if P and Q are prime ideals, I is P-primary, J is Q-primary, and J ⊃ I, then Q ⊃ P. (All of these results can be found in [N].)

I present solutions to several questions of Paul Bankston [2] by means of another version of the ultracoproduct construction, and explain the relation of ultracoproduct of compact Hausdorff spaces to other constructions combining topology, algebra and logic.