The notation that I shall use here for the logic of quantification is of the familiar kind wherein the letters ‘p’, ‘q’, etc. stand in place of unspecified statements and the letters ‘ƒ’, ‘g’, etc. stand in place of unspecified predicates. The present section will deal with the significance of this notation; the purpose and scope of the paper as a whole can better be indicated afterward, in §2.

By “predicates” I mean, not properties (or classes) and relations, but merely certain notational expressions. As a first approach they may be thought of as expressions like ‘walks,’ ‘is red,’ ‘touches,’ ‘gives to.’ Where ‘ƒ’, ‘g’, ‘h’, and ‘k’ represent these four predicates, we may read ‘ƒx’ ‘gy’, ‘hxy’, and ‘κxyz’ as ‘x walks,’ ‘y is red,’ ‘x touches y,’ ‘x gives y to z.’

We examine the multiplicity of complementation amongst subspaces of V∞. A subspace V is a complement of a subspace W if V ∩ W = {0} and (V ∪ W)* = V∞. A subspace is called fully co-r.e. if it is generated by a co-r.e. subset of a recursive basis of V∞. We observe that every r.e. subspace has a fully co-r.e. complement.

Theorem. If S is any fully co-r.e. subspace then S has a decidable complement.

We give an analysis of other types of complements S may have. For example, if S is fully co-r.e. and nonrecursive, then S has a (nonrecursive) r.e. nowhere simple complement.

We impose the condition of immunity upon our subspaces.

Theorem. Suppose V is fully co-r.e. Then V is immune iff there exist M1, M2 ∈ L(V∞), with M1supermaximal and M2k-thin, such that M1, ⊕ V = M2 ⊕ V = V∞.

