The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P− + BΣ2. The proof has two components: a lemma that in any model of P− + BΣ2, if B is recursively enumerable and incomplete then IΣ1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.

We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is ${\rm{\Delta }}_\alpha ^0 $-complete for some α. To prove this, we extend Montalbán’s η-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinal α and a cone in the Turing degrees such that the exact complexity of computing an isomorphism between the given structure and another copy ${\cal B}$ in the cone is a c.e. degree in ${\rm{\Delta }}_\alpha ^0\left( {\cal B} \right)$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions.

An ω-model (a model in which all natural numbers are standard) of the predicative fragment of Quine's set theory “New Foundations” (NF) is constructed. Marcel Crabbé has shown that a theory NFI extending predicative NF is consistent, and the model constructed is actually a model of NFI as well. The construction follows the construction of ω-models of NFU (NF with urelements) by R. B. Jensen, and, like the construction of Jensen for NFU, it can be used to construct α-models for any ordinal α. The construction proceeds via a model of a type theory of a peculiar kind; we first discuss such “tangled type theories” in general, exhibiting a “tangled type theory” (and also an extension of Zermelo set theory with Δ0 comprehension) which is equiconsistent with NF (for which the consistency problem seems no easier than the corresponding problem for NF (still open)), and pointing out that “tangled type theory with urelements” has a quite natural interpretation, which seems to provide an explanation for the more natural behaviour of NFU relative to the other set theories of this kind, and can be seen anachronistically as underlying Jensen's consistency proof for NFU.

Let A2 be the axiomatic system of second order arithmetic as described in [2]. One of the models of A2 is the “principal model” Mpr consisting of all integers and all sets of integers. Obviously there exist many denumerable ω-models elementarily equivalent to Mpr and we shall deal in this paper with some questions pertaining to this family which we denote by .

In §1 we define a rather natural relation ε between two denumerable families of sets of integers. From the upward Skolem-Löwenheim theorem it follows easily that there exists a family ordered by ε in the type ω1, but it is not immediately obvious whether there exist a subfamily of not well-ordered by ε. In the present paper we construct such a family of type η. ω1 where η is the order type of rationals and indicate some applications to hyperdegrees.

We adopt the terminology and notation of [2], with the only change that we adjoin to the language of A2 the constants ν0, ν1, … for the consecutive numerals 0, 1, 2, … and axioms which characterise them:

Also we modify the axioms of A2 given in [2] by prefixing them by general quantifiers bounded either to S or to N.

Let P be any one of the following combinatorial properties: weak P-pointness, weak (semi-) Q-pointness, weak (semi-)selectivity, ω-closedness. We deal with the following two questions: (1) What is the least cardinal k such that there exists an ideal with k many generators that does not have the property P? (2) Can one extend every ideal with the property P to a prime ideal with the property P?

We consider the quantifier hierarchy of Takahashi [1972] and show how it gives rise to reflection theorems for some large cardinals in ZF, a new natural subtheory of Zermelo's set theory, a potentially useful new reduction of the consistency problem for Quine's NF, and a sharpening of another reduction of this problem due to Boffa.

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.

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

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.

We define a σ-ideal on the set of functions ωω with the property that a real x ∈ ωω is a Hechler real over V if and only if x omits all Borel sets in . In fact we define a topology on ωω related to Hechler forcing such that is the family of first category sets in . We study cardinal invariants of the ideal .

In [1, §4], my ‘proof’ that GH1 has the finite model property is incorrect; there are considerable obscurities towards the end of §1, particularly on p. 33; and I should have exhibited the finite models for GH1. In §1 of this paper I expand the analysis of the sub-directly irreducible models for GH1 which I give in §1 of [1]. In §2 I give a correct proof that GH1 has the finite model property. In §3 I exhibit these finite models as models on certain ordered sets.

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

The history of the Gentzenization of relevant logics goes back to Kripke [17], who in 1959 Gentzenized R→ and went on to prove its decidability. Formulae were separated by commas on the left side of the turnstile, the commas just representing nested implications. Kripke employed just a singleton formula to the right of the turnstile. He also considered adding negation, as well as other connectives, but it was not until 1961 that Belnap and Wallace, in [5], Gentzenized and proved its decidability, though their Gentzenization employed commas on both sides of the turnstile. Subsequently, in 1966, the logic R without distribution, now called LR (for lattice R), was Gentzenized in a similar style by Meyer in [20]. He also went on to show decidability for LR by extending Kripke's argument. Later, in 1969, Dunn Gentzenized R+ (published in [1], pp. 381–391) using two structural connectives (commas and semicolons) to the left of the turnstile, and with a single formula to the right. Here, the commas represent conjunction and the semicolons represent an intensional conjunction, called “fusion”. This is all nicely set out in McRobbie [19], where he also introduces left-handed Gentzenizations and analytic tableaux for a number of fragments of relevant logics. In 1979, further work on distributionless logic was done by Grishin, in a series of papers, including [16], in which he produced a Gentzenization of quantified RW without distribution (which we will call LRWQ), and used it to prove the decidability of this quantified logic.

We compare several closely related continuum invariants, i.e., a, ae. ap in two forcing models. And we shall ask some open questions in this field.

It is shown (in ZF) that every hereditarily countable set has rank less than ω2, and that if ℵ1 is singular then there are hereditarily countable sets of all ranks less than ω2.

Conjecture (1) of [Ma83] is confirmed here by the following result: if 3 ≤ α < ω, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form S ⊆ T (asserting that one binary relation is included in another), which is provable with α + 1 variables, but not provable with only α variables (using a special sequent calculus designed for deducing properties of binary relations).

Intuitively, a topological space is a set together with some notion of “nearness”. Classically, this notion of nearness is usually described by a collection of open sets. With the development of Non-standard analysis by Abraham Robinson [11], we have an alternative way to describe this notion. If X is any set and *X is a nonstandard extension of X then we can describe a topology on X by means of a relationship of “infinitely close” on some points of X. In many ways this latter approach is more intuitive and leads to more straightforward proofs [11] than the classical approach. The first section of this paper explores the connections between these two approaches. In the main section of the paper we extend the notion of “infinitely close” to infinite points of *X. In the final section we give a very intuitive characterization of the compact-open topology (when the domain is locally compact) and use it to give quick, straight-forward proofs of the usual facts about this topology [1], [2]. This last section can be read independently of the second section.