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.

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.

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

The Turing jump can easily be iterated any finite number of times. The challenge is posed by by transfinite iterations. a(ω) has an intuitively compelling definition: {‹m, n›: n ∈ a(m)}. Starting with Putnam et al. [1], [2], [9] and culminating in Jockusch-Simpson [8] and Hodes [6], recent work has justified this ω-jump and extended it through .

Of great use are the master codes of Jensen [3], [7]. Briefly, a Δn(Lβ)-master code is a complete Δn(Lβ) set of ordinals, with supremum as small as possible. Connections with classical recursion theory are tight. When the Δn(Lβ) master codes are reals, they are Turing equivalent. If a is a Δn(Lβ) MC, then a′ is a Δn + 1(Lβ) MC. Intuitively satisfying transfinite jumps, such as the ω-jump above, produce a Turing jump hierarchy equal to an initial segment of the master codes.

Hodes capitalized on these facts by defining 0α, α < , set-theoretically as the degree of the αth MC which is a real, and then proving the equivalence of a jump-theoretic definition of 0α. The successor codes are jumps of their predecessors, and for a limit λ, 0λ is the minimum of a set of degrees associated with {0α: α: < λ}.

Let T be a countable, complete, ω-stable, nonmultidimensional theory. By Lascar [7], in Teq there is in every dimension of T a type with Lascar rank ωα for some α. We give sufficient conditions for α to coincide with the level of that dimension in Pillay's [10] RK-hierarchy of dimensions computed in Teq. In particular, this is fulfilled for modules.

A categorical structure suitable for interpreting polymorphic lambda calculus (PLC) is defined, providing an algebraic semantics for PLC which is sound and complete. In fact, there is an equivalence between the theories and the categories. Also presented is a definitional extension of PLC including “subtypes”, for example, equality subtypes, together with a construction providing models of the extended language, and a context for Girard's extension of the Dialectica interpretation.

We show that M ⊨ κ is a completely Ramsey cardinal iff there is a Rowbottom M-ultrafilter on κ.

L. van den Dries proved that the theory of n-valued rings has a model companion. We show here that this result is still true when the valuation rings are required to satisfy given inclusion relations (we restrict ourselves to the case of residual characteristic zero).

Subtle cardinals were first introduced in a paper by Jensen and Kunen [JK]. They show that if κ is subtle then ◇κ holds. Subtle cardinals also play an important role in [B1], where Baumgartner proposed that certain large cardinal properties should be considered as properties of their associated normal ideals. He shows that in the case of ineffables, the ideals are particularly useful, as can be seen by the following theorem, κ is ineffable if and only if κ is subtle and Π½-indescribable and the subtle and Π½-indescribable ideals cohere, i.e. they generate a proper, normal ideal (which in fact turns out to be the ineffable ideal).

In this paper we examine properties of subtle cardinals and consider methods of forcing that destroy the property of subtlety while maintaining other properties. The following is a list of results.

1) We relativize the following two facts about subtle cardinals:

i) if κ is n-subtle then {α < κ: α is not n-subtle} is n-subtle, and

ii) if κ is (n + 1)-subtle then {α < κ: α is n-subtle} is in the (n + 1)-subtle filter to subsets of κ:

i′) if A is an n-subtle subset of κ then {α ϵ A: A ∩ α is not n-subtle} is n-subtle, and

ii′) if A is an (n + 1)-subtle subset of κ then {α ϵ A: A ∩ α is n-subtle} is (n + 1)-subtle.

2) We show that although a stationary limit of subtles is subtle, a subtle limit of subtles is not necessarily 2-subtle.

3) In §3 we use the technique of forcing to turn a subtle cardinal into a κ-Mahlo cardinal that is no longer subtle.

4) In §4 we extend the results of §3 by showing how to turn an (n + 1)-subtle cardinal into an n-subtle cardinal that is no longer (n + 1)-subtle.

We investigate some relations between omitting types of a countable theory and some notions defined in terms of the real line, such as for example the ideal of meager subsets of R. We also try to express connections between the logical structure of a theory and the existence of its countable models omitting certain families of types.

It is well known that assuming MA we can omit < nonisolated types. But MA is rather a strong axiom. We prove that in order to be able to omit < nonisolated types it is sufficient to assume that the real line cannot be covered by less than meager sets; and this is in fact the weakest possible condition. It is worth pointing out that by means of forcing we can easily obtain the model of ZFC in which R cannot be covered by < meager sets. It suffices to add to the ground model Cohen generic reals.

We also formulate similar results for omitting pairwise contradictory types. It turns out that from some point of view it is much more difficult to find the family of pairwise contradictory types which cannot be omitted by a model of T, than to find such a family of possibly noncontradictory types. Moreover, for any two countable theories T1, T2 without prime models, the existence of a family of κ types which cannot be omitted by a model of T1 is equivalent to the existence of such a family for T2. This means that from the point of view of omitting types all theories without prime models are identical. Similar results hold for omitting pairwise contradictory types.

Une conséquence de la classification des théories complètes d'algèbres de Boole par Tarski [5] est que la théorie élémentaire d'une algèbre de Boole A est déterminée par le type d'isomorphisme du treillis de ses idéaux définissables et, pour chacun de ces idéaux, par le nombre d'atomes du quotient de A par cet idéal lorsque ce nombre est fini. Une remarque analogue peut être faite à propos des cas particuliers d'algèbres de Boole munies d'un idéal distingué étudiés par Ershov [1] et par Jurie et Touraille [3]; dans to us ces cas, c'est la simplicité des treillis possibles qui permet la classification des théories complètes. Le résultat principal de cet article est que, dans le cas général d'une algèbre de Boole munie d'une famille quelconque d'idéaux distingués, la théorie d'un modèle peut encore être caractérisée grâce à une structure algébrique sur l'ensemble de ses idéaux définissables. Il s'agit d'une structure d'algèbre de Heyting munie d'une opération unaire sa définie par sa(K) = {a: a/K est sans atome}, et cette structure s'avère être engendrée par les idéaux distingués du modèle. La méthode utilisée est l'élimination directe des quantificateurs, par réductions successives des formules. Elle nécessite des propriétés algébriques et topologiques qui sont données aux §§1 et 2: on introduit au §1 la notion d'algèbre de Heyting étoilée, c'est-à-dire d'algèbre de Heyting munie d'une opération unaire * vérifiant des égalités qui permettent de rendre compte, d'une certaine façon, de la dérivation de Cantor-Bendixon; le §2 est consacré à des propriétés topologiques qui, dans le cas de l'espace de Stone d'une algèbre de Boole A, permettent d'éclaircir les relations possibles entre les atomes des quotients de A par des idéaux différents.