We study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.

In this paper we introduce a recursive notation system O(Π3) of ordinals. An element of the notation system is called an ordinal diagram. The system is designed for proof theoretic study of theories of Π3-reflection. We show that for each α < Ω in O(Π3) a set theory KP Π3 for Π3-reflection proves that the initial segment of O(Π3) determined by α is a well ordering. Proof theoretic study for such theories will be reported in [ 4].

We consider a set generic over the arithmetic sets. A subset A of the natural numbers is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every -set of strings S, there is a string σ ⊂ A such that σ ∈ S or no extension of σ is in S. By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤ a) denote the set of degrees which are recursive in a.

We say a is a strong minimal cover of g if every degree strictly below a is less than or equal to g. In this paper we show that there are a degree a and a 1-generic degree g < a such that a is a strong minimal cover of g. This easily implies that there is a 1-generic degree without the cupping property. Jockusch [7] showed that every 2-generic degree has the cupping property. Slaman and Steel [17] and independently Cooper [3] showed that there are recursively enumerable degrees a and b < a such that no degree c < a joins b above a. Take a 1-generic degree g below b. Then g does not have the cupping property.

In [1], examples of types of U-rank 1 (i.e., minimal types) in the theories of separably closed fields were constructed, en route to displaying certain dimension phenomena. We construct here additional examples with U-rank 1 and of various transcendence degrees over arbitrary separably closed fields. Our examples include ones which are minimal but of infinite transcendence degree, i.e., not thin. Our interest in building new examples was piqued after seeing the role played by minimal types over separably closed fields in Hrushovski's analysis of abelian varieties. This article is the result of several working sessions between the authors at Wesleyan University and Paris 7, and was completed during the Model Theory of Fields program at MSRI in 1998. We are grateful for the hospitality and support of all three institutions. We thank Elisabeth Bouscaren and Françoise Delon for reading an earlier version of this paper, providing useful suggestions and corrections.

Let X be a compact metric space. A closed set K ⊆ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) > r is allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA0, WKL0 and ACA0. We also give some applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA0 version of this result for weakly located closed sets.