In this paper we continue, from [2], the development of provably recursive analysis, that is, the study of real numbers defined by programs which can be proven to be correct in some fixed axiom system S. In particular we develop the provable analogue of an effective operator on the set of recursive real numbers, namely, a provably correct operator on the set of provably recursive real numbers. In Theorems 1 and 2 we exhibit a provably correct operator on which is discontinuous at 0; we thus disprove the analogue of the Ceitin-Moschovakis theorem of recursive analysis, which states that every effective operator on is (effectively) continuous. Our final theorems show, however, that no provably correct operator on can be proven (in S) to be discontinuous.

We use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing reducibility.

In [6, p. 317] Curry described a formal system assigning types to terms of the type-free λ-calculus. In [11] Scott gave a natural semantics for this type assignment and asked whether a completeness result holds.

Inspired by [4] and [5] we extend the syntax and semantics of the Curry types in such a way that filters in the resulting type structure form a domain in the sense of Scott [12]. We will show that it is possible to turn the domain of types into a λ-model, among other reasons because all λ-terms possess a type. This model gives the completeness result for the extended system. By a conservativity result the completeness for Curry's system follows.

Independently Hindley [8], [9] has proved both completeness results using term models. His method of proof is in some sense dual to ours.

For λ-calculus notation see [1].

A well-known result, going back to the twenties, states that, under some reasonable assumptions, any logic can be characterized as the set of formulas satisfied by a matrix 〈, F〉, where is an algebra of the appropriate type, and F a subset of the domain of , called the set of designated elements. In particular, every quasi-classical modal logic—a set of modal formulas, containing the smallest classical modal logic E, which is closed under the inference rules of substitution and modus ponens—is characterized by such a matrix, where now is a modal algebra, and F is a filter of . If the modal logic is in fact normal, then we can do away with the filter; we can study normal modal logics in the setting of varieties of modal algebras. This point of view was adopted already quite explicitly in McKinsey and Tarski [8]. The observation that the lattice of normal modal logics is dually isomorphic to the lattice of subvarieties of a variety of modal algebras paved the road for an algebraic study of normal modal logics. The algebraic approach made available some general results from Universal Algebra, notably those obtained by Jónsson [6], and thereby was able to contribute new insights in the realm of normal modal logics [2], [3], [4], [10].

The requirement that a modal logic be normal is rather a severe one, however, and many of the systems which have been considered in the literature do not meet it. For instance, of the five celebrated modal systems, S1–S5, introduced by Lewis, S4 and S5 are the only normal ones, while only SI fails to be quasi-classical. The purpose of this paper is to generalize the algebraic approach so as to be applicable not just to normal modal logics, but to quasi-classical modal logics in general.

One of the objectives of mathematics is to construct suitable models for practical or theoretical phenomena and to explore the mathematical richness of such models. This enables other scientists to obtain a better understanding of such phenomena. As an example we will mention the real line and related structures. The line can be used profitably in the study of discrete phenomena like population growth, chemical reactions, etc.

Today's version of the real line is a topological completion of the rational numbers. This is so because then mathematicians have been able to work out a powerful analysis of the line. By using the real line to construct models for finitary phenomena we are more able to study those phenomena than we would have been sticking only to true-to-nature but finite structures.

So we may say that the line is a mathematical model for certain finite structures. This motivates us to seek natural models for other types of finite structures, and it is natural to look for models that in some sense are complete.

In this paper our starting point will be finite systems of finite operators. For the sake of simplicity we assume that they all are operators of one variable and that all the values are natural numbers. There is a natural extension of the systems such that they accept several variables and give finite operators as values, but the notational complexity will then obscure the idea of the construction.

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.

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.

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.

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.

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α.

We review some known results about the Ramsey property for partitions of reals, and we present a certain two-person game such that if either player has a winning strategy then a homogeneous set for the partition can be constructed, and conversely. This gives alternative proofs of some of the known results. We then discuss possible uses of the game in obtaining effective versions of Ramsey's theorem and prove a theorem along these lines.

