This is the first part of a series of papers on certain topics of model theory of modules, which will further consist of Part II. On stability and categoricity of flat modules and Part III. On infiniteness of sets definable in modules. Although these parts are only weakly connected, it is convenient to have common background and notation. The first part was written in Summer 1980, when I did not know about either footnote (3) appearing in the final version of [GA 2] or about the work of the “Bedford College Group” concerning stability theory of modules. I would like to thank Wilfrid Hodges and Mike Prest for their interest in this note, which encouraged me to include it as the first part of the present series, and for acquainting me with their unpublished work, to which I refer in footnotes. I should also like to thank the referee for his suggestions, in particular for correcting the argument in Remark (5) and for drawing my attention to [Z-H].

A syntactical analysis of Zimmermann's notion of “endlich matriziellen Untergruppen” of modules [ZI, p. 1087] shows that it coincides with the notion of subgroups definable by positive primitive formulae (without parameters) [GA 1, p. 80]. Then combination of [ZI, Folgerung 3.4] with [GA 1, Lemma 5] (or [GA 2, Theorem 1] for uncountable rings) yields purely algebraic criteria for total transcendence of modules. I present here a proof of this result using only the following facts.

(G1) A module M is totally transcendental iff it satisfies the minimal condition on subgroups definable by positive primitive formulae (without parameters) [GA 1, Lemma 5] (and [GA 2, Theorem 1] for uncountable rings).

Cette note est une suite à mon article Théories instables, this Journal, vol. 46 (1981), pp. 513–522. Quand il en a eu pris connaissance, Saharon Shelah–et c'est remplir un devoir agréable que de lui témoigner ici ma reconnaissance pour l'intérêt qu'il porte à mes travaux–m'a fait savoir qu'il pouvait en simplifier les résultats, et a publié le Théorème 1 de ce post-scriptum, pour le cas des cohéritiers, dans les “added in proof” de son Simple unstable théories, Annals of Mathematical Logic, vol. 19 (1980), pp. 177–203, plusieurs mois avant que ne paraisse l'article qu'il améliore. On verra ici que ce théorème se généralise sans problème aux fils spéciaux, et que son corollaire, le Théorème 2, représente un net progrès sur mon résultat original, puisqu'il est à la fois plus général, plus précis, et obtenu à moindre frais, le lemme sur les ultrafiltres devenant inutile.

Quelques rappels pour commencer: je considère une théorie complète T, sans propriété d'indépendance; cela signifie que toute suite … ai … indicernable dans l'ordre est insécable, c'est-à-dire qu'il ne peut exister de formule f(x, ȳ) et de paramètres tels que f(ai, ) soit vraie cofinalement, et fausse cofinalement, dans la suite; cela signifie encore que cette suite s est découpée par la formule f(x, ) en un nombre fini de segments S1, …, Sk, la formule prenant la même valeur de vérité dans chaque segment, et des valeurs opposées dans des segments consécutifs; ce nombre k de segments sera appelé nombre d'alternance de la formule f(x, ) sur la suite s. On remarquera que, par compacité, ce nombre d'alternance est majoré en fonction seulement de f(x, ȳ).

The incompleteness of ZF set theory leads one to look for natural extensions of ZF in which one can prove statements independent of ZF which appear to be “true”. One approach has been to add large cardinal axioms. Or, one can investigate second-order expansions like Kelley-Morse class theory, KM. In this paper we look at a set theory ZF(aa), with an added quantifier aa which ranges over ordinals. The “aa” stands for “almost all”, and although we will consider interpretations in terms of the closed unbounded filter on a regular cardinal κ, we will consider other interpretations also.

We start in §1 by giving the axioms for the theory ZF(aa) and presenting a completeness theorem which gives a model-theoretic definition of ZF(aa). In §2 we investigate set theory with a satisfaction predicate and interpret it in a fragment of ZF(aa). In §3 we generalize the methods of §2 to obtain a hierarchy of satisfaction predicates. We use these predicates to prove reflection theorems, as well as to prove the consistency of certain fragments of ZF(aa). Next, in §4 we discuss expandability of models of ZF to models of fragments of ZF(aa) and of Kelley-Morse. We conclude in §5 with a discussion of an extension ZF(aa) + DET of ZF(aa) in which the quantifier aa is self-dual.