Corollary. Suppose V is any r.e. subspace with a fully co-r.e. immune complement W(e.g., V is maximal or V is h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such that V ⊕ W = M ⊕ W = D ⊕ W = V∞.

We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspace V of V∞ is nowhere sound if (i) for all Q ∈ L(V∞) if Q ⊃ V then Q = V∞, (ii) V is immune and (iii) every complement of V is immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces.

We present a comprehensive study of the axiom schemas (induction and collection schemas for parameter free Σ n formulas) and some closely related schemas.

L'absence ou la présence de la propriété d'indépendance, introduite par Shelah, est sans aucun doute une mesure significative de la complexité, du point de vue de la théorie des modèles, d'une théorie instable. Il importe donc de distinguer les théories qui ont cette propriété de celles qui ne l'ont pas; le critère de Keisler [1] et de Shelah [5], qui consiste à compter le nombre de types qu'on peut obtenir sur un ensemble de paramètres de cardinal λ, n'emporte la décision que si l'on nie assez brutalement l'hypothèse du continu généralisée. Je propose ici de compter, étant donnée une partie X, de cardinal λ, d'un espace de types Si(M), quel peut être le cardinal de l'adhérence de X; ce point de vue équivaut au précédent si la théorie T est stable (voir la remarque après le Théorème 7); et si T n'a pas la propriété d'indépendance ce cardinal est au plus 2λ, tandis que si T a la propriété d'indépendance il peut atteindre 22λ (Théorème 7). Cela donne, indépendamment d'hypothèses de théorie des ensembles, une mesure quantitative de la plus grande complexité des espaces de types s'il y a propriété d'indépendance; et sous la forme du Théorème 8, cela devient un test très maniable dans les situations concrètes, car l'expérience m'a prouvé que les cohéritiers d'un type sont toujours faciles à déterminer.

Dans une première section, je considère un type complet p au dessus d'un modèle M d'une théorie complète T, et parmi les fils de p sur une extension élémentaire de M j'en distingue certains que j'appelle fils spéciaux de p: cette notion est naturelle et utile pour la suite, car le critère que j'ai décrit revient à prouver l'abondance de certains fils spéciaux d'un même type; on notera au passage le Théorème 3.

Le théorème de caractérisation de la propriété d'indépendance est prouvé dans une deuxième section, grâce à un résultat de combinatoire (Théorème 6); j'y montre aussi, à titre d'illustration, qu'un ordre total n'a jamais la propriété d'indépendance.

Let q0, q1,… be a standard enumeration of all partial recursive functions of one variable. For each i, let wi = range qi and for any recursively enumerable (r.e.) set α, let θα = {n | wn = α}. If A is a class of r.e. sets, let θA = the index set of A = {n | wn ∈ A}. It is the purpose of this paper to classify the possible recursive isomorphism types of index sets of finite classes of r.e. sets. The main theorem will also provide an answer to the question left open in [2] concerning the possible double isomorphism types of pairs (θα, θβ) where α ⊂ β.

The hyperarithmetical hierarchy assigns a degree of unsolvability hγ to each constructive ordinal γ. This assignment has the properties that h0 is the recursive degree and hγ+1 is the jump h′γ of hγ. For a limit ordinal λ < ω1 it is not so easy to define hγ. The original definitions used systems of notations for ordinals, see Spector [6]. There are also later notation-free definitions due to Shoenfield (unpublished) and to Hensel and Putnam [4].

Let A be a subset of ω, the set of natural numbers. The degree of A is its degree of recursive unsolvability. We say that A is rich if every degree above that of A is represented by a subset of A. We say that A is poor if no degree strictly above that of A is represented by a subset of A. The existence of infinite poor (and hence nonrich) sets was proved by Soare [9].

Theorem 1. Suppose that A is infinite and not rich. Then every hyperarith-metical subset H of ω is recursive in A.

In the special case when H is arithmetical, Theorem 1 was proved by Jockusch [4] who employed a degree-theoretic analysis of Ramsey's theorem [3]. In our proof of Theorem 1 we employ a similar, degree-theoretic analysis of a certain generalization of Ramsey's theorem. The generalization of Ramsey's theorem is due to Nash-Williams [6]. If A ⊆ ω we write [A]ω for the set of all infinite subsets of A. If P ⊆ [ω]ω we let H(P) be the set of all infinite sets A such that either [A]ω ⊆ P = ∅. Nash-Williams' theorem is essentially the statement that if P ⊆ [ω]ω is clopen (in the usual, Baire topology on [ω]ω) then H(P) is nonempty. Subsequent, further generalizations of Ramsey's theorem were proved by Galvin and Prikry [1], Silver [8], Mathias [5], and analyzed degree-theoretically by Solovay [10]; those results are not needed for this paper.

Let M be a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by defining d(g, h) = Ω{2−n: g (xn) ≠ h(xn) or g−1 (xn) ≠ h−1 (xn)} where {xn : n ∈ ω} is an enumeration of M An automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1 closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In the present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms of M which can be considered as an atomic model of some theory naturally associated to M. We do it in a general context of weak models for second-order quantifiers.

The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks.

This paper is a sequel to our earlier paper, “Limit Ultrapowers”, [6]. In that paper we introduced the limit ultrapower construction and proved that is isomorphic to a limit ultrapower of if and only if every PCΔ class which contains also contains . In Section 1 of this paper we introduce the more general limit ultraproduct construction, and in Section 2 we prove that, for any class K of relational systems, a relational system is isomorphic to a limit ultraproduct of members of K if and only if every PCΔ class which includes K also contains . As a consequence, the property of K being an intersection of PCΔ classes is characterized purely set-theoretically by the property of K being closed under isomorphisms and limit ultraproducts.

In Section 3 we apply limit ultraproducts to obtain model-theoretic conditions equivalent to the set-theoretic condition that every α-complete ultrafilter is γ+-complete. The first result, Theorem 3.7, was announced in the abstract [8], and it is also closely related to a result which was stated without proof in [10], namely Theorem 2 of that paper.

In Sections 4 and 5 we apply our results in order to improve a theorem of Craig in [2]. Craig considered the logic L(Q), where Q is a set of cardinals, obtained from ordinary first order logic by adding for each α ϵ Q the quantifier “there exist at least α”.

The decision procedures to be described in this paper constitute simplifications of methods previously developed by G. H. von Wright. The decision problems for both the systems under consideration have already been solved, but the known solutions are hopelessly impractical. Our methods for S4 and M, while not “practical” in the sense that they can be applied quickly and easily to any formula, do constitute a vast improvement over any other known methods. It appears, for example, that our methods (with the aid of very little ingenuity) will yield decisions readily when applied to modal functions of degree two (or less) with three (or fewer) distinct propositional variables.

Following Soare [11] we say a recursively enumerable (r.e.) degree a has the anticupping (a.c.) property if there is a nonzero r.e. degree b < a such that for no r.e. c < a does a = b ∪ c.

Cooper [2] and Yates showed that 0′ has the a.c. property, while Harrington (see Miller [6]) proved that every high r.e. degree a has the a.c. property.

The recent paper by Ambos-Spies, Jockusch, Shore and Soare [1] describes a general theoretical framework for cupping and capping below 0′ which seems likely to be useful in a wider context.

Definition. (1) We say b is strongly noncuppable belowa if 0 < b < a and, for each d < a, b ∪ d ≠ a.

(2) We say an r.e. a has the strong anticupping property if there is an r.e. b which is strongly noncuppable below a.

The main results on cupping in (≤ 0′) are due to Epstein, Posner and Robinson. For instance it is known (Posner and Robinson [8]) that the s.a.c. property fails for 0′.

We prove below that r.e. degrees with the s.a.c. property do exist, hence obtaining a nonzero r.e. degree a such that (≤ a) ≢e(≤h) for any high r.e. degree h. This result, obtained by means of an infinite injury construction in (≤ 0′), extends Theorem 2 of [3], proved using a finite injury construction in (≤ 0′).

Our main source of notation and terminology is [3].

An important technique in large cardinal set theory is that of extending an elementary embedding j: M → N between inner models to an elementary embedding j* : M[G] → N[G*] between generic extensions of them. This technique is crucial both in the study of large cardinal preservation and of internal consistency. In easy cases, such as when forcing to make the GCH hold while preserving a measurable cardinal (via a reverse Easton iteration of α-Cohen forcing for successor cardinals α), the generic G* is simply generated by the image of G. But in difficult cases, such as in Woodin's proof that a hypermeasurable is sufficient to obtain a failure of the GCH at a measurable, a preliminary version of G* must be constructed (possibly in a further generic extension of M[G]) and then modified to provide the required G*. In this article we use perfect trees to reduce some difficult cases to easy ones, using fusion as a substitute for distributivity. We apply our technique to provide a new proof of Woodin's theorem as well as the new result that global domination at inaccessibles (the statement that d(κ) is less than 2κ for inaccessible κ, where d(κ) is the dominating number at κ) is internally consistent, given the existence of 0#.

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

There are properties of finite structures that are expressible with the use of Hilbert's ∈-operator in a manner that does not depend on the actual interpretation for ∈-terms. but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu.

T. Jech and K. Prikry introduced the concept of precipitous ideals as a counterpart of measurable cardinals for small cardinals (Jech and Prikry [1]). To get a precipitous ideal on ℵ1( W. Mitchell used the Cohen extension by the standard Levy collapse that makes κ = ℵ1, where κ is a measurable cardinal in the ground model (Jech, Magidor, Mitchell and Prikry [2]). His proof essentially used the fact that , where is the notion of forcing of Levy collapse and j is the elementary embedding obtained by a normal ultrafilter on κ.

On the other hand, we know that has the κ-chain condition. In this paper, we show that the κ-chain condition for notions of forcing plays an essential role for preserving normal precipitous ideals. Namely,

Theorem 1. Let κ be a regular uncountable cardinal and I a normal ideal on κ. Let be a notion of forcing with the κ-chain condition. Then, I is precipitous iff ⊩“the ideal on κ generated by I is precipitous”.

As an application of Theorem 1, we have the following theorem.

Theorem 2. Let κ be a regular uncountable cardinal, and Γ be a κ-saturated normal ideal on κ. Then, {a < κ; the ideal of thin sets on a is precipitous} has either Γ-measure one or Γ-measure zero, and the ideal of thin sets on κ is precipitous iff {α< κ; the ideal of thin sets on α is precipitous) has Γ-measure one.

The standard topological representation of a Boolean algebra via the clopen sets of a Stone space requires a nonconstructive choice principle, equivalent to the Boolean Prime Ideal Theorem. In this article, we describe a choice-free topological representation of Boolean algebras. This representation uses a subclass of the spectral spaces that Stone used in his representation of distributive lattices via compact open sets. It also takes advantage of Tarski’s observation that the regular open sets of any topological space form a Boolean algebra. We prove without choice principles that any Boolean algebra arises from a special spectral space X via the compact regular open sets of X; these sets may also be described as those that are both compact open in X and regular open in the upset topology of the specialization order of X, allowing one to apply to an arbitrary Boolean algebra simple reasoning about regular opens of a separative poset. Our representation is therefore a mix of Stone and Tarski, with the two connected by Vietoris: the relevant spectral spaces also arise as the hyperspace of nonempty closed sets of a Stone space endowed with the upper Vietoris topology. This connection makes clear the relation between our point-set topological approach to choice-free Stone duality, which may be called the hyperspace approach, and a point-free approach to choice-free Stone duality using Stone locales. Unlike Stone’s representation of Boolean algebras via Stone spaces, our choice-free topological representation of Boolean algebras does not show that every Boolean algebra can be represented as a field of sets; but like Stone’s representation, it provides the benefit of a topological perspective on Boolean algebras, only now without choice. In addition to representation, we establish a choice-free dual equivalence between the category of Boolean algebras with Boolean homomorphisms and a subcategory of the category of spectral spaces with spectral maps. We show how this duality can be used to prove some basic facts about Boolean algebras.

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t. This was proved for unary similarity types by Per Lindström [17] with a counting argument. We extend his method to arbitrary similarity types.

The concepts “classical valuation” and “supervaluation” were introduced by van Fraassen around 1966, to provide a semantic analysis of the then extant axiomatic systems of free logic. Consider an atomic sentence

and a “partial” model which fails to interpret c. Then (1) has no truth value in , nor does

While the valuelessness of (1) was found intuitively acceptable, that of (2) was not. Indeed, (2) and all other tautologies are theorems of free logic.

Van Fraassen found a way to accommodate both intuitions. He interprets the unproblematic atomic sentences as usual, while “interpreting” those like (1) by simply assigning them a truth-value in arbitrary fashion. Then a truth-value for every sentence can be defined in the usual way; the result van Fraassen calls a “classical valuation” of the language. The arbitrary element in any given classical valuation is then eliminated by passage to the “supervaluation” over , which agrees with the classical valuations where they agree among themselves, and otherwise is undefined. In the supervaluation over , (1) is valueless but (2) true (since true on all classical valuations), as was required.

There is a slight, but crucial oversimplification in the preceding account. Evaluation of the sentence

requires prior evaluation of the open formula

But here mere assignment of truth-value is not enough; a whole set must be arbitrarily assigned as extension. The quantification over classical valuations involved in passage to the supervaluation thus involves an implicit quantification over subsets of the domain of : supervaluations are second order.

In March 1973, W. Veldman [1] discovered that, by a slight modification of a Kripke-model, it was possible to give an intuitionistic proof of the completeness-theorem for the intuitionistic predicate calculus (IPC) with respect to modified Kripke models. The modification was the following: Let f represent absurdity, then we allow the possibility that and we agree that, for all sentences ϕ, , if . Just one modified Kripke model is constructed such that validity in implies derivability in IPC. While usually one thinks of as some subset of ⋃ n Nat n and of as the discrete natural ordering in ⋃ n Nat n, in Veldman's model , is a spread and , where Γα and Γβ are sets of sentences associated with α, resp. β, is a nondiscrete ordering.

In the completeness-proofs, both for Beth and for Kripke models that we present here, we consider only models over ⋃n Nat n, with the natural discrete ordering and we need validity in all models, not just in one, to get derivability in IPC. Also we have to modify the definition of a model in a somewhat different way than Veldman did. We agree that if ∨s[M⊨s f], then M⊨sϕ for each s ∈ ⋃n Nat n and for each sentence ϕ.

One can view a single model of the type constructed in [1] as the result of throwing together all the models of (the type constructed in) this paper into one big model, which has the somewhat strange properties mentioned above.

We consider first-order logic only. A theory S will be called locally interpretable in a theory T if every theorem of S is interpretable in T. If S is locally interpretable in T and T is consistent then S is consistent. Most known relative consistency proofs can be viewed as local interpretations. The classic examples are the cartesian interpretation of the elementary theorems of Euclidean n-dimensional geometry into the first-order theory of real closed fields, the interpretation of the arithmetic of integers (rational numbers) into the arithmetic of positive integers, the interpretation of ZF + (V = L) into ZF, the interpretation of analysis into ZFC, relative consistency proofs by forcing, etc. Those interpretations are global. Under fairly general conditions local interpretability implies global interpretability; see Remarks (7), (8), and (9) below.

We define the type (interpretability type) of a theory S to be the class of all theories T such that S is locally interpretable in T and vice versa. There happen to be such types and they are partially ordered by the relation of local interpretability. This partial ordering is of lattice type and has the following form:

The lattice is distributive and complete and satisfies the infinite distributivity law of Brouwerian lattices:

We do not know if the dual law

is true. We will show that the lattice is algebraic and that its compact elements form a sublattice and are precisely the types of finitely axiomatizable theories, and several other facts.