Yuval Gabay

Postdoctoral research position, Department of Mathematics, Ben-Gurion University of the Negev

Double Jump Inversions and Strong Minimal Covers in the Turing Degrees

Richard Shore

Mathematical logic

Abstract: Decidability problems for (fragments of) the theory of the structure D of Turing degrees, form a wide and interesting class, much of which is yet unsolved. Lachlan showed in 1968 that the first order theory of D with the Turing reducibility relation is undecidable. Later results concerned the decidability (or undecidability) of fragments of this theory, and of other theories obtained by extending the language (e.g. with 0 or with the Turing jump operator). Proofs of these results often hinge on the ability to embed certain classes of structures (lattices, jump-hierarchies, etc.) in certain ways, into the structure of Turing degrees. The first part of the dissertation presents two results which concern embeddings onto initial segments of D with known double jumps, in other words a double jump inversion of certain degree structures onto initial segments. These results may prove to be useful tools in uncovering decidability results for (fragments of) the theory of the Turing degrees in languages containing the double jump operator.

The second part of the dissertation relates to the problem of characterizing the Turing degrees which have a strong minimal cover, an issue first raised by Spector in 1956. Ishmukhametov solved the problem for the recursively enumerable degrees, by showing that those which have a strong minimal cover are exactly the r.e. weakly recursive degrees. Here we show that this characterization fails outside the r.e. degrees, and also construct a degree below 0' which is not weakly recursive, thereby answering a question from Ishmukhametov's paper.

PhD

PhD