Let V∞ be a fully effective infinite dimensional vector space over a recursive field F. That is, we assume that the universe of V∞ is a recursive set, the operations of addition and scalar multiplication are recursive, and there is a uniform effective procedure to decide whether any finite set {υ0, …, υn} of vectors from V∞ is independent. The lattice of recursively enumerable subspaces has been extensively studied since its introduction by Metakides and Nerode [MN1] (see for example, [Do2], [Gu], [KR], [Re1], [Re2], and [Sh]). For those unfamiliar with the literature on , we shall give a list of basic definitions required for this paper in §0.

It is well known that complements in V∞ are not unique. For example, in [Re2] Remmel constructed r.e. spaces M1 and M2 and co-r.e. spaces Q1 and Q2 such that for all i, j ∈ {1, 2}, Mi ⊕ Qj = V∞ and M1 is supermaximal, M2 is not maximal, Q1 has a fully extendible basis, and Q2 has no extendible basis. We say a subspace Q of V∞ is fully co-r.e. if Q is generated by a co-r.e. subset of some recursive basis of V∞. Downey [Do2] has shown that every r.e. subspace of V∞ has a complement which is a fully co-r.e. subspace. Moreover suppose Q is any fully co-r.e. subspace, say Q = (C)* where C is a co-r.e. subset of a recursive basis B of V∞; if C is nonrecursive, then it is shown in [Do2] that Q has a decidable complement as well as a nondecidable nowhere simple complement.

There is a distinction between semantical paradoxes on the one hand and logical or mathematical paradoxes on the other, going back to Ramsey [1925]. Those falling under the first heading have to do with such notions as truth, assertion (or proposition), definition, etc., while those falling under the second have to do with membership, class, relation, function (and derivative notions such as cardinal and ordinal number), etc. There are a number of compelling reasons for maintaining this separation but, as we shall see, there are also many close parallels from the logical point of view.

The initial solutions to the paradoxes on each side—namely Russell's theory of types for mathematics and Tarski's hierarchy of language levels for semantics— were early recognized to be excessively restrictive. The first really workable solution to the mathematical paradoxes was provided by Zermelo's theory of sets, subsequently improved by Fraenkel. The informal argument that the paradoxes are blocked in ZF is that its axioms are true in the cumulative hierarchy of sets where (i) unlike the theory of types, a set may have members of various (ordinal) levels, but (ii) as in the theory of types, the level of a set is greater than that of each of its members. Thus in ZF there is no set of all sets, nor any Russell set {x∣x∉x} (which would be universal since ∀x(x∉x) holds in ZF). Nor is there a set of all ordinal numbers (and so the Burali-Forti paradox is blocked).

The importance of the logical ‘generalized quantifiers’ (Mostowski [1957]) for the semantics of natural language was brought out clearly in Barwise & Cooper [1981]. Basically, the idea is that a quantifier phrase QA (such as “all women”, “most children”, “no men”) refers to a set of sets of individuals, viz. those B for which (QA)B holds. Thus, e.g., given a fixed model with universe E,

where ⟦A⟧ is the set of individuals forming the extension of the predicate “A” in the model. This point of view permits an elegant and uniform semantic treatment of the subject-predicate form that pervades natural language.

Such denotations of quantifier phrases exhibit familiar mathematical structures. Thus, for instance, all A produces filters, and no A produces ideals. The denotation of most A is neither; but it is still monotone, in the sense of being closed under supersets. Mere closure under subsets occurs too; witness a quantifier phrase like few A. These mathematical structures are at present being used in organizing linguistic observations and formulating hypotheses about them. In addition to the already mentioned paper of Barwise & Cooper, an interesting example is Zwarts [1981], containing applications to the phenomena of “negative polarity” and “conjunction reduction”. In the course of the latter investigation, several methodological issues of a wider logical interest arose, and these have inspired the present paper.

In order to present these issues, let us shift the above perspective, placing the emphasis on quantifier expressions per se (“all”, “most”, “no”, “some”, etcetera), viewed as denoting relations Q between sets of individuals.

The purpose of the present paper is to give a new, simple proof of the theorem of M. Davis, H. Putnam and J. Robinson [1961], which states that every recursively enumerable relation A(a1, …, an) is exponential diophantine, i.e. can be represented in the form

