Bulletin of Symbolic Logic 11 (1):1-27 (2005)
A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
Measure Theory and Weak König's Lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
Embeddings Into the Medvedev and Muchnik Lattices of Π0 1 Classes.Stephen Binns & Stephen G. Simpson - 2004 - Archive for Mathematical Logic 43 (3):399-414.
A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
Vitali's Theorem and WWKL.Douglas K. Brown, Mariagnese Giusto & Stephen G. Simpson - 2002 - Archive for Mathematical Logic 41 (2):191-206.
Citations of this work BETA
Propagation of Partial Randomness.Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama - 2014 - Annals of Pure and Applied Logic 165 (2):742-758.
Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Effectively Closed Mass Problems and Intuitionism.Kojiro Higuchi - 2012 - Annals of Pure and Applied Logic 163 (6):693-697.
Cone Avoidance and Randomness Preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
Similar books and articles
More About Uniform Upper Bounds on Ideals of Turing Degrees.Harold T. Hodes - 1983 - Journal of Symbolic Logic 48 (2):441-457.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
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.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2010 - Notre Dame Journal of Formal Logic 52 (1):21-38.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Wtt-Degrees and T-Degrees of R.E. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
Randomness, Relativization and Turing Degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515 - 535.
Almost Everywhere Domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
Added to index2009-01-28
Total downloads198 ( #20,300 of 2,153,864 )
Recent downloads (6 months)1 ( #398,005 of 2,153,864 )
How can I increase my downloads?