We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.

We simultaneously generalize Silver’s perfect set theorem for co-analytic equivalence relations and Harrington-Marker-Shelah’s Dilworth-style perfect set theorem for Borel quasi-orders, establish the analogous theorem at the next definable cardinal, and give further generalizations under weaker definability conditions.

The purpose is to study the strength of Ramsey’s Theorem for pairs restricted to recursive assignments of k-many colors, with respect to Intuitionistic Heyting Arithmetic. We prove that for every natural number $k \ge 2$, Ramsey’s Theorem for pairs and recursive assignments of k colors is equivalent to the Limited Lesser Principle of Omniscience for ${\rm{\Sigma }}_3^0$ formulas over Heyting Arithmetic. Alternatively, the same theorem over intuitionistic arithmetic is equivalent to: for every recursively enumerable infinite k-ary tree there is some $i < k$ and some branch with infinitely many children of index i.

In this paper we study nonmultidimensional superstable theories T, possibly in an uncountable language, and develop some techniques permitting the generalisation of certain results from the finite rank (and/or countable language) context to the general case.

We prove, among other things, the following: there is a set A0 of parameters, which has cardinality at most ∣T∣, and in the finite-dimensional case is finite, such that over any B ⊇ A0 there is a locally atomic model. One of the consequences of this is that if C is the monster model of T, φ(x) is a formula over A0, φC ⊇ X and (X, φC) satisfies the Tarski-Vaught condition after adding names for A0, then there is an elementary substructure M of C containing A0 such that φM = X. Applications to the spectrum problem will appear in [Ch-P].

In fact, all the components of the machinery we develop are already present in the general theory. One such component involves a stratification of the regular types of T using a generalized notion of weakly minimal formula. This appears in [Sh, Chapter V and the proof of IX.2.4] and also in [P2]. A second component involves definable groups which arise as ‘binding” groups. The existence of such groups, under certain hypotheses on the behavior of nonorthogonality, is due to Hrushovski [Hr1], and our use of them to help obtain “j-constructible” models is similar to their use in [Bu-Sh].

In his excellent review of four notes of Skolem on recursive functions of natural numbers Bernays states: “The question whether every relation y = f(x1,…, xn) with a recursive function ƒ is primitive recursive remains undecided.” Actually, the question is easily answered in the negative by a form of the familiar diagonal argument.

We start with the ternary recursive relation R, referred to in the review, such that R(x, y, 0), R(x, y, 1), … is an enumeration of all binary primitive recursive relations.

We investigate the effects of various forcings on several forms of the Halpern– Läuchli theorem. For inaccessible κ, we show they are preserved by forcings of size less than κ. Combining this with work of Zhang in [17] yields that the polarized partition relations associated with finite products of the κ-rationals are preserved by all forcings of size less than κ over models satisfying the Halpern– Läuchli theorem at κ. We also show that the Halpern–Läuchli theorem is preserved by <κ-closed forcings assuming κ is measurable, following some observed reflection properties.

Assume T is a small superstable theory. We introduce the notion of a flat Morley sequence, which is a counterpart of the notion of an infinite Morley sequence in a type p, in case when p is a complete type over a finite set of parameters. We show that for any flat Morley sequence Q there is a model M of T which is τ-atomic over {Q}. When additionally T has few countable models and is 1-based, we prove that within M there is an infinite Morley sequence I, with I ⊂ dcl(Q), such that M is prime over I.

We prove a p-adic, local version of the Monotonicity Theorem for P-minimal structures. The existence of such a theorem was originally conjectured by Haskell and Macpherson. We approach the problem by considering the first order strict derivative. In particular, we show that, for a wide class of P-minimal structures, the definable functions f : K → K are almost everywhere strictly differentiable and satisfy the Local Jacobian Property.

A grafted frame is a new kind of frame which combines a modal frame and some relevance frames. A grafted model consists of a grafted frame and a truth-value assignment. In this paper, the grafted frame and the grafted model are constructed and used to show the completeness of S1. The implications of S1-completeness are discussed.

A grafted frame does not combine two kinds of frames simply by putting relations defined in the components together. That is, the resulting grafted frame is not in the form of <W,R,R′>, or more generally, in the form of <W, R, R′,R″>,…>, which consists of a non-empty set with several relations defined on it.1 Rather, it resembles the construction of fibering proposed by D. M. Gabbay and M. Finger (see [4] and [3]). On a grafted frame, some modal worlds, which belong to the initial modal frame, are attached by some relevance frames.

However, these two semantics have important differences. Consider the combined semantics involving semantics of relevance logic and modal logic. A fibred model and a grafted model proposed in this paper differ in the following respects. First, a fibred model is constructed from a class of modal models and a class of relevance models. A grafted model consists of a grafted frame and a truth-value assignment, where the grafted frame is constructed from a modal frame and some relevance frames, and the assignment is a union of a modal truth-value assignment VM and some relevance truth-value assignments VR. VM (VR) defined in this paper is not the same as the assignment contained in a modal (relevance) model. Second, in a fibred model each relevance world is associated (or fibred) with a modal model and each modal world with a relevance model.2 To be the grafted frame on which a grafted model is based, it is enough to have some modal worlds attached by some relevance frames. Moreover, no relevance world is associated with a modal frame in the grafted frame. Third, fibred models are intended to provide an appropriate semantics to combined logics. Grafted frames and grafted models are inspired to characterize S1, which, containing only one modality □, is not a combined logic. It is shown in this paper that S1 is sort of a meta-logic of the intersection of S0.4 and F, where S0.4, a new system proposed in this paper, is in turn a meta-logic of the relevance logic.

I investigate the relationships between three hierarchies of reflection principles for a forcing class $\Gamma $ : the hierarchy of bounded forcing axioms, of $\Sigma ^1_1$ -absoluteness, and of Aronszajn tree preservation principles. The latter principle at level $\kappa $ says that whenever T is a tree of height $\omega _1$ and width $\kappa $ that does not have a branch of order type $\omega _1$ , and whenever ${\mathord {\mathbb P}}$ is a forcing notion in $\Gamma $ , then it is not the case that ${\mathord {\mathbb P}}$ forces that T has such a branch. $\Sigma ^1_1$ -absoluteness serves as an intermediary between these principles and the bounded forcing axioms. A special case of the main result is that for forcing classes that don’t add reals, the three principles at level $2^\omega $ are equivalent. Special attention is paid to certain subclasses of subcomplete forcing, since these are natural forcing classes that don’t add reals.

We show that the first order theory of the lattice <ω(S) of finite dimensional closed subsets of any nontrivial infinite dimensional Steinitz Exhange System S has logical complexity at least that of first order number theory and that the first order theory of the lattice (S∞) of computably enumerable closed subsets of any nontrivial infinite dimensional computable Steinitz Exchange System S∞ has logical complexity exactly that of first order number theory. Thus, for example, the lattice of finite dimensional subspaces of a standard copy of ⊕ωQ interprets first order arithmetic and is therefore as complicated as possible. In particular, our results show that the first order theories of the lattice (V∞) of c.e. subspaces of a fully effective ℵ0-dimensional vector space V∞ and the lattice of c.e. algebraically closed subfields of a fully effective algebraically closed field F∞ of countably infinite transcendence degree each have logical complexity that of first order number theory.