where a1 …, an, x1, …, xm range over natural numbers and R and S are functions built up from these variables and natural number constants by the operations of addition, A + B, multiplication, AB, and exponentiation, AB. We refer to the variables a1,…,an as parameters and the variables x1 …, xm as unknowns.

Historically, the Davis, Putnam and Robinson theorem was one of the important steps in the eventual solution of Hilbert's tenth problem by the second author [1970], who proved that the exponential relation, a = bc, is diophantine, and hence that the right side of (1) can be replaced by a polynomial equation. But this part will not be reproved here. Readers wishing to read about the proof of that are directed to the papers of Y. Matijasevič [1971a], M. Davis [1973], Y. Matijasevič and J. Robinson [1975] or C. Smoryński [1972]. We concern ourselves here for the most part only with exponential diophantine equations until §5 where we mention a few consequences for the class NP of sets computable in nondeterministic polynomial time.

In this paper we consider various generalizations of the notion of hugeness. We remind the reader that a cardinal κ is huge if there exist a cardinal λ > κ, an inner model M which is closed under λ-sequences, and an elementary embedding i: V → M with critical point κ such that i(κ) = λ. We shall call λ a target for κ and shall write κ → (λ) to express this fact. Equivalently, κ is huge with target λ if and only if there exists a normal ultrafilter on P=κ(λ) = {X ⊆ λ:X has order type κ}. For the proof and additional facts on hugeness, see [3].

We assume that the reader is familiar with the notions of measurability and supercompactness. If κ is γ-supercompact for each γ < λ, we shall say that κ is < λ-supercompact. We note that if κ → (λ), it follows immediately that κ is < λ-supercompact.

Throughout the paper, n shall be used to denote a positive integer, the letters α, β, and δ shall denote ordinals, while κ, λ, γ, and η shall be reserved for cardinals. All addition is ordinal addition. V denotes the universe of all sets.

All results except for Theorems 6b and 6c and Lemma 6d can be formalized in ZFC.

This paper was written while the first named author was at Rochester Institute of Technology, Rochester, New York. We wish to thank the department of mathematics at R.I.T. for secretarial time and facilities.

c.c.c. posets are characterised in terms of -generic conditions. This characterisation can be applied to get simple proofs of many facts about c.c.c. forcing including Con(MA + ┐CH).

We exhibit a Horn sentence expressing the statement of the title; the construction generalizes to arbitrary primes in place of five.

A subspace V of an infinite dimensional fully effective vector space V∞ is called decidable if V is r.e. and there exists an r.e. W such that V ⊕ W = V∞. These subspaces of V∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V∞) and the set of decidable subspaces forms a lower semilattice S(V∞). We analyse S(V∞) and its relationship with L(V∞). We show:

Proposition. Let U, V, W ∈ L(V∞) where U is infinite dimensional andU ⊕ V = W. Then there exists a decidable subspace D such that U ⊕ D = W.

Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces.

These results allow us to show:

Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V∞), is undecidable.

This contrasts sharply with the result for recursive sets.

Finally we examine various generalizations of our results. In particular we analyse S*(V∞), that is, S(V∞) modulo finite dimensional subspaces. We show S*(V∞) is not a lattice.

In this paper, we remark on some properties of equality that tend to be neglected and use them to give a proof of an extension of Lyndon's interpolation theorem. Let LK be a first order classical predicate calculus and LK= a first order classical predicate calculus with equality. We assume that LK and LK= have the propositional constant Τ (truth). For each formula F in LK=, let Rel+ (F), Rel− (F), Rel(F), and Fun(F) be the set of all the predicate symbols which occur in F positively, the set of all the predicate symbols which occur in F negatively, the set of all the predicate symbols which occur in F, and the set of all the function symbols which occur in F.

Theorem A (Lyndon [5]). Suppose that A and B are sentences in LK such that A ⊃ B is provable in LK. Then there is a sentence C in LK such that:

(i) A ⊃ C and C ⊃ B are provable in LK;

(ii) and

(iii) .

The sentence C which satisfies (i), (ii), (iii) in Theorem A is said to be an interpolant for A ⊃ B in Theorem A. Note that condition (iii) is not included in the original form of Lyndon's interpolation theorem (cf. [5]), but we can easily add this condition. Also, there is some obscurity in the original formulation with regard to the equality symbol. For example, Lyndon writes: “The theorem takes the same form whether or not we admit a predicate denoting identity, with suitable axioms, to the predicate calculus” [5, p. 129].

