Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On cototality and the skip operator in the enumeration degrees


Authors: Uri Andrews, Hristo A. Ganchev, Rutger Kuyper, Steffen Lempp, Joseph S. Miller, Alexandra A. Soskova and Mariya I. Soskova
Journal: Trans. Amer. Math. Soc. 372 (2019), 1631-1670
MSC (2010): Primary 03D30
DOI: https://doi.org/10.1090/tran/7604
Published electronically: May 9, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A set $ A\subseteq \omega $ is cototal if it is enumeration reducible to its complement,  $ \overline {A}$. The skip of $ A$ is the uniform upper bound of the complements of all sets enumeration reducible to $ A$. These are closely connected: $ A$ has cototal degree if and only if it is enumeration reducible to its skip. We study cototality and related properties, using the skip operator as a tool in our investigation. We give many examples of classes of enumeration degrees that either guarantee or prohibit cototality. We also study the skip for its own sake, noting that it has many of the nice properties of the Turing jump, even though the skip of $ A$ is not always above $ A$ (i.e., not all degrees are cototal). In fact, there is a set that is its own double skip.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D30

Retrieve articles in all journals with MSC (2010): 03D30


Additional Information

Uri Andrews
Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
Email: andrews@math.wisc.edu

Hristo A. Ganchev
Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
Email: ganchev@fmi.uni-sofia.bg

Rutger Kuyper
Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
Email: mail@rutgerkuyper.com

Steffen Lempp
Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
Email: lempp@math.wisc.edu

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
Email: jmiller@math.wisc.edu

Alexandra A. Soskova
Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
Email: asoskova@fmi.uni-sofia.bg

Mariya I. Soskova
Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
Email: msoskova@math.wisc.edu

DOI: https://doi.org/10.1090/tran/7604
Received by editor(s): December 2, 2016
Received by editor(s) in revised form: January 2, 2018, and April 21, 2018
Published electronically: May 9, 2019
Additional Notes: The third author was supported by John Templeton Foundation grant 15619: “Mind, Mechanism and Mathematics: Turing Centenary Research Project”.
The fourth author was partially supported by AMS-Simons Foundation Collaboration Grant 209087 and a binational NSF grant DMS-1101123 entitled “Collaboration in Computability”.
This research was carried out while the fourth and fifth authors were visiting the University of Sofia in Summer 2015 and while the last author was visiting the University of Wisconsin–Madison in Fall 2015.
The fifth author was partially supported by grant #358043 from the Simons Foundation.
The last two authors were supported by National Science Fund of Bulgaria grant #02/16 from 19.12.2016.
Article copyright: © Copyright 2019 American Mathematical Society