Abstract In this article, we will show that ${\rm{R}}{{\rm{T}}^2} + WK{L_0}$ is a ${\rm{\Pi }}_1^1$ -conservative extension of ${\rm{B\Sigma }}_3^0$ .

Abstract We show that no nontrivial principal ideal of the enumeration degrees is linearly ordered: in fact, below every nonzero enumeration degree one can embed every countable partial order. The result can be relativized above any total degree: if a,b are enumeration degrees, with a total, and a < b, then in the degree interval (a,b), one can embed every countable partial order.

Abstract We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let 2-RANbe the principle that for every realXthere is a realRwhich is 2-random relative toX. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theoryRCA0and soRCA0+ 2-RANimplies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is not conservative overRCA0for arithmetic sentences. Thus, from the Csima–Mileti fact that the existence of random reals has infinitary-combinatorial consequences we can conclude that 2-RANhas non-trivial arithmetic consequences. In Section 4, we show that 2-RANis conservative overRCA0+BΣ2for -sentences. Thus, the set of first-order consequences of 2-RANis strictly stronger thanP−+IΣ1and no stronger thanP−+BΣ2.

Abstract We show that there is a lowT-upper bound for the class ofK-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in T-degrees for which there is a lowT-upper bound.

Abstract. In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).

Abstract We show there is a non-recursive r.e. set A such that if W is any low r.e. set. then the join W ⊕ A is also low. That is. A is “almost deep”. This answers a question of Joekusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.)

Abstract We study the proof–theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT k n denote Ramsey's theorem for k –colorings of n –element sets, and let RT <∞ n denote (∀ k )RT k n . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k –coloring of the n –element sets of natural numbers, there is an infinite homogeneous set X with X ″ ≤ T 0 ( n ) . Let I Σ n and B Σ n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + I Σ 2 + RT 2 2 is conservative over RCA 0 + I Σ 2 for Π 1 1 statements and that RCA 0 + I Σ 3 + RT <∞ 2 is Π 1 1 -conservative over RCA 0 + I Σ 3 . It follows that RCA 0 + RT 2 2 does not imply B Σ 3 . In contrast, J. Hirst showed that RCA 0 + RT <∞ 2 does imply B Σ 3 , and we include a proof of a slightly strengthened version of this result. It follows that RT <∞ 2 is strictly stronger than RT 2 2 over RCA 0 .

One recursively enumerable real $\alpha$ dominates another one $\beta$ if there are nondecreasing recursive sequences of rational numbers $(a[n]:n\in\omega)$ approximating $\alpha$ and $(b[n]:n\in\omega)$ approximating $\beta$ and a positive constant C such that for all n, $C(\alpha-a[n])\geq(\beta-b[n])$. See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin's Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350--359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the $\Omega$-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350--359]. Second, we show that the sets in a universal Martin-Löf test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Löf test.

Abstract There is a comeager set contained in the set of 1-generic reals and a first order structure such that for any real number X. there is an element of which is recursive in X if and only if there is a presentation of which is recursive in X.

Abstract We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.

Theorem. There is a non-empty Π10 class of reals, each of which computes a real of minimal (Turing) degree. Corollary. WKL ⊢ “there is a minimal Turing degree”. This answers a question of H. Friedman and S. Simpson.

Abstract We show that the Π20 enumeration degrees are not dense. This answers a question posed by Cooper.

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

A first-order sentence Φ is Σ2 if there is a quantifier-free formula Θ such that Φ has the form . The Σ2-theory of a structure for a language ℒ is the set of Σ2-sentences of ℒ true in . It was shown independently by Lerman and Shore (see [Le, Theorem VII.4.4]) that the Σ2-theory of the structure = 〈D, ≤ 〉 is decidable, where D is the set of degrees of unsolvability and ≤ is the standard ordering of D. This result is optimal in the sense that the Σ3-theory of is undecidable, a result due to J. Schmerl. (For a proof, see [Le, Theorem VII.4.5]. As Lerman has pointed out, this proof should be corrected by defining θσ to be ∀xσ1(x) rather than ∀x(ψ(x)→ σ1(x)).) Nonetheless, in this paper we extend the decidability result of Lerman and Shore by showing that the Σ2-theory of is decidable, where ⋃ is the least upper bound operator and 0 is the least degree. Of course ⋃ is definable in , but many interesting degree-theoretic results are expressible as Σ2-sentences in the language of ∪ but not as Σ2-sentences in the language of . For instance, Simpson observed that the Posner-Robinson cupping theorem could be used to show that for any nonzero degrees a, b, there is a degree g such that b ≤ a ⋃ g, and b ⋠ g (see [PR, Corollary 6]). However, the Posner-Robinson technique does not seem to suffice to decide the Σ2-theory of ∪. We introduce instead a new method for coding a set into the join of two other sets and use it to decide this theory.

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees. This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

