As is well known, the following are equivalent for any uniform ultrafilter U on an uncountable cardinal:

• (i) U is selective;

• (ii) U → ;

• (iii) U → .

In §1 of this paper, we consider this result in terms of M-ultrafilters (Definition 1.1), where M is a transitive model of ZFC (Zermelo-Fraenkel set theory with the axiom of choice). We define the partition properties and for M-ultrafilters (Definition 1.3), and characterize those M-ultrafilters that possess these properties (Theorem 1.5) so that the result mentioned at the beginning is subsumed as the special case that M is V, the universe of all sets. It turns out that the two properties have to be handled separately, and that, besides selectivity, we need to formulate additional conditions (Definition 1.4). The extra conditions become superfluous when M = V because they are then trivially satisfied. One of them is nothing new; it is none other than Kunen's iterability-of-ultrapowers condition.

In §2, we obtain characterizations of the partition properties I+ → and I+ → (Definition 2.3) of uniform ideals I on an infinite cardinal κ (Theorem 2.6). This is done by applying the main results of §1 to the canonical -ultrafilter in the Boolean-valued model constructed from the completion of the quotient algebra P(κ)/I. They are related to certain known characterizations of weakly compact and of Ramsey cardinals.

Our basic set theory is ZFC. In §1, it has to be supplemented by a new unary predicate symbol M and new nonlogical axioms that make M look like a transitive model of ZFC.

Buchholz [4] simplified the system of ordinal notations of the Schütte school (cf. [12]), by using the notion of collapsing functions (cf. [5]). In this paper we give a simple relationship between Buchholz's new system of ordinal notations and Takeuti's system of ordinal diagrams. From this simple relationship it turns out that the structures of these two systems are very close.

We give two systems OT(I) (§1) and OT(I, A) (§2) of ordinal notations which are considered generalizations of Buchholz's original system, where I and A are well-ordered sets. The original system OT of Buchholz [4] is OT(ω + 1, {0}) in our sense. Here the set OT(I) of ordinal notations is defined as a subset of the set Od(I) of ordinal diagrams in [6], and the set OT(I, A) of ordinal notations as a subset of the set O(I, A) of ordinal diagrams in [14].

One of the more significant achievements of twentieth century mathematics, especially from the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in the 1930's which provided a precise and robust definition of what it means for a problem to be computationally solvable, or decidable, and which showed that there are undecidable problems which arise naturally in logic and computer science. Indeed, when one is faced with a new computational problem, one of the first questions to be answered is whether the problem is decidable or undecidable. A problem is usually defined to be decidable if and only if it can be solved by some Turing machine, and the class of decidable problems defined in this way remains unchanged if “Turing machine” is replaced by any of a variety of other formal models of computation. The division of all problems into two classes, decidable or undecidable, is very coarse, and refinements have been made on both sides of the boundary. On the undecidable side, work in recursive function theory, using tools such as effective reducibility, has exposed much additional structure such as degrees of unsolvability. The main purpose of this survey article is to describe a branch of computational complexity theory which attempts to expose more structure within the decidable side of the boundary.

Motivated in part by practical considerations, the additional structure is obtained by placing upper bounds on the amounts of computational resources which are needed to solve the problem. Two common measures of the computational resources used by an algorithm are time, the number of steps executed by the algorithm, and space, the amount of memory used by the algorithm.

The problem mentioned in the title has already been investigated by J. Baumgartner, J. Stern, A. Miller and many others (see [2] and [5]). We prove here some generalizations of theorems of Miller and Stern from [2] and [5]. We use standard set-theoretical notation. Let

One can check that in the above definition we can replace “compact subset of ωω” by “closed nowhere dense subset of ω2” or “Fσ and meager subset of ω2” (as any Fσ subset of ω2 can be presented as a disjoint countable union of compact sets).

For functions f, g ϵ ωω we define f ≼ g if for all but finitely many n ϵ ω we have f(n) ≤ g(n). Let denote the least cardinality of a family A ⊆ ωω such that for any f ϵ ωω there is g ϵ A for which f ≼ g. It is easy to see that ≤ κω ≤ κ1. If f ϵ ωω then let ≼(f) = {h ϵωω: h ≼ f}.

