It is a theorem of Rowbottom [12] that if κ is measurable and I is a normal prime ideal on κ, then for each λ < κ,

In this paper a natural structural property of ideals, distributivity, is considered and shown to be related to this and other ideal theoretic partition relations.

The set theoretical terminology is standard (see [7]) and background results on the theory of ideals may be found in [5] and [8]. Throughout κ will denote an uncountable regular cardinal, and I a proper, nonprincipal, κ-complete ideal on κ. NSκ is the ideal of nonstationary subsets of κ, and Iκ = {X ⊆ κ∣∣X∣<κ}. If A ∈ I+ (= P(κ) − I), then an I-partition of A is a maximal collection W ⊆, P(A) ∩ I+ so that X ∩ Y ∈ I whenever X, Y ∈ W, X ≠ Y. The I-partition W is said to be disjoint if distinct members of W are disjoint, and in this case, for denotes the unique member of W containing ξ. A sequence 〈Wα ∣ α < η} of I-partitions of A is said to be decreasing if whenever α < β < η and X ∈ Wβ there is a Y ∈ Wα such that X ⊆ Y. (i.e., Wβ refines Wα).

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces, , of a recursively presented vector space V∞ has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all of these models, the algebraic closure of a set is nontrivial. (The formal definition of the algebraic closure of a set S, denoted cl(S), is given in §1, however in vector spaces, cl(S) is just the subspace generated by S, in Boolean algebras, cl(S) is just the subalgebra generated by S, and in algebraically closed fields, cl(S) is just the algebraically closed subfield generated by S.)

In this paper, we give a general model theoretic setting (whose precise definition will be given in §1) in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the models which we study is that the algebraic closure of set is just itself, i.e., cl(S) = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class of n-dimensional partial orderings.

§1. Introduction. Sacks [16] showed that every computably enumerable (c.e.) degree > 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a Δ2 splitting above each proper predecessor (by ‘splitting’ we understand ‘nontrivial splitting’). Arslanov [1] showed that 0′ has a d.c.e. splitting above each c.e. a < 0′. On the other hand, Lachlan [11] proved the existence of a c.e. a < 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [10] showed that one could take a = 0′. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0′.

Heterogeneous splittings are best considered in the context of cupping and non-cupping. Posner and Robinson [15] showed that every nonzero Δ2 degree can be nontrivially cupped to 0′, and Arslanov [1] showed that every c.e. degree > 0 can be d.c.e. cupped to 0′ (and hence since every d.c.e., or even n-c.e., degree has a nonzero c.e. predecessor, every n-c.e. degree > 0 is d.c.e. cuppable). Cooper [4] and Yates (see Miller [13]) showed the existence of degrees noncuppable in the c.e. degrees. Moreover, the search for relative cupping results was drastically limited by Cooper [5], and Slaman and Steel [17] (see also Downey [9]), who showed that there is a nonzero c.e. degree a below which even Δ2 cupping of c.e. degrees fails.

We prove below what appears to be the strongest possible of such nonsplitting and noncupping results.

The purpose of this paper is to put on record some theorems relating to improvements in the primitive frame of combinatory logic. These improvements were, for the most part, suggested by the work of Rosser, who formulated a weakened system of combinatory logic in which the rules had a simple character not possessed by those of the original system. In the latter the rules B, C, W, K were in reality axiom-schemes, and their postulation amounted to assuming infinitely many axioms. Rosser had rules of procedure such that no propositions were deducible from them except in combination with axioms (or previously proved propositions); moreover, the conclusion of each rule was uniquely determined by the premises. He also eliminated equality as a primitive term, defining it (essentially) according to the traditional method. This paper shows that these and related advantages apply to certain formulations of the full system of combinatory logic, so far as it concerns the theory of combinators.