Ambos-Spies (1984a) showed that the two basic nondistributive lattices can be embedded in Rp-T, the polynomial-time Turing degrees of the recursive sets. We introduce more general techniques to extend his results to show that every recursive lattice can be embedded in Rp-T. In addition to lattice-theoretic representation theorems, we use the scheme of priority style arguments coupled with “looking back” techniques presented in Shinoda and Slaman (1988, 1990). We also generalize the density type results of Ladner (1975) and many others to settle the full extension of the embedding problem for Rp-T. Combined with the logical analysis of sentences with one alternation of quantifiers (Shore 1978, Lerman 1983), these results suffice to decide the full ∀∃-theory of Rp-T. They also give a strong nonhomogeneity result: the p-time degrees of the sets recursive in (and, if desired, p-time above) two distinct sets A and B are almost never isomorphic. The situation for the p-time many-one degrees is quite different. We decide the extension of the embedding problem (differently than for Rp-T) but not the ∀∃-theory.

Since its introduction in [K1-Po], the upper semilattice of Turing degrees has been an object of fascination to practitioners of the recursion-theoretic art. Starting from relatively simple concepts and definitions, it has turned out to be a structure of enormous complexity and richness. This paper is a contribution to the ongoing study of this structure. Much of the work on Turing degrees may be formulated in terms of the embeddability of certain first-order structures in a structure whose universe is some set of degrees and whose relations, functions, and constants are natural degree-theoretic ones. Thus, for example, we know that if {P, ≤P) is a partial ordering of cardinality at most ℵ1 which is locally countable—each point has at most countably many predecessors—then there is an embedding where D is the set of all Turing degrees and

Abstract Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X′, its Turing jump, is recursive in ∅′ and high if X′ computes ∅″. Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of A ⊕ W is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turing functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that (W ⊕ A)′ is forced to disagree with Φ(−;A′). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a “moderately” deep degree: There is a low nonzero degree whose join with any other low degree is not high.

Abstract Posner [6] has shown, by a nonuniform proof, that every degree has a complement below 0′. We show that a 1-generic complement for each set of degree between 0 and 0′ can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above ∅′. In the second half of the paper, we show that the complementation of the degrees below 0′ does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems.

Abstract We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P−) together with Σ2-collection (BΣ2). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither lown nor highn-1, while true, cannot be established in P− + BΣn+1. Consequently, no bounded fragment of first order arithmetic establishes the facts that the highn and lown jump hierarchies are proper on the recursively enumerable degrees.

Abstract Let A and B be subsets of the reals. Say that AK≥ B, if there is a real a such that the relation “x ∈ B” is uniformly ⊿1 (a, A) in . This reducibility induces an equivalence relation ≡K on the sets of reals; the ≡K-equivalence class of a set is called its Kleene degree. Let be the structure that consists of the Kleene degrees and the induced partial order ≥. A substructure of that is of interest is , the Kleene degrees of the sets of reals. If sharps exist, then there is not much to , as Steel [9] has shown that the existence of sharps implies that has only two elements: the degree of the empty set and the degree of the complete set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in ; in the context of V = L, Hrbáček has shown that is dense and has no minimal pairs. The Hrbáček results led Simpson [6] to make the following conjecture: if V = L, then forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Gödel's maximal thin set is the infimum of two strictly larger elements of . The second main result deals with the notion of jump in . Let A′ be the complete Kleene enumerable set relative to A. Say that A is low-n if A(n) has the same degree as ⊘(n), and A is high-n if A(n) has the same degree as ⊘(n+1). Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete set in L. They have also shown that various other sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x# does not exist, then there is an element of that, for all n, is neither low-n nor high-n. In §2, ZFC is used to show that, for all n, if A is and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp].

Abstract Let p be a set. A function Φ is uniformly Σ1(p) in every admissible set if there is a Σ1 formula ϕ in the parameter p so that ϕ defines Φ in every Σ1-admissible set which includes p. A theorem of Van de Wiele states that if Φ is a total function from sets to sets then Φ is uniformly Σ1 in every admissible set if and only if it is E-recursive. A function is ESp-recursive if it can be generated from the schemes for E-recursion together with a selection scheme over the transitive closure of p. The selection scheme is exactly what is needed to insure that the ESP-recursively enumerable predicates are closed under existential quantification over the transitive closure of p. Two theorems are established: a) If the transitive closure of p is countable then a total function on sets is ESp-recursive if and only if it is uniformly Σ1(p) in every admissible set. b) For any p, if Φ is a function on the ordinal numbers then Φ is ESP-recursive if and only if it is uniformly Σ1(p) in every admissible set.