It is well known that many statements provable from combinatorial principles true in the constructible universe L can also be shown to be consistent with ZFC by forcing. Recent work by Shelah and Stanley [4] and the author [5] has clarified the relationship between the axiom of constructibility and forcing by providing Martin's Axiom-type forcing axioms equivalent to ◊ and the existence of morasses. In this paper we continue this line of research by providing a forcing axiom equivalent to □κ. The forcing axiom generalizes easily to inaccessible, non-Mahlo cardinals, and provides the motivation for a corresponding generalization of □κ.

In order to state our forcing axiom, we will need to define a strategic closure condition for partial orders. Suppose P = 〈P, ≤〉 is a partial order. For each ordinal α we will consider a game played by two players, Good and Bad. The players choose, in order, the terms in a descending sequence of conditions 〈pβ∣β < α〉 Good chooses all terms pβ for limit β, and Bad chooses all the others. Bad wins if for some limit β<α, Good is unable to move at stage β because 〈pγ∣γ < β〉 has no lower bound. Otherwise, Good wins. Of course, we will be rooting for Good.

Let be a well-founded model of ZFC whose class of ordinals has uncountable cofinality, such that has a Σn end extension for each n ∈ ω. It is shown in Theorem 1.1 that there is such a model which has no elementary end extension. In the process some interesting facts about topless end extensions (those with no least new ordinal) are uncovered, for example Theorem 2.1: If is a well-founded model of ZFC, such that has uncountable cofinality and has a topless Σ3 end extension, then has a topless elementary end extension and also a well-founded elementary end extension, and contains ordinals which are (in ) highly hyperinaccessible. In §3 related results are proved for κ-like models (κ any regular cardinal) which need not be well founded. As an application a soft proof is given of a theorem of Schmerl on the model-theoretic relation κ → λ. (The author has been informed that Silver had earlier, independently, found a similar unpublished proof of that theorem.) Also, a simpler proof is given of (a generalization of) a characterization by Keisler and Silver of the class of well-founded models which have a Σn end extension for each n ∈ ω. The case κ = ω1 is investigated more deeply in §4, where the problem solved by Theorem 1.1 is considered for non-well-founded models. In Theorems 4.1 and 4.4, ω1-like models of ZFC are constructed which have a Σn end extension for all n ∈ ω but have no elementary end extension. ω1-like models of ZFC which have no Σ3 end extension are produced in Theorem 4.2. The proof uses a notion of satisfaction class, which is also applied in the proof of Theorem 4.6: No model of ZFC has a definable end extension which satisfies ZFC. Finally, Theorem 5.1 generalizes results of Keisler and Morley, and Hutchinson, by asserting that every model of ZFC of countable cofinality has a topless elementary end extension. This contrasts with the rest of the paper, which shows that for well-founded models of uncountable cofinality and for κ-like models with κ regular, topless end extensions are much rarer than blunt end extensions.

The theories considered here are countable and complete, and the types are all complete too. Let T be an L-theory. A sequence σ = (σn(ν))n∈ω of L-formulas is said to be independent (with respect to T) if for each α ∈ 2<ω, the sentence

is in T. As an example, let T = Th(Z, +), and let σ be the sequence of formulas saying (in the language of groups) ν is divisible by the nth prime, for n ∈ ω.