One of the most interesting concepts arising from the study of L(V∞), the lattice of r.e. subspaces of a fully effective vector space of infinite dimension (cf. [6], [7] or [10]), was that of a supermaximal subspace. Supermaximal subspaces of V∞ were those with the fewest possible r.e. superspaces, that is, we say M ∈ L(L∞) is supermaximal if dim(V∞/M) = ∞ and for all Q ∈ L(V∞) with Q ⊇ M, either dim(Q/M) < ∞ or Q = V∞. These spaces were particularly interesting because they had no natural analogue in L(ω), the lattice of r.e. sets. Later Metakides and Nerode [8], Baldwin [1] and the author [2] found that supermaximal substructures occurred in more general settings. In particular, they were found to occur in L(F∞), the lattice of r.e. algebraically closed subfields of F∞ (a recursively presented field of infinite transcendence degree) (cf. [3]). The main tool in these later papers was the concept of a Steinitz (closure) system with recursive dependence (cf. [1], [2], [4] or [8]). We assume familiarity with the definitions and basic results of Metakides and Nerode [8], and only give a brief sketch of some nonstandard facts in §2. If the reader is not familiar with Steinitz systems he is advised to either obtain [1] or [2], or simply identify a Steinitz system (U, cl) with (V∞, *), that is, he should identify U with V∞, and cl(A) with A*, the subspace generated by A.

We prove that every relation-universal model of an ω-stable theory is saturated. We also show there is a large class of ω-stable theories for which every resplendent model is homogeneous.

The purpose of this paper is to establish a connection between the complexity of κ-ultrafilters over a measurable cardinal κ, and the existence of ascending Rudin-Keisler chains of κ-ultrafilters and of inner models with several measurable cardinals.

If V is a model of ZFC + “There exists a measurable cardinal κ”, then V satisfies “There exists a normal κ-ultrafilter”, that is to say a “simple” κ-ultrafilter. The only known examples of “complex” κ-ultrafilters have been constructed by Kanamori [2], Ketonen [4] and Kunen (cf. [2]) with stronger hypotheses than measurability: compactness or supercompactness. Using the notions of skies and constellations defined by Kanamori [2] for the measurable case, and which witness the complexity of a κ-ultrafilter, we shall show the necessity of such assumptions, namely:

Theorem 1. If λ < κ is a strongly inaccessible cardinal, the existence of a κ-ultrafilter with more than λ constellations implies that there is an inner model with two measurable cardinals if λ = ω and λ + 1 measurable cardinals otherwise.

Theorem 2. Let θ < κ be an arbitrary ordinal. If there is a κ-ultrafilter such that the order-type of its skies is greater than ωθ, then there exists an inner model with θ + 1 measurable cardinals.

And as a corollary, we obtain:

Theorem 3. Let μ < κ be a regular cardinal. If there exists a κ-ultrafilter containing the closed-unbounded subsets of κ and {α < κ: cf(α) = μ}, then there is an inner model with two measurable cardinals if μ = ω, and μ + 1 measurable cardinals otherwise.

Problems of computing probabilities of statements about large, finite structures have become an important subject area of finite combinatorics. Within the last two decades many researchers have turned their attention to such problems and have developed a variety of methods for dealing with them. Applications of these ideas include nonconstructive existence proofs for graphs with certain properties by showing the properties occur with nonzero probabilities (for examples see Erdös and Spencer [ES] and Bollobás [Bo]), and determination of average running times for sorting algorithms by computing asymptotic probabilities of statements about permutations (see Knuth [Kn]). Two types of techniques recur in solutions to such problems: probabilistic techniques, such as those used by Erdös and Spencer [ES], and classical assymptotic techniques, such as those surveyed by Bender [Be] and de Bruijn [Br]. Studying this body of techniques, one notices that characteristics of these problems suggest certain methods of solution, in much the same way that the form of an integrand may suggest certain substitutions. The question arises, then, as to whether there is a systematic way to approach these problems: is there an algorithm for computing asymptotic probabilities? I will show that the answer is “no”—for any reasonable formulation, the problem of computing asymptotic probabilities is undecidable.

The main theorem of the paper is Theorem 1.6, which says that there is a finitely axiomatizable class in which every first order sentence has an asymptotic probability of 0 or 1—i.e., is almost always true or almost always false in finite structures—but for which the problem of deciding whether a sentence has asymptotic probability 0 or 1 is undecidable. Heretofore, classes known to have such a 0-1 law have had decidable asymptotic probability problems (see Lynch [Ly] for examples and a discussion of previous work in the area).

