The theory of cylindric algebras (CA's) is the algebraic theory of first order logics. Several ideas about logic are easier to formulate in the frame of CA-theory. Such are e.g. some concepts of abstract model theory (cf. [1] and [10]–[12]) as well as ideas about relationships between several axiomatic theories of different similarity types (cf. [4] and [10]). In contrast with the relationship between Boolean algebras and classical propositional logic, CA's correspond not only to classical first order logic but also to several other ones. Hence CA-theoretic results contain more information than their counterparts in first order logic. For more about this see [1], [3], [5], [9], [10] and [12].

Here we shall use the notation and concepts of the monographs Henkin-Monk-Tarski [7] and [8]. ω denotes the set of natural numbers. CAα denotes the class of all cylindric algebras of dimension α; by “a CAα” we shall understand an element of the class CAα. The class Dcα ⊆ CAα was defined in [7]. Note that Dcα = 0 for α ∈ ω. The classes Wsα, and Csα were defined in 1.1.1 of [8], p. 4. They are called the classes of all weak cylindric set algebras, regular cylindric set algebras and cylindric set algebras respectively. It is proved in [8] (I.7.13, I.1.9) that ⊆ CAα. (These inclusions are proper by 7.3.7, 1.4.3 and 1.5.3 of [8].)

It was proved in 2.3.22 and 2.3.23 of [7] that every simple, finitely generated Dcα is generated by a single element. This is the algebraic counterpart of a property of first order logics (cf. 2.3.23 of [7]). The question arose: for which simple CAα's does “finitely generated” imply “generated by a single element” (see p. 291 and Problem 2.3 in [7]). In terms of abstract model theory this amounts to asking the question: For which logics does the property described in 2.3.23 of [7] hold? This property is roughly the following. In any maximal theory any finite set of concepts is definable in terms of a single concept. The connection with CA-theory is that maximal theories correspond to simple CA's (the elements of which are the concepts of the original logic) and definability corresponds to generation.

This paper consists of two parts. In §1 we mention the first strongly compact cardinal. Magidor proved in [6] that it can be the first measurable and it can be also the first supercompact. In [2], Apter proved that Con(ZFC + there is a supercompact limit of supercompact cardinals) implies Con(ZFC + the first strongly compact cardinal κ is ϕ(κ)-supercompact + no α < κ is ϕ(α)-supercompact) for a formula ϕ which satisfies certain conditions.

We shall get almost the same conclusion as Apter's theorem assuming only one supercompact cardinal. Our notion of forcing is the same as in [2] and a trick makes it possible.

In §2 we study a kind of fine ultrafilter on Pκλ investigated by Menas in [7], where κ is a measurable limit of strongly compact cardinals. He showed that such an ultrafilter is not normal in some case (Theorems 2.21 and 2.22 in [7]). We shall show that it is not normal in any case (even if κ is supercompact). We also prove that it is weakly normal in some case.

We work in ZFC and much of our notation is standard. But we mention the following: the letters α,β,γ… denote ordinals, whereas κ,λ,μ,… are reserved for cardinals. R(α) is the collection of sets rank <α. φM denotes the realization of a formula φ to a class M. Except when it is necessary, we drop “M”. For example, M ⊩ “κ is φ(κ)-supercompact” means “κ is φM(κ)-supercompact in M”. If x is a set, |x| is its cardinality, Px is its power set, and . If also x ⊆ OR, denotes its order type in the natural ordering. The identity function with the domain appropriate to the context is denoted by id. For the notation concerning ultrapowers and elementary embeddings, see [11]. When we talk about forcing, “⊩” will mean “weakly forces” and “p < q” means “p is stronger than q”.

Assuming the existence of a supercompact cardinal, we construct a model of ZFC + (There exists a nonsplitting stationary subset of ). Answering a question of Uri Abraham [A], [A-S], we prove that adding a real to the world always makes stationary

In [6] Gödel observed that intuitionistic propositional logic can be interpreted in Lewis's modal logic (S4). The idea behind this interpretation is to regard the modal operator □ as expressing the epistemic notion of “informal provability”. With the work of Shapiro [12], Myhill [10], Goodman [7], [8], and Ščedrov [11] this simple idea has developed into a successful program of integrating classical and intuitionistic mathematics.

There is one question quite central to the above program that has remained open. Namely:

In the present paper we give an affirmative answer to this question.

The main ingredient in our proof is the construction of an interpretation of epistemic set theory into intuitionistic set theory which is inverse to the Gödel translation. This is accomplished in two steps. First we observe that Funayama's theorem is constructively provable and apply it to the power set of 1. This provides an embedding of the set of propositions into a complete topological Boolean algebra . Second, in a fashion completely analogous to the construction of Boolean-valued models of classical set theory, we define the -valued universe V(). V() gives a model of epistemic set theory and, since we use a constructive metatheory, this provides an interpretation of epistemic set theory into intuitionistic set theory.

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 we give a positive answer to Julia Robinson's question whether the definability of + and · from S and ∣ that she proved in the case of positive integers is extendible to arbitrary integers (cf. [JR, p. 102]).

If κ is a measurable cardinal, then it is a well-known fact that there is at least one normal ultrafilter over κ. In [K-1], Kunen showed that one cannot say more without further assumptions, for if U is a normal ultrafilter over κ, then L[U] is an inner model of ZFC in which κ has exactly one normal measure. On the other hand, Kunen and Paris showed [K-P] that if κ is measurable in the ground model, then there is a forcing extension in which κ has normal ultrafilters, so it is consistent that κ has the maximum possible number of normal ultrafilters. Starting with assumptions stronger than measurability, Mitchell [Mi-1] filled in the gap by constructing models of ZFC + GCH satisfying “there are exactly λ normal ultrafilters over κ”, where λ could be κ+ or κ++ (measured in the model), or anything ≤ κ. Whether or not Mitchell's results can be obtained by starting only with a measurable cardinal in the ground model and defining a forcing extension is unknown.

There are substantial differences between the Mitchell models and the Kunen-Paris models. In the Kunen-Paris models κ can be the only measurable cardinal. However, in the Mitchell model in which κ has exactly 2 normal ultrafilters, one of them contains the set {α < κ: α is measurable} while the other does not. Thus it is natural to ask if it is possible to get a model M of ZFC in which κ is the only measurable cardinal and κ has exactly 2 normal ultrafilters. In this paper we will show that, using appropriate large cardinal assumptions, the answer is yes.

This article is a rewriting of my Ph.D. Thesis, supervised by Professor G. Sabbagh, and incorporates a suggestion from Professor B. Poizat. My main result can be crudely summarized (but see below for detailed statements) by the equality: first-order theory of F[Xi]i∈I = weak second-order theory of F.

§I.1. Conventions. The letter F will always denote a commutative field, and I a nonempty set. A field or a ring (A; +, ·) will often be written A for short. We shall use symbols which are definable in all our models, and in the structure of natural numbers (N; +, ·):

— the constant 0, defined by the formula Z(x): ∀y (x + y = y);

— the constant 1, defined by the formula U(x): ∀y (x · y = y);

— the operation ∹ x − y = z ↔ x = y + z;

— the relation of division: x ∣ y ↔ ∃ z(x · z = y).

A domain is a commutative ring with unity and without any zero divisor.

By “… → …” we mean “… is definable in …, uniformly in any model M of L”.

All our constructions will be uniform, unless otherwise mentioned.

§I.2. Weak second-order models and languages. First of all, we have to define the models Pf(M), Sf(M), Sf′(M) and HF(M) associated to a model M = {A; ℐ) of a first-order language L [CK, pp. 18–20]. Let L1 be the extension of L obtained by adjunction of a second list of variables (denoted by capital letters), and of a membership symbol ∈. Pf(M) is the model (A, Pf(A); ℐ, ∈) of L1, (where Pf(A) is the set of finite subsets of A. Let L2 be the extension of L obtained by adjunction of a second list of variables, a membership symbol ∈, and a concatenation symbol ◠.

§I. In 1961, R. L. Vaught ([V]) asked if one could prove, without the continuum hypothesis, that there exists a countable complete theory with exactly ℵ1 isomorphism types of countable models. The following statement is known as Vaught conjecture:

Let T be a countable theory. If T has uncountably many countable models, then T hascountable models.

More than twenty years later, this question is still open. Many papers have been written on the question: see for example [HM], [M1], [M2] and [St]. In the opinion of many people, it is a major problem in model theory.

Of course, I cannot say what Vaught had in mind when he asked the question. I just want to explain here what meaning I personally see to this problem. In particular, I will not speak about the topological Vaught conjecture, which is quite another issue.

I suppose that the first question I shall have to face is the following: “Why on earth are you interested in the number of countable models—particularly since the whole question disappears if we assume the continuum hypothesis?” The answer is simply that I am not interested in the number of countable models, nor in the number of models in any cardinality, as a matter of fact. An explanation is due here; it will be a little technical and it will rest upon two names: Scott (sentences) and Morley (theorem).

For sets of natural numbers A and B, A is enumeration reducible to B if there is some effective algorithm which when given any enumeration of B will produce an enumeration of A. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib 0. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0″ is an upper bound for the minimal pair constructed in §1, and in §2 we improve this bound to any Σ2-high Δ2 degree. In contrast to this we show that every low degree c bounds a degree a which is not in any minimal pair bounded by c. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In §3 we show that if a, b is any minimal pair of co-r.e. degrees such that a is low then a, b is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0′. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In §4 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings.

As usual, {Wi}i ∈ ω is the standard listing of the recursively enumerable sets, Du is the finite set with canonical index u and {‹ m, n ›}m, n ∈ ω is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.

In the wake of Silver's breakthrough on the Singular Cardinals Problem (Silver [74]) followed one of the landmark results in set theory, Jensen's Covering Lemma (Devlin-Jensen [74]): If 0# does not exist then for every uncountable x ⊆ ORD there exists a constructible Y ⊇ X, card(Y) = card(X). Thus it is fair to say that in the absence of large cardinals, V is “close to L”.

It is natural to ask, as did Solovay, if we can fairly interpret the phrase “close to L” to mean “generic over L”. For example, if V = L[a], a ⊆ ω and if 0# does not exist then is V-generic over L for some partial ordering ∈ L? Notice that an affirmative answer implies that in the absence of 0#, no real can “code” a proper class of information.

Jensen's Coding Theorem provides a negative answer to Solovay's question, in a striking way: Any class can be “coded” by a real without introducing 0#. More precisely, if A ⊆ ORD then there is a forcing definable over 〈L[A], A〉 such that ⊩ V = L[a], a ⊆ ω, A is definable from a. Moreover if 0# ∉ L[A] then ⊩ 0# does not exist. Now as any M ⊨ ZFC can be generically extended to a model of the form L[A] (without introducing 0#) we obtain: For any 〈M, A〉 ⊨ ZFC (that is, M ⊨ ZFC and M obeys Replacement for formulas mentioning A as a predicate) there is an 〈M, A〉-definable forcing such that ⊩ V = L[a], a ⊆ ω, 〈M, A〉 is definable from a. Moreover if 0# ∉ M then ⊩ 0# does not exist.

In this paper we prove that if T is the complete elementary diagram of a countable structure and is a theory as in the title, then Vaught's conjecture holds for T. This result is Theorem 7, below. In the process of establishing this proposition, in Theorem 3 we give a sufficient condition for a superstable theory having only countably many types without parameters to be ω-stable. Familiarity with the rudiments of stability theory, as presented in [3] and [4], will be supposed throughout. The notation used is, by now, standard.

We begin by giving a new proof of a lemma due to J. Saffe in [6]. For T stable, recall that the multiplicity of a type p over a set A ⊆ ℳ ⊨ T is the cardinality of the collection of strong types over A extending p.

Lemma 1 (Saffe). Let T be stable, A ⊆ ℳ ⊨ T. If t(b̄, A) has infinite multiplicity and t(c̄, A) has finite multiplicity, then t(b̄, A ∪ {c̄}) has infinite multiplicity.

Proof. We suppose not and work for a contradiction. Let ‹b̄γ:γ ≤ α›, α ≥ ω, be a list of elements so that t(b̄γ, A) = t(b̄, A) for all γ ≤ α, and st(b̄γ, A) ≠ st(b̄δ, A) for γ ≠ δ. Furthermore, let c̄γ satisfy t(b̄γ∧c̄γ, A) = t(b̄ ∧ c̄, A) for each γ < α.

Since t(c̄, A) has finite multiplicity, we may assume for all γ, δ < α. that st(c̄γ, A) = st(c̄δ, A). For each γ < α there is an automorphism fγ of the so-called “monster model” of T (a sufficiently large, saturated model of T) that preserves strong types over A and is such that f(c̄γ) = c̄0.

Throughout this paper, ⊿ will denote a commutative ring with multiplicative identity, 1. The algebras we consider will be associative ⊿-algebras which are not necessarily commutative and do not necessarily contain a multiplicative identity. By standard methods, every ⊿-algebra can be embedded in an existentially closed (e.c.) Δ-algebra—and even in one which is existentially universal (e.u.). (See §0 for more details.)

We shall be studying the ideals of e.c. ⊿-algebras. Since every ideal is a sum of principal ideals, a natural place to begin is with principal ideals. In §1 we show that for an algebraically closed (a.c.) ⊿-algebra A, and elements a, b in A, whether or not b belongs to the principal ideal (a)A generated by a, depends only on the underlying ⊿-module structure of A; more precisely, for b to belong to (a)A it is necessary and sufficient that b satisfies every positive existential formula θ(ν) in the language of ⊿-modules which is satisfied by a (cf. Corollary 1.8). For special classes of rings ⊿ this condition can be simplified (Proposition 1.10): e.g. for Prüfer rings it is enough to consider formulas of the form ∃x(λx = μν); and for regular rings it is enough to consider formulas μν = 0 (where λ, μ ∈ ⊿).

In §2 we use the results of §1 to study e.c. and e.u. algebras over a principal ideal domain (p.i.d.) ⊿ (Note that for ⊿ = Z this includes the case of e.c. rings.) We obtain a necessary and sufficient condition for an a.c. ⊿-algebra to be e.c. (Theorem 2.4). We also show (Theorem 2.2) that in an a.c. ⊿-algebra A every element that is divisible by all nonzero elements of ⊿ belongs to the divisible part D(A) of A. (It should be noted that, while a.c. ⊿-modules are always divisible [ES], an e.c. ⊿-algebra is never divisible: see the end of §0. Moreover, an e.c. ⊿-algebra always contains torsion-free elements: see Remark 2.3.) We prove that every bounded ideal in an a.c. ⊿-algebra is principal (2.7).

Let T be superstable. We say a type p is weakly minimal if R(p, L, ∞) = 1. Let M ⊨ T be uncountable and saturated, H = p(M). We say D ⊂ H is locally modular if for all X, Y ⊂ D with X = acl(X) ∩ D, Y = acl(Y) ∩ D and X ∩ Y ≠ ∅,

Theorem 1. Let p ∈ S(A) be weakly minimal and D the realizations of stp(a/A) for some a realizing p. Then D is locally modular or p has Morley rank 1.

Theorem 2. Let H, G be definable over some finite A, weakly minimal, locally modular and nonorthogonal. Then for all a ∈ H∖acl(A), b ∈ G∖acl(A) there area′ ∈ H, b′ ∈ G such that a′ ∈ acl(abb′A)∖acl(aA). Similarly when H and G are the realizations of complete types or strong types over A.

Suppose D ⊂ M is a strongly minimal set definable in M with parameters from C. We say D is locally modular if for all X, Y ⊂ D, with X = acl(X ∪ C)∩D, Y = acl(Y ∪ C) ∩ D and X ∩ Y ≠ ∅,

We prove the following theorems.

Theorem 1. Suppose M is stable and D ⊂ M is strongly minimal. If D is not locally modular then inMeqthere is a definable pseudoplane.

(For a discussion of Meq see [M, §A].) This is the main part of Theorem 1 of [Z2] and the trichotomy theorem of [Z3].

Theorem 2. Suppose M is stable and D, D′ ⊂ M are strongly minimal and nonorthogonal. Then D is locally modular if and only if D′ is locally modular.

Given a prime p, we exhibit a Horn sentence Hp which expresses “the cardinality is not p” and has size O(p5 log p).