A theory T has an independent sequence of formulas just in case it has types. If T has one independent sequence σ, then it has other independent sequences of arbitrarily high degree. (These can be obtained by taking conjunctions of the formulas from σ. If T has an independent sequence that is recursive, or one that is recursive in some type, then T will have types of arbitrarily high degree. (This follows from the fact that the independent sequence can be used to encode any set in a type.)

Nadel and the author had wondered whether a theory with types must have an independent sequence of formulas that is recursive in one of the types. The main result of the present paper is an example of a recursive theory for which this is not the case.

We shall prove the following theorem: If κ is an infinite cardinal and Γ: P(κ) → cf κ a partition of the power-set of κ then we can find a homogeneous ⊿-system of size κ such that the kernel of the ⊿-system is in the same partition class as all the members of the ⊿-system.

We give two new finite combinatorial statements which are independent of Peano arithmetic, using the methods of Kirby and Paris [6] and Paris [12]. Both are in fact equivalent over Peano arithmetic (denoted by P) to its 1-consistency. The first involves trees and the second linear orderings. Both were “motivated” by anti-basis theorems of Clote (cf. [1], [2]). The one involving trees, however, is not unrelated to the Kirby-Paris characterization of strong cuts in terms of the tree property [6], but, in fact, comes directly from König's lemma, of which it is a miniaturization. (See the remark preceding Theorem 3 below.) The resulting combinatorial statement is easily seen to imply the independent statement discovered by Mills [11], but it is not clear how to show their equivalence over Peano arithmetic without going through 1-consistency. The one involving linear orderings miniaturizes the property of infinite sets X that any linear ordering of X is isomorphic to ω or ω* on some infinite subset of X. Both statements are analogous to Example 2 of [12] and involve the notion of dense [12] or relatively large [14] finite set.

We adopt the notations and definitions of [6] and [12]. We shall in particular have need of the notions of semiregular, regular and strong initial segments and of indicators.

The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of rand over arbitrary subsets of T. We prove that there is no monadic second-order formula ϕ*(X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies ϕ*(X, y) in T.

In a paper of 1933 Gödel proved that every satisfiable first-order ∀2∃* sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀2∃* sentence.

This paper's goal is to determine which complete theories of perfect, e-free Ax fields are model-complete. A field K is e-free for a positive integer e if the Galois group g(KS∣K), where Ks is the separable closure of K, is an e-free, profinite group. A perfect field K is pseudo-algebraically closed if each nonvoid, absolutely irreducible variety defined over K has a K-rational point. A perfect, pseudo-algebraically closed field is called an Ax field. The main theorem is

A complete theory of e-free Ax fields is model-complete if and only if its field of absolute numbers is e-free.

The sufficiency of the latter condition is an easy consequence of a result of Moshe Jarden and Ursel Kiehne [10] and has been noted independently by A. Macintyre and K. McKenna and undoubtedly by others as well. Consequently the necessity of the latter condition is the interesting part of this paper.

James Ax [3] initiated the investigation of 1-free Ax fields. He proved that these fields, which he called pseudo-finite fields, are precisely the infinite models of the theory of finite fields. He [3] also presented examples of perfect, 1-free fields which are not pseudo-algebraically closed and an example of a 1-free Ax field whose complete theory is not model-complete. Moshe Jarden [5] showed that the first examples are isolated cases in that almost all, perfect, 1-free, algebraic extensions of a denumerable, Hilbertian field are pseudo-algebraically closed. The results in this paper show that the second example is also an isolated case in that almost all complete theories of 1-free Ax fields are model-complete.

The complete, model-complete theories of pseudo-algebraically closed fields were characterized completely in [11]. That work constituted the first step towards determining all the model-complete theories of fields in the usual language of fields. In this paper the second step is taken. Namely, the methods of [11] are extended to characterize the complete, model-complete theories of pseudo-real closed fields and pseudo-p-adically closed fields.

In order to unify the treatment of these two types of fields, the relevant properties of real closed ordered fields and p-adically closed valued fields are abstracted. The subsequent investigation of model-complete theories of fields is based entirely on these properties. The properties were selected in order to solve three problems: (1) finding universal theories with the joint embedding property, (2) finding first order conditions in the usual language of fields which are necessary and sufficient for a polynomial over a field to have a zero in a formally real or formally p-adic extension of that field, and (3) finding subgroups of Galois groups whose fixed fields are formally real or formally p-adic.

This paper is related to, and uses in §1 but not in the other sections, parts of K. McKenna's work [8] on model-complete theories of ordered fields and p-valued fields. However, the results herein are not direct consequences of his work, both because these results apply to a more general situation and because they use a different formal language. Concerning the latter point, in some instances, such as real closed ordered fields and p-adically closed valued fields, model-complete theories in expanded languages do yield model-complete theories of ordinary fields other than theories of pseudo-algebraically closed fields. However, in other cases, such as differentially closed fields, this is not so.