This is the second part of a study on model theory of modules begun in [RO]. Throughout, I refer to that paper as “Part I”. I observed there a coincidence between some algebraic and logical points of view in the theory of modules, which led to a convenient representation of p.p. definable sets in flat modules (§1); it becomes especially nice in the case of regular rings (cf. Remark 7 in Part I). Using this in the present paper I obtain a simplified criterion for total transcendence and superstability in the case of flat modules. This enables me to give, besides partial results for arbitrary flat modules (§2), a complete description of the stability classes for modules over regular rings (§3). Particularly, it turns out that a totally transcendental module over a regular ring can be regarded as a module over a semisimple ring (cf. Remark 10 in Part I). This is the crucial observation for the examination of categoricity here: By Morley's theorem, a countable ℵ1-categorical theory is totally transcendental. Consequently, an ℵ1-categorical module over a countable regular ring can be regarded as a module over a semisimple ring. That is why I separately treat categoricity of modules over semisimple rings (§4), even without any assumption on the power of the ring. As a consequence I obtain a complete description of ℵ1-categorical modules over countable regular rings (§5). In the investigation presented here the main tool is the technique of idempotents avoiding the commutativity assumption made in the corresponding results of Garavaglia [GA 1, pp. 86–88], who used maximal ideals for that purpose. At the end of the present paper I show how to derive these latter results in our context.

On the way I simplify the known criterion for elementary equivalence for modules over regular rings (§3), which simplifies again in case of semisimple rings (§4). Such a criterion is needed in order to construct Vaughtian pairs (in the categoricity consideration) and it turns out to be useful also for another purpose treated in the third part of this series of papers.

In [10] Friedman showed that (-AC) is a conservative extension of (-CA)<ε0 for -sentences where i = min(n + 2, 4), i.e., i = 2, 3, 4 for n = 0, 1, 2 + m. Feferman [5], [7] and Tait [11], [12] reobtained this result for n = 0, 1 and even with (-DC) instead of (-AC). Feferman and Sieg established in [9] the conservativeness of (-DC) over (-CA)<ε0 for -sentences (i as above) for all n. In each paper, different methods of proof have been used. In particular, Feferman and Sieg showed how to apply familiar proof-theoretical techniques by passing through languages with Skolem functionals.

In this paper we study the same choice principles in the presence of the Bar Rule (BR), which permits one to infer the scheme of transfinite induction on a primitive recursive relation ≺ when it has been proved that ≺ is wellfounded. The main result (Theorem 1 below) characterizes (-DC) + (BR) as a conservative extension of a system of the autonomously iterated -comprehension axiom for -sentences (i depending on n as above). For n = 0 this has been proved by Feferman in the form that (-DC) + (BR) is a conservative extension of (-CA)<Γ0; this was first done in [8] by use of the Gödel functional interpretation for the stronger system Zω + μ + (QF-AC) + (BR) and then more recently by the simpler methods of [9]. Jäger showed how the latter methods could also be used to obtain the general result of Theorem 1 below.

A modal theory Z using the Guaspari witness comparison signs ≤, < is developed. The theory Z is similar to, but weaker than, the theory R of Guaspari and Solovay. Nevertheless, Z proves the independence of the Rosser fixed-point. A Kripke semantics for Z is presented and some arithmetical interpretations of Z are investigated. Then Z is enriched to ZI by adding a new modality sign for interpretability and by axioms expressing some facts about interpretability of theories. Two arithmetical interpretations of ZI are presented. The proofs of the validity of the axioms of ZI in arithmetical interpretations use some strengthening of Solovay's result about interpretability in Gödel-Bernays set theory.