A first order representation (f.o.r.) in topology is an assignment of finitary relational structures of the same type to topological spaces in such a way that homeomorphic spaces get sent to isomorphic structures. We first define the notions “one f.o.r. is at least as expressive as another relative to a class of spaces” and “one class of spaces is definable in another relative to an f.o.r.”, and prove some general statements. Following this we compare some well-known classes of spaces and first order representations. A principal result is that if X and Y are two Tichonov spaces whose posets of zero-sets are elementarily equivalent then their respective rings of bounded continuous real-valued functions satisfy the same positive-universal sentences. The proof of this uses the technique of constructing ultraproducts as direct limits of products in a category theoretic setting.

An r.e. set A is nowhere simple if for every r.e. set We such that We − A is infinite, there is an infinite r.e. set W such that W ⊆ We − A. The definition of nowhere simple sets is due to R. Shore in [4]. In [4], Shore studied various properties of nowhere simple sets and showed that they could be used to give an elegant and simple proof of the fact that every nontrivial class of r.e. sets C closed under recursive isomorphisms is an automorphism base for , the lattice of r.e. sets modulo finite sets, (that is, an automorphism α of is completely determined by its action on C; see Theorem 8 of [4]). Shore also defined the notion of effectively nowhere simple sets.

Definition. An r.e. set A is effectively nowhere simple if there is a recursive function f such that for every i, Wf(i) ⊆ Wi − A and Wf(i) is infinite iff Wi − A is infinite. f is called a witness function for A.

Other than to produce examples of effectively nowhere simple sets and nowhere simple sets that are not effectively nowhere simple, Shore did not concern himself with the properties of effectively nowhere simple sets since he felt that effectively nowhere simple sets were unlikely to be lattice invariant in either E, the lattice of r.e. sets, or in .

