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)

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)

A generic computation of a subset $A$ of $\mathbb{N}$ consists of a computation that correctly computes most of the bits of $A$, and never incorrectly computes any bits of $A$, but which does not necessarily give an answer for every input. The motivation for this concept comes from group theory and complexity theory, but the purely recursion theoretic analysis proves to be interesting, and often counterintuitive. The primary result of this paper is that there are no minimal pairs for generic (...) computability, answering a question of Jockusch and Schupp. (shrink)

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led (...) to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ (...) on A (equivalently, it is not definable by a computable $\Sigma _\alpha $ formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α. (shrink)