We show that there are Π5 formulas in the language of the Turing degrees, [Formula: see text], with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L2 = x ≥ y|x″ = y″} in any jump ideal containing 0. There are also Σ6&Π6 and Π8 formulas that define the relations w = x″ and w = x', respectively, in any such ideal [Formula: see text]. In the language with just ≤ (...) the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π2 or Σ2 formula in the language with just ≤ defines L2 or L2. Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of [Formula: see text] is fixed on every degree above 0″ and every relation on [Formula: see text] which is invariant under the double jump or under join with 0″ is definable over [Formula: see text] if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in [Formula: see text]. (shrink)

This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...) systems of reverse mathematics. While retaining the usual base theory and working still within second order arithmetic, theorems are described that range from those far below the usual systems to ones far above. (shrink)

The occasion of a retiring presidential address seems like a time to look back, take stock and perhaps look ahead.Institutionally, it was an honor to serve as President of the Association and I want to thank my teachers and predecessors for guidance and advice and my fellow officers and our publisher for their work and support. To all of the members who answered my calls to chair or serve on this or that committee, I offer my thanks as well. Your (...) work was both needed and appreciated.A major component of the efforts of the Association is devoted to our publications. My first important task as President was to deal with the need to reorganize the reviews section of the JSL and eventually to move it to the BSL. Appropriately enough, my first administrative job for the Association, some thirty years ago, was to serve on a committee to plan a reorganization of the reviews. I thank all those who helped with this transition and who took over the task of running the new reviews section. I hope that it will be another thirty years before further major changes are needed in this area and that someone else will be making them. (shrink)

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...) (RT₂²) splits into a stable version (SRT₂²) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for RT₂² and SRT₂²). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL₀, DNR, and BΣ₂. We show, for instance, that WKL₀ is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is Π₁¹-conservative over the base system RCA₀. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply SRT₂² (and so does not imply RT₂²). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and RT₂² on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions. (shrink)

We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. (...) In this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$, r- $\Pi _{2}^{1}$, and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic. (shrink)

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $\scr{D}_{h}$ . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of $\scr{D}_{h}$ . Corollaries include the decidability of the two quantifier theory of $\scr{D}_{h}$ and the undecidability of its three quantifier theory. The key tool in the proof is a (...) new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of $\omega _{1}^{CK}$ . Somewhat surprisingly, the set theoretic analog of this forcing does not preserve ω₁. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of $\scr{D}_{h}$. (shrink)

There are $\Pi_5$ formulas in the language of the Turing degrees, D, with ≤, ∨ and $\vedge$ , that define the relations $x" \leq y"$ , x" = y" and so $x \in L_{2}(y)=\{x\geqy|x"=y"\}$ in any jump ideal containing $0^(\omega)$ . There are also $\Sigma_6$ & $\Pi_6$ and $\Pi_8$ formulas that define the relations w = x" and w = x', respectively, in any such ideal I. In the language with just ≤ the quantifier complexity of each of these definitions (...) increases by one. On the other hand, no Π2 or Σ2 formula in the language with just ≤ defines L2 or $x\inL_{2}(y)$ . Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of I is fixed on every degree above 0" and every relation on I that is invariant under double jump or joining with 0" is definable over I if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in I. Similar direct coding arguments show that every hyperjump ideal I is rigid and biinterpretable with second order arithmetic with set quantification ranging over sets with hyperdegrees in I. Analogous results hold for various coarser degree structures. (shrink)

At the 1993 Annual meeting of the Association for Symbolic Logic, the Council of the association voted to establish a new journal to be called The Bulletin of Symbolic Logic. The intended goal of the Council was to produce a journal that would be both accessible and of interest to as wide an audience as possible, with the stated purpose of keeping the logic community abreast of important developments in all parts of our discipline. The first issue was to appear (...) in March of 1995 and you now have it in your hands.In accordance with the Council resolution, we intend to publish primarily two types of papers. The first section of The Bulletin, Articles, will usually be devoted to works of an expository or survey nature. These papers will generally present topics of broad interest in a way that should be accessible to a large majority of the members of the Association. Topics will be drawn from all areas of logic including mathematical or philosophical logic, logic in computer science or linguistics, the history or philosophy of logic, logic education and applications of logic to other fields. One view of a role that this section of The Bulletin will play is as an ongoing handbook of logic. (shrink)

If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...) the minimum element of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family. (shrink)

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for (...) any ideal of the r.e. degrees. (shrink)

iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...) of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space. (shrink)

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets modulo (...) the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order with least element 0, the degree of the computable sets, and greatest element 1 or 0′, the degree of K. Post's problem then asks if there are any other elements of.The solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].

We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.

We investigate the relationship of the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low 2.

We present some abstract theorems showing how domination properties equivalent to being $\overline{GL}_{2}$ or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in $\overline{GL}_{2}$ is recursively enumerable in a 1-generic degree strictly below it. Our major new result is (...) that every array nonrecursive degree is r.e. in some degree strictly below it. Our analysis of array nonrecursiveness and construction of generic sequences below ANR degrees also reveal a new level of uniformity in these types of results. (shrink)

Recall that [Formula: see text] is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that [Formula: see text] is dense, i.e. satisfies [Formula: see text]. Our proof combines an oracle construction with hyperarithmetical theory.