Schnorr trivial sets and truth-table reducibility

&
Journal of Symbolic Logic 75 (2):501-521 (2010)
  Copy   BIBTEX

Abstract

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1268917492

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,296

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

Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Hyperimmune-free degrees and Schnorr triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
Schnorr triviality and genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Lowness for the class of Schnorr random sets.B. Kjös-Hanssen, A. Nies & F. Stephan - 2005 - Notre Dame Journal of Formal Logic 35 (3):647-657.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Superhighness.Bjørn Kjos-Hanssen & Andrée Nies - 2009 - Notre Dame Journal of Formal Logic 50 (4):445-452.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.

Analytics

Added to PP
2010-09-12

Downloads
8 (#1,345,183)

6 months
46 (#95,336)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Schnorr triviality and genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.

View all 8 citations / Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7-12):159-166.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7‐12):159-166.

View all 9 references / Add more references