Certain investigations have been made concerning the nature of classes of recursively enumerable sets, and the relation of such classes to the recursively enumerable indices of their sets. For instance, a theorem of Rice [3, Theorem XIV(a), p. 324] states that if A is the complete set of indices for a class of recursively enumerable sets (that is, if there is a class of recursively enumerable sets such that and if A is recursive, then either A = ⌀ or A = ω. A relate theorem by Rice and Shapiro [3, Theorem XIV(b), p. 324] can be stated as follows:

Let be a class of recursively enumerable sets, and let A be the complete set of indices for . Then A is r.e. if and only if there is an r.e. set D of canonical indices of finite sets Du, u ∈ D, such that

A somewhat similar theorem of Yates is the following: Let be a class of recursively enumerable sets which contains all finite sets. Let A be the complete set of indices for . Then there is a uniform recursive enumeration of the sets in if and only if A is recursively enumerable in 0(2)—that is, if and only if A is Σ3. A corollary of this is that if C is any r.e. set such that C(2)≡T⌀(2), there is a uniform recursive enumeration of all sets We such that We ≤TC [9, Theorem 9, p. 265].

The Classification Theorem for ℵ0-categorical strictly minimal sets says that if H is strictly minimal and ℵ0-categorical, either H has in effect no structure at all or is essentially an affine or projective space over a finite field. Zil′ber, in [Z2], showed that if H were a counterexample to this Classification Theorem it would interpret a rank 2, degree 1 pseudoplane. Cherlin later noticed (see [CHL, Appendices 2 and 3], for the proof) that the Classification Theorem is a consequence of the Classification Theorem for finite simple groups. In [Z4] and [Z5], Zil′ber found a quite different proof of the Classification Theorem using no deep group theory.

Meanwhile in [Z3], Zil′ber introduced the notion of envelope in an attempt to prove that no complete totally categorical theory T can be finitely axiomatizable. The idea of the proof was to show that if M is a model of such a T and H ⊆ M is strongly minimal, then an envelope of any sufficiently large finite subset of H is a finite model of any fixed finite subset of T. [Z3] contains an error, which Zil′ber has since corrected (in a nontrivial way).

In [CHL], Cherlin, Harrington and Lachlan used the Classification Theorem to expand and reorganize Zil′ber's work. In particular, they generalized most of his work to ℵ0-categorical, ℵ0-stable structures, proved the Morley rank is finite in these structures, and introduced the powerful Coordinatization Theorem (Theorem 3.1 of [CHL]; Proposition 1.14 of the present paper). They also showed that ℵ0-categorical, ℵ0-stable structures are not finitely axiomatizable using a notion of envelope that is the same as Zil′ber's except in one particularly perverse case; [CHL]'s notion of envelope is used throughout the current paper. Peretyat'kin [P] has found an example of an ℵ1-categorical finitely axiomatizable structure.

An important problem, widely treated in the analysis of the structure of degree orderings, is that of partial order and lattice embeddings. Thus for example we have the results on embeddings of all countable partial orderings in the Turing degrees by Kleene and Post [3] and in the r.e. T-degrees by Sacks [10]. For lattice embeddings the work on T-degrees culminated in the characterization of countable initial segments by Lachlan and Lebeuf [4]. For the r.e. T-degrees there has been a continuing line of progress on this question. (See Soare [20] and Lerman, Shore, and Soare [8].) Similar projects have been undertaken for the T-degrees below 0′ (Kleene and Post [3], Lerman [6]) as well as for most other degree orderings. The results have been used not only to analyse individual orderings but also to distinguish between them (Shore [16], [19], [17]).

The situation for α-jecursive theory, the study of recursion in (admissible) ordinals, is similar to, though not as well developed as, that for Turing degrees. All afinite partial orderings have been embedded even in the α-r.e. degrees (see Lerman [5]). Lattice embedding results are somewhat fragmentary however. In terms of initial segments even the question of the existence of a minimal α-degree has not been settled for all admissibles. (See Shore [12] for a proof for Σ2-admissible ordinals, however.) Results on more complicated lattices have only reached to the finite distributive ones for Σ3-admissible ordinals (see Dorer [1]).

In 1965 Zadeh introduced the concept of fuzzy sets. The characteristic of fuzzy sets is that the range of truth value of the membership relation is the closed interval [0, 1] of real numbers. The logical operations ⊃, ∼ on [0, 1] which are used for Zadeh's fuzzy sets seem to be Łukasiewciz's logic, where p ⊃ q = min(1, 1 − p + q), ∼ p = 1 − p. L. S. Hay extended in [4] Łukasiewicz's logic to a predicate logic and proved its weak completeness theorem: if P is valid then P + Pn is provable for each positive integer n. She also showed that one can without losing consistency obtain completeness of the system by use of additional infinitary rule.

Now, from a logical standpoint, each logic has its corresponding set theory in which each logical operation is translated into a basic operation for set theory; namely, the relation ⊆ and = on sets are translation of the logical operations → and ↔. For Łukasiewicz's logic, P Λ (P ⊃ Q). ⊃ Q is not valid. Translating it to the set version, it follows that the axiom of extensionality does not hold. Thus this very basic principle of set theory is not valid in the corresponding set theory.

We say that a pair of r.e. sets B and C split an r.e. set A if B ∩ C = ∅ and B ∪ C = A. Friedberg [F] was the first to study the degrees of splittings of r.e. sets. He showed that every nonrecursive r.e. set A has a splitting into nonrecursive sets. Generalizations and strengthenings of Friedberg's result were obtained by Sacks [Sa2], Owings [O], and Morley and Soare [MS].

The question which motivated both [LR] and this paper is the determination of possible degrees of splittings of A. It is easy to see that if B and C split A, then both B and C are Turing reducible to A (written B ≤TA and C ≤TA). The Sacks splitting theorem [Sa2] is a result in this direction, as are results by Lachlan and Ladner on mitotic and nonmitotic sets. Call an r.e. set A mitotic if there is a splitting B and C of A such that both B and C have the same Turing degree as A; A is nonmitotic otherwise. Lachlan [Lac] showed that nonmitotic sets exist, and Ladner [Lad1], [Lad2] carried out an exhaustive study of the degrees of mitotic sets.

The Sacks splitting theorem [Sa2] shows that if A is r.e. and nonrecursive, then there are r.e. sets B and C splitting A such that B <TA and C <TA. Since B is r.e. and nonrecursive, we can now split B and continue in this manner to produce infinitely many r.e. degrees below the degree of A which are degrees of sets forming part of a splitting of A. We say that an r.e. set A has the universal splitting property (USP) if for any r.e. set D ≤T A, there is a splitting B and C of A such that B and D are Turing equivalent (written B ≡TD).