We see far away, Newton said, if we stand on giants' shoulders. We take him seriously here and moreover (as appropriate to recursion-theorists) we will jump from one giant to another, since this paper is mostly an exegesis of two fundamental works: Feferman's Some applications of the notions of forcing and generic sets [4] and Sacks' Forcing with perfect closed sets [19]. We hope the reader is not afraid of heights: our exercises are risky ones, since the two giants are in turn on the shoulders of others! Feferman [4] rests on the basic works of Cohen [2], who introduced forcing with finite conditions in the context of set theory; Sacks [19] relies on Spector [24], who realized—in recursion theory—the necessity of more powerful approximations than the finite ones.

To minimize the risk we will try to keep technicalities to a minimum, choosing to give priority to the methodology of forcing. We do not suppose any previous knowledge of forcing in the reader, but we do require some acquaintance with recursion theory. After all, our interest lies in the applications of the forcing method to the study of various recursion-theoretic notions of degrees. The farther we go, the deeper we plunge into recursion theory.

In Part I only very basic notions and results are used, like the definitions of the arithmetical hierarchy and of the jump operator and their relationships.

In this paper we show that it is consistent with ZFC that for any set of reals of cardinality the continuum, there is a continuous map from that set onto the closed unit interval. In fact, this holds in the iterated perfect set model. We also show that in this model every set of reals which is always of first category has cardinality less than or equal to ω1.

Indecomposability of ultrafilters was introduced by Keisler as a natural weakening of the concept of measurability. The property was first studied in depth by Chudnovsky and Chudnovsky, Prikry, and Silver (see [4] and [5]). One intriguing result of this early work was the following theorem: if κ is an inaccessible cardinal and there is an indecomposable ultrafilter over κ, then κ is in fact ω-Mahlo. Silver asked whether this result could be strengthened to say that an inaccessible cardinal carrying an indecomposable ultrafilter must be measurable. We prove in this paper that this is not the case; we construct a model where κ is inaccessible and carries an indecomposable ultrafilter but κ is not even weakly compact.

The results in this paper form part of the research for my doctoral dissertation at the University of California, Berkeley. I would like to thank my thesis advisor, Robert Solovay, for his patient guidance during this endeavor.

In [1978] Harrington and MacQueen proved that if B is an (A, E)-semirecursive subset of A, such that the functions in BA can be coded as elements of A in an (A, E)-recursive way, then ENV(A, E) is closed under the existential quantifier ∃T ∈ B.

Later Moschovakis showed that if ENV(Vκ, ∈, E) is closed under the quantifier ∃t ∈ λ, where λ is the p-cofinality of κ, then

the p-cofinality of κ is the least ordinal λ for which there exists a (κ, <, E)-recursive partial function ƒ into κ, such that ƒ∣λ is total from λ onto an unbounded subset of κ.