We find an axiom which implies = ω1 → κ1 = ω1, and which can be preserved by any ccc notion of forcing of “small cardinality”. We construct also in a generic model many partitions of ωω into compact sets preserved not only by any random real extension, but also by Sacks' notion of forcing. This shows that from some point of view Miller's modification of Sacks' forcing (from [2]) is the “minimal” one able to destroy a partition of ωω into compact sets.

If U is a normal measure on κ then we can add indiscernibles for U either by Prikry forcing [P] or by taking an iterated ultrapower which will add a sequence of indiscernibles for over M. These constructions are equivalent: the set C of indiscernibles for added by the iterated ultrapower is Prikry generic for [Mat]. Prikry forcing has been extended for sequences of measures of length by Magidor [Mag], and his method readily extends to . In this case the measure U is replaced by a sequence of measures and the set C of indiscernibles is replaced by a system of indiscernibles for : is a function such that (κ, β) is a set of indiscernibles for (κ, β) for each . The equivalence between forcing and iterated ultra-powers still holds true for such sequences: there is an interated ultrapower j: V → M (which is defined in detail later in this paper) such that the system of indiscernibles for j() constructed by j is Magidor generic over M.

The construction of the system of indiscernibles works equally well for o(κ) ≧ κ +. Radin has defined a variant of Prikry forcing which also works for o(κ) > κ + ([R]; see also [Mi82] where Radin forcing is applied specifically to sequences of measures, rather than to hypermeasures as in Radin's paper), but Radin's forcing is weaker than Magidor's extension of Prikry forcing in the sense that the system of indiscernibles generated by the interated ultrapower is not Radin generic for j(), but only the set . That is, an indiscernible does not belong to a specific measure, but only to the whole sequence of measures on the cardinal κ.

Classes of forcings which add a real by forcing with branching conditions are examined, and conditions are found which guarantee that the generic real is of minimal degree over the ground model. An application is made to almost-disjoint coding via a real of minimal degree.

We prove that MM (Martin maximum) is equivalent (in ZFC) to the older axiom SPFA (semiproper forcing axiom). We also prove that SPFA does not imply SPFA+ or even PFA+ (using the consistency of a large cardinal).

We show in ZFC, assuming all reals have sharps, that a countable collection of Δ⅓-degrees without a minimal upper bound implies the existence of inner models with measurable cardinals.

Dominical categories are categories in which the notions of partial morphisms and their domains become explicit, with the latter being endomorphisms rather than subobjects of their sources. These categories form the basis for a novel abstract formulation of recursion theory, to which the present paper is devoted. The abstractness has of course its usual concomitant advantage of generality: it is interesting to see that many of the fundamental results of recursion theory remain valid in contexts far removed from their classic manifestations. A principal reason for introducing this new formulation is to achieve an algebraization of the generalized incompleteness theorem, by providing a category-theoretic development of the concepts and tools of elementary recursion theory that are inherent in demonstrating the theorem.

Dominical recursion theory avoids the commitment to sets and partial functions which is characteristic of other formulations, and thus allows for an intrinsic recursion theory within such structures as polyadic algebras. It is worthy of notice that much of elementary recursion theory can be developed without reference to elements.

By Gödel's generalized incompleteness theorem for consistent arithmetical system T we mean any statement of the following sort:

(1) if every recursive set is definable in T, then T is essentially undecidable [41]; or

(2) if all recursive functions are definable in T, then T is essentially undecidable [41]; or

(3) if every recursive set is definable in T, then T 0 and R 0 (the sets of Gödel numbers of the theorems and refutables of T) are recursively inseparable [39]; or

(4) if all re sets are representable in T, then T 0 is creative [28], [39]; or

(5) if T is a Rosser theory (i.e., all disjoint re sets are strongly separable in T), then T 0 and R 0 are effectively inseparable [39].

Answering a question of A. Kanamori, we prove that there is no Jónsson filter over the least Jónsson cardinal. We also notice that, assuming □κ, the successor κ+ cannot be Jónsson.

In this paper we give a closer analysis of the elementary properties of the Banach spaces C(K), where K is a totally disconnected, compact Hausdorff space, in terms of the Boolean algebra B(K) of clopen subsets of K. In particular we sharpen a result in [4] by showing that if B(K1) and B(K2) satisfy the same sentences with ≤ n alternations of quantifiers, then the same is true of C(K1) and C(K2). As a consequence we show that for each n there exist C(K) spaces which are elementarily equivalent for sentences with ≤ n quantifier alternations, but which are not elementary equivalent in the full sense. Thus the elementary properties of Banach spaces cannot be determined by looking at sentences with a bounded number of quantifier alternations.

The notion of elementary equivalence for Banach spaces which is studied here was introduced by the second author [4] and is expressed using the language of positive bounded formulas in a first-order language for Banach spaces. As was shown in [4], two Banach spaces are elementarily equivalent in this sense if and only if they have isometrically isomorphic Banach space ultrapowers (or, equivalently, isometrically isomorphic nonstandard hulls.)

We consider Banach spaces over the field of real numbers. If X is such a space, Bx will denote the closed unit ball of X, Bx = {x ϵ X∣ ∣∣x∣∣ ≤ 1}. Given a compact Hausdorff space K, we let C(K) denote the Banach space of all continuous real-valued functions on K, under the supremum norm. We will especially be concerned with such spaces when K is a totally disconnected compact Hausdorff space. In that case B(K) will denote the Boolean algebra of all clopen subsets of K. We adopt the standard notation from model theory and Banach space theory.

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

In [3] we have shown how the simplification of gap-1 morasses introduced in [4] can be extended to gap-2 morasses. As in the gap-1 case, the definition of simplified (κ, 2)-morasses (gap-2 morasses of height κ) makes sense for κ = ω, although the smallest size for Jensen's original gap-2 morasses was κ = ω1. The existence of simplified gap-1 morasses of height ω is provable in ZFC (see [2]), but the same cannot be true for gap-2 morasses, since the top level of a simplified (ω, 2)-morass is a simplified (ω1, 1)-morass, and the existence of simplified (ω1, 1)-morasses is not provable in ZFC. In this paper we prove the best existence theorem for simplified (ω, 2)-morasses that we can hope for:

Theorem 1.1. There is a simplified (ω, 2)-morass iff there is a simplified (ω1, 1)-morass.

Before giving the proof we briefly summarize the definition of simplified (ω, 2)-morasses. For a more thorough treatment, and proofs of some of the basic properties of simplified gap-2 morasses which will be used below, we refer the reader to [3]. Suppose ‹‹φζ ∣ ζ ≤ ω1›, ‹ℊζξ ∣ ξ < ξ ≤ ω1›› is a simplified (ω1, 1)-morass. (We are using the “expanded” version of the definition.) We assume the morass is neat (see [4]). For each ζ < ω1 let σζ be the split point of ℊζ, ζ + 1; i.e., ℊζ, ζ + 1 is a pair {id, b}, where id is the identity function, b ↾ σζ = id and b(σζ) = φζ. A simplified (ω, 2)-morass will describe the construction of this simplified (ω, 1)-morass from finite pieces. The finite pieces will be the initial segments of the morass picked out by an increasing sequence of natural numbers ‹ni ∣ i < ω ›. We call this piece level i of the (ω, 2)-morass, and we call the full simplified (ω1, 1)-morass level ω. To make sure the pieces are really finite, we require that φx and ℊxy are finite for x < y < ω.

The underlying modules of existentially closed ⊿-algebras are studied. Among other things, it is proved that they are all elementarily equivalent, and that all of them are existentially closed as modules if and only if ⊿ is regular. It is also proved that every saturated module in the appropriate elementary equivalence class underlies an ex. ⊿-algebra. Applications to some problems in module theory are given. A number of open questions are mentioned.

We describe a first-order theory of generalized sets intended to allow a similar treatment of sets and proper classes. The theory is motivated by the iterative conception of set. It has a ternary membership symbol interpreted as membership relative to a set-building step. Set and proper class are defined notions. We prove that sets and proper classes with a defined membership form an inner model of Bernays-Morse class theory. We extend ordinal and cardinal notions to generalized sets and prove ordinal and cardinal results in the theory. We prove that the theory is consistent relative to ZFC + (∃x) [x is a strongly inaccessible cardinal].

We shall be concerned here with weak axiomatic systems of set theory with a universal set. The language in which they are expressed is that of set theory—two primitive predicates, = and ϵ, and no function symbols (though some function symbols will be introduced by definitional abbreviation). All the theories will have stratified axioms only, and they will all have Ext (extensionality: (∀x)(∀y)(x = y· ↔ ·(∀z)(z ϵ x ↔ z ϵ y))). In fact, in addition to extensionality, they have only axioms saying that the universe is closed under certain set-theoretic operations, viz. all of the form

and these will always include singleton, i.e., ι′x exists if x does (the iota notation for singleton, due to Russell and Whitehead, is used here to avoid confusion with {x: Φ}, set abstraction), and also x ∪ y, x ∩ y and − x (the complement of x). The system with these axioms is called NF2 in the literature (see [F]). The other axioms we consider will be those giving ⋃x, ⋂x, {y: y ⊆x} and {y: x ⊆ y}. We will frequently have occasion to bear in mind that 〈 V, ⊆ 〉 is a Boolean algebra in any theory extending NF2. There is no use of the axiom of choice at any point in this paper. Since the systems with which we will be concerned exhibit this feature of having, in addition to extensionality, only axioms stating that V is closed under certain operations, we will be very interested in terms of the theories in question. A T-term, for T such a theory, is a thing (with no free variables) built up from V or ∧ by means of the T-operations, which are of course the operations that the axioms of T say the universe is closed under.

We set = ‹, ≤L , # ›, where is the set of degrees of nonconstructibility for countable sets of countable ordinals. We show how to define inductively over this structure the degrees of such sets of ordinals in Κ, the core model, and the next few core models thereafter, i.e. without reference to mice, premice or measurable cardinals

We introduce a well-founded relation < between filters on the space of descending sequences of ordinals. For each regular uncountable cardinal κ, the length of the relation is an ordinal o(κ) ≤ (2κ)+.

A model of ZFC is constructed in which the distributivity cardinal h is , and in which there are no ω 2-towers in [ω]ω. As an immediate corollary, it follows that any base-matrix tree in this model has no cofinal branches. The model is constructed via a form of iterated Mathias forcing, in which a mixture of finite and countable supports is used.

The system RM is the most well-understood (and to our opinion, also the most important) system among the logics developed by the Anderson and Belnap school. In this paper we investigate RM from a constructive point of view. For example, we give a new proof of the completeness of RM relative to the Sugihara matrix (first shown by Meyer), a proof in which a p.r. procedure is presented, applying which to a sentence A in RM language yields either a proof of it in RM or a refuting valuation for it in the Sugihara matrix SZ.

Two topics dealt with in this work deserve a special attention.

a) The admissibility of γ. This is a famous theorem of Meyer and Dunn. In [1] Anderson and Belnap emphasize that “the Meyer-Dunn argument … guarantees the existence of a proof of B, but there is no guarantee that the proof of B is related in any sort of plausible way to the proofs of A and Ā ∨ B.” In §2 we provide such a guarantee for the RM-case. In fact, we give there a direct method of obtaining a proof of B from given proofs of A and Ā ∨ B.

b) The relationships betweenRMand its full negation-implication fragment. RM is known ([1, pp. 148–149], and [3]) to be a conservative extension of (Sobociński 3-valued logic; see [4]). Anderson and Belnap admit [1, p. 149] that this fact came to them as a distinct surprise, since RM as a whole is far from being three-valued. In this paper, however, this “surprising” fact appears quite natural (see III.3). In fact, we show that , is the “hard core” of RM, since our proof of the completeness of RM is based in an essential way on the completeness of relative to the Sobociński matrix, and since the Gentzen-type calculus we develop for RM is a direct extension of a similar (but much simpler) calculus for . Because of the importance has in this work, we devote the first section to a constructive investigation of it.

We note, finally, that the Gentzen-type calculus mentioned above admits cut-elimination and normal-form techniques. (Such calculi were found till now only for RM without distribution.)