The method of procedure is as follows. Instead of setting up a primitive frame at the start and then deriving its properties, I begin (after some preliminary explanations in §2) by stating in §3 the properties which it is desired to establish. The next few sections are devoted to the formulation and proof of certain general theorems concerning possible bases for the system of §3. These theorems are, perhaps, more general than is necessary for the immediate purpose, but they are of some interest on their own account. A formulation in terms of the primitives of original system (i.e., B, C, W, and K), which is of the same general type as Rosser's formulation, is obtained at the end of §6. In §7 are discussed the changes in this formulation which are sufficient in order to base it on the primitive combinators S and K of Schönfinkel.

We prove that a form of the Erdӧs property (consistent with V = L[Hω2] and strictly weaker than the Weak Chang's Conjecture at ω1), together with Bounded Martin's Maximum implies that Woodin's principle ψAC holds, and therefore . We also prove that ψAC implies that every function f: ω1 → ω1 is bounded by some canonical function on a club and use this to produce a model of the Bounded Semiproper Forcing Axiom in which Bounded Martin's Maximum fails.

Recursion theory has been dominated by one example. The notion of a dominical category was introduced (see [2] and [3]) at least in part in the hope of subverting this dominance. The structures of number theory, freed from this original context, led to much of modern algebra with a consequent enrichment of number theory itself: it seemed not unreasonable to attempt to contribute, however modestly, to a similar development of recursion theory. Thus (in the loosest sort of analogy) recursion categories are intended to stand in relation to the class of partial recursive functions as rings do to the rational integers.

But if such a generalization is to serve its intended purpose, it ought to allow examples substantially different in spirit from the prototype. Recursion categories are, of course, the proper generalization of classical recursion theory. As a novice in this formidable field I am incapable of encompassing its full extent and must rely on the advice of others (I thank in particular R. DiPaola) in concluding that most of these earlier generalizations are not of this character. Indeed, the examples of recursion categories so far adduced (cf., in addition to the references above, [1] and [4]) are themselves closely tied to the classical one.

We attempt here to open the door to radically disparate examples by proving an existence theorem allowing the construction of recursion categories in a wide, and so far unexplored, variety of contexts very distant from that of the natural or ordinal numbers and their subsets, the locus of the traditional theory.

In order to do this, it has been necessary to introduce a number of unfamiliar notions—unfamiliar, that is, even in the context of the earlier discussion of dominical categories. This novelty is perhaps mitigated by the fact that, however unfamiliar, they cannot be said to be unusual, as the discussion later will show. We mention in particular those of a “formally free semigroup”, which retains the indexation function of a free semigroup, while giving up the characteristic universal property and that of “uniform generation”, which generalizes finite generation in the fashion assorted to our argument.

Let Nk denote the set of words over the alphabet Σk = {1, …, k}. Nk contains the null word which is denoted λ. We consider decision problems for various first-order interpreted predicate languages in which the variables range over Nk (k ≧ 2). Our main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in Section 4, settles the decision problem for any language constructed on the basis of the relations and functions listed below.

The starting point of this article is an old question asked by Feferman in his paper on Hancock's conjecture [6] about the strength of . This theory is obtained from the well-known theory ID1 by restricting fixed point induction to formulas that contain fixed point constants only positively. The techniques used to perform the proof-theoretic analysis of also permit to analyze its transfinitely iterated variants . Thus, we eventually know that

We apply Hrushovski-Fraïsseé's amalgamation procedure to obtain a theory of fields of prime characteristic of Morley rank 2 equipped with a definable additive subgroup of rank 1.

The attempt to find usable diagrams for n terms of the sort devised by John Venn seems to have originated with Venn himself, who published diagrams for up to five classes (the fifth class, however, was shaped like a doughnut, and contained an area outside itself — like the hole in the doughnut). Venn then suggested that “if we wanted to use a diagram for six terms (x, y, z, w, v, u) the best plan would probably be to take two five-term figures, one for the u part and one for the non-u part of all the other combinations …” Such a method would, as Venn admits, be somewhat confusing to the eye, and thus fail to fulfil one of the major purposes of the diagram; nevertheless, it is a method which could be extended to cover n classes.

Venn also suggests (but without illustration) another method for drawing diagrams for n terms: “… the rule of formation would be very simple. We should merely have to begin by drawing any closed figure, and then proceed to draw others subject to the one condition that each intersect once, and once only, all the existing subdivisions produced by those which had gone before.” Then, in a rather surprising footnote, he adds: “It will be found that when we adhere to continuous figures, instead of the discontinuous five-term figure given above, there is a tendency for the resultant outlines thus successively drawn to assume a comb-like shape after the first four or five. If we begin by circles or other rounded figures the teeth are curved, if by parallelograms then they are straight.

It is consistent that there is a set mapping from the four-tuples of ωn into the finite subsets with no free subsets of size tn for some natural number tn. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into the finite subsets with no infinite free sets. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into ωn with no uncountable free sets.

It is proved that the following conditions are equivalent:

(a) there exists a complete, atomless, σ–centered Boolean algebra, which does not contain any regular, atomless, countable subalgebra.

(b) there exists a nowhere dense ultrafilter on ω.

Therefore, the existence of such algebras is undecidable in ZFC. In “forcing language” condition (a) says that there exists a non–trivial σ–centered forcing not adding Cohen reals.

Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify the minimal axioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very often equivalent to the theorem over the base theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of only four logical systems. The latter plus the base theory are called the ‘Big Five’ and the associated equivalences are robust following Montalbán, i.e., stable under small variations of the theorems at hand. Working in Kohlenbach’s higher-order RM, we obtain two new and long series of equivalences based on theorems due to Bolzano, Weierstrass, Jordan, and Cantor; these equivalences are extremely robust and have no counterpart among the Big Five systems. Thus, higher-order RM is much richer than its second-order cousin, boasting at least two extra ‘Big’ systems.

We improve results of Marczewski, Frankiewicz, Brown, and others comparing the ω-ideals of measure zero, meager, Marczewski measure zero, and completely Ramsey null sets; in particular, we remove CH from the hypothesis of many of Brown's constructions of sets lying in some of these ideals but not in others. We improve upon work of Marczewski by constructing, without CH, a nonmeasurable Marczewski measure zero set lacking the property of Baire. We extend our analysis of ω-ideals to include the completely Ramsey null sets relative to a Ramsey ultrafilter and obtain all 32 possible examples of sets in some ideals and not others, some under the assumption of MA, but most in ZFC alone. We also improve upon the known constructions of a Marczewski measure zero set which is not Ramsey by using a set theoretic hypothesis which is weaker than those used by other authors. We give several consistency proofs: one concerning the relative sizes of the covering numbers for the meager sets and the completely Ramsey null sets; another concerning the size of non; and a third concerning the size of add. We also study those classes of perfect sets which are bases for the class of always first category sets.

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.

In my paper [1], with which I assume the reader is familiar, I defined an arithmetic theory of constructions ATC and gave an interpretation of intuitionistic arithmetic HA in ATC. I proved that, in a suitable sense, every formula provable in HA is also provable in ATC. I proved the converse of this result only for positive sentences. In the present paper I will prove in full generality that any formula of HA which is provable in ATC is already provable in HA. In a later paper I shall use this result to obtain new information about certain extensions of HA by addition of higher types.

It is shown that the constructive four-valued logic N4 can be faithfully embedded into the modal logic S4. This embedding is used to obtain complete, cut-free display sequent calculi for N4 and C4, the modal logic of consistency over N4. C4 is a natural monotonic base system for semantics-based non-monotonic reasoning.

We try to count the number of countable models M of T with a fixed set Q = Φ(M) of realizations of a type Φ. Also, for stable T, we define an ordinal rank measuring multiplicity of types, with additivity properties similar to those of U-rank.