In this paper we prove that for any infinite ordinal κ if p-card(κ) = κ, then ENV(κ, <, E) is closed under ∃t ∈ μ, for μ < p-cf(κ); p-cf(κ) is the “boldface” analog of p-cf((κ) and p-card(κ) is defined similarly.

From this follows that for any infinite ordinal κ the following two statements are equivalent.

(i) ENV(κ, <, E) is closed under bounded existential quantification.

(ii) ENV(κ, <, E) = ENV(κ, <, E#) or p-cf(κ) = κ.

We also show that we cannot omit any of the hypotheses in the above theorem.

We follow mainly the notation of Kechris and Moschovakis [1977].

This paper is devoted to the study of recursively and short recursively saturated models of PA by means of so-called nonstandard satisfaction methods. The paper is intended to be self-contained. In particular, no knowledge of nonstandard satisfaction classes is assumed. In fact we shall not use this notion explicitly.

We define a certain property of models of PA which we call the S-property and prove that properly short recursively saturated models (see Definition 2.1. below) are exactly short models with the S-property. The main result is that all properly short recursively saturated models are elementary cuts of recursively saturated models. This is a generalization to the uncountable case of the theorem of C. Smorynski [9] and is an easy application of some general results concerning cofinal extensions of models of PA which we discuss in §3.

On the way we obtain another proof of the result of Smorynski and Stavi [10] which says that short recursive and recursive saturation is preserved under cofinal extensions.

The author wants to thank H. Kotlarski and W. Marek for valuable suggestions concerning the subject of the paper.

Special thanks must also go to J. Paris for the lemma used in the proof of Theorem 3.5.

This paper has three parts. In this first part, we formulate and prove from V = L a new combinatorial principle, ⋄++. In the second part, we discuss the topological problem which led to the formulation of ⋄++. Finally, we use ⋄++ to construct a space solving the topological problem.

It was brought to our attention by M. Fitting that Beth's semantic tableau system using the intuitionistic propositional rules and the classical quantifier rules produces a correct but incomplete axiomatization of the logic CD of constant domains. The formula

where T is a truth constant, being an instance of a formula which is valid in all Kripke models with constant domains but which is not provable without cut.

From the Fitting formula one can immediately obtain that the sequent

although provable in the system GD outlined in [3], does not have a cut-free proof (in the system GD).

If the only problem with GD were the sequent S0, then we could extend GD to the system GD+ by adding the following (correct) rule:

Since the new rule still satisfies the subformula property a cut elimination theorem for GD+ would be a step in the right direction for a syntactical proof for the interpolation theorem for the logic of constant domains (cf. Gabbay [2]; see also §4). Unfortunately, one can show that the sequent

where P is a propositional parameter (or formula without x free) has a derivation in GD+, but does not have a cut-free derivation (in GD+). Of course, we could extend GD+ to GD++ by adding the following correct (and with the subformula property) rule:

But then we can find a sequent S2 which, although provable with cut in GD++, does not have a cut-free derivation in GD++.

An example is given of a complete theory with minimal models of arbitrarily large minimality rank.

Throughout, M will denote a transitive model of ZFC. Using the terms “random” and “generic” in the sense of [1], one may ask whether there can exist real numbers x and y such that x is generic over M[y] and y is random over M[x]. We shall see below by an elementary argument that this is not possible, and so, in a crude sense at least, random and generic extensions do not commute. This does not however rule out the possibility of a weaker commutativity. Let B be the complete Boolean algebra (in M) for adjoining a random real followed by a generic real and C be the complete Boolean algebra for adjoining a generic real followed by a random real. Then it still might be the case that B and C are isomorphic. This also fails, though, and we shall prove this by establishing the following combinatorial properties of MB and MC:

but

In addition this will show that C cannot be embedded as a complete subalgebra of B.

The property satisfied by B is reminiscent of calibre ℵ1 [2]. B would have calibre if we could replace “infinite” by “uncountable”, and this occurs if Martin's Axiom holds in M. To obtain the nonisomorphism of B and C in general necessitated looking at the weaker property.

The following rough summary is intended to give the non-specialist in fine-structure an idea of what core models are and what they are used for. References are usually given to proofs but very few proofs are given. Also attribution of results is rather careless: I hope to give full historical notes in a forthcoming more detailed exposition.

Jensen is certainly responsible for the bulk of these results. This paper is based in part on a lecture he gave in Oxford in 1979, and my warmest thanks are due to him for his patient explanations of these results. (I should add that he has not seen this paper in proof and should not be held responsible for any false claims which it contains.) Mitchell has been the main driving force behind the generalisations of K, and his influence on the results in §5 is perhaps not adequately reflected there. The language of “hypermeasures” has been replaced here by “extenders”, but the reader of [14] will find translation easy.

Graeme Forbes, Robin Gandy, Wilfrid Hodges and the referee read the paper in proof and I am most grateful for their many suggested improvements.

Let U and U′ be measures on a cardinal κ: that is, normal κ-complete ultrafilters on κ. The partial ordering ⊲ was defined in [M74]: we say U ⊲ U′ if U ∈ Vκ/U′. A model L(ℱ) was constructed in which this ordering was a well ordering, and it was shown that under proper assumptions the length of this well ordering could be any ordinal up to κ++L(ℱ). In this paper we will revisit this material and show that the coherence required in the construction of ℱ can be greatly weakened. This change simplifies some proofs, weakens the assumption needed for the results stated above (Theorem 1, below), and proves one new result (Theorem 5, below) which is suggestive although its significance is not clear.

We have tried to make this paper self-contained and to that end have repeated some material from [M74]. We begin with some definitions before stating Theorem 1.

The ordering ⊲ is well founded. This may be seen by assuming that it is not and letting κ be least such that ⊲ is not well founded on measures on κ. If U is a measure on κ with an infinite descending chain below it, then the measures on κ in VκU are still not well founded by ⊲, contradicting the fact that iU(κ) is the least cardinal in Vκ/U such that ⊲ is not well founded. Since ⊲ is well founded, we can define O(U) to be the rank of U in the partial ordering ⊲ of measures on κ, and O(κ) to be the rank of this partial ordering.

Associated with each first-order theory is a Boolean algebra of sentences and a Boolean space of models. Homomorphisms between the sentence algebras correspond to continuous maps between the model spaces. To what do recursive homomorphisms correspond? We introduce axiomatizable maps as the appropriate dual. For these maps we prove a Cantor-Bernstein theorem. Duality and the Cantor-Bernstein theorem are used to show that the Boolean sentence algebras of any two undecidable languages or of any two functional languages are recursively isomorphic where a language is undecidable iff it has at least one operation or relation symbol of two or more places or at least two unary operation symbols, and a language is functional iff it has exactly one unary operation symbol and all other symbols are for unary relations, constants, or propositions.

We conclude here the treatment of forcing in recursion theory begun in Part I and continued in Part II of [31]. The numbering of sections is the continuation of the numbering of the first two parts. The bibliography is independent.

In Part I our language was a first-order language: the only set we considered was the (set constant for the) generic set. In Part II a second-order language was introduced, and we had to interpret the second-order variables in some way. What we did was to consider the ramified analytic hierarchy, defined by induction as:

A0 = {X ⊆ ω: X is arithmetic},

Aα+1 = {X ⊆ ω: X is definable (in 2nd order arithmetic) over Aα},

Aλ = ⋃α<λAα (λ limit),

RA = ⋃αAα.

We then used (a relativized version of) the fact that (Kleene [27]). The definition of RA is obviously modeled on the definition of the constructible hierarchy introduced by Gödel [14]. For this we no longer work in a language for second-order arithmetic, but in a language for (first-order) set theory with membership as the only nonlogical relation:

L0 = ⊘,

Lα+1 = {X: X is (first-order) definable over Lα},

Lλ = ⋃α<λLα (λ limit),

L = ⋃αLα.

Definition 1 (Kurepa [3, p. 99]). Let E be a partially ordered set. Then σE denotes the set of all bounded well-ordered subsets of E. We consider σE as a partially ordered set with ordering defined as follows: st if and only if s is an initial segment of t.

Then σE is a tree, i.e., {s ∈ σ E∣ st} is well-ordered for every t ∈ σE. The trees of the form αE were extensively studied by Kurepa in [3]–[10]. For example, in [4], he used σQ and σR to construct various sorts of Aronszajn trees. (Here Q and R denote the rationals and reals, respectively.) While considering monotone mapping between some kind of ordered sets, he came to the following two questions several times:

P.1. Does there exist a strictly increasing rational function on σQ? (See [4, Problème 2], [5, p. 1033], [6, p. 841], [7, Problem 23.3.3].)

P.2. Let T be a tree in which every chain is countable and every level has cardinality <2ℵ0. Does there exist a strictly increasing real function on T? (See [6, p. 246] and [7].)

It is known today that Problem 2 is independent of the usual axioms of set theory (see [1]). Concerning Problem 1 we have the following.