The ω-Turing degrees

&
Annals of Pure and Applied Logic 165 (9):1512-1532 (2014)
  Copy   BIBTEX

Abstract

In this paper we initiate the study of the ω-Turing reducibility between sequences of sets of natural numbers. We shall prove that the induced degree structure is an extension of the structure of the Turing degrees and that the two structures are closely connected, but different enough. Further we shall prove some definability results for the local theory of the newly defined structure

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2014.04.017

Other Versions

No versions found

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Continuity of capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.
The jump operator on the ω-enumeration degrees.Hristo Ganchev & Ivan N. Soskov - 2009 - Annals of Pure and Applied Logic 160 (3):289-301.
Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
Automorphisms in the PTIME-Turing degrees of recursive sets.Christine Ann Haught & Theodore A. Slaman - 1997 - Annals of Pure and Applied Logic 84 (1):139-152.
Upper bounds on locally countable admissible initial segments of a Turing degree hierarchy.Harold T. Hodes - 1981 - Journal of Symbolic Logic 46 (4):753-760.
On the Degree Structure of Equivalence Relations Under Computable Reducibility.Keng Meng Ng & Hongyuan Yu - 2019 - Notre Dame Journal of Formal Logic 60 (4):733-761.
Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
Embeddings in the Strong Reducibilities Between 1 and npm.Phil Watson - 1997 - Mathematical Logic Quarterly 43 (4):559-568.
The jump operation for structure degrees.V. Baleva - 2005 - Archive for Mathematical Logic 45 (3):249-265.
Turing degrees of hypersimple relations on computable structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.

Analytics

Added to PP
2015-01-22

Downloads
41 (#1,355,281)

6 months
6 (#1,537,359)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

The jump operator on the ω-enumeration degrees.Hristo Ganchev & Ivan N. Soskov - 2009 - Annals of Pure and Applied Logic 160 (3):289-301.
On a question of G. E. Sacks.Donald A. Martin - 1966 - Journal of Symbolic Logic 31 (1):66-69.
Degrees joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
On a Problem of G. E. Sacks.A. H. Lachlan - 1967 - Journal of Symbolic Logic 32 (1):125-125.

View all 6 references / Add more references