Inside the Muchnik degrees II: The degree structures induced by the arithmetical hierarchy of countably continuous functions

Annals of Pure and Applied Logic 165 (6):1201-1241 (2014)

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π10 subsets of Cantor space, we also show that every nonzero finite-2-piecewise degree includes infinitely many Medvedev degrees, every nonzero countable-Δ20-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-2-countable-Δ20-piecewise degree includes infinitely many countable-Δ20-piecewise degrees, and every nonzero Muchnik degree includes infinitely many finite-2-countable-Δ20-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ20-piecewise degree of a nonempty Π10 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2014.03.001
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,629
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Descriptive Set Theory.Yiannis N. Moschovakis - 1981 - Journal of Symbolic Logic 46 (4):874-876.

View all 27 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Borel-Amenable Reducibilities for Sets of Reals.Luca Motto Ros - 2009 - Journal of Symbolic Logic 74 (1):27-49.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
An Almost-Universal Cupping Degree.Jiang Liu & Guohua Wu - 2011 - Journal of Symbolic Logic 76 (4):1137-1152.
Hyperimmunity in 2sp ℕ.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2):293-316.
A Hierarchy for the Plus Cupping Turing Degrees.Yong Wang & Angsheng Li - 2003 - Journal of Symbolic Logic 68 (3):972-988.
Coding True Arithmetic in the Medvedev and Muchnik Degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
Mass Problems and Measure-Theoretic Regularity.Stephen G. Simpson - 2009 - Bulletin of Symbolic Logic 15 (4):385-409.
A Quasi-Order on Continuous Functions.Raphaël Carroy - 2013 - Journal of Symbolic Logic 78 (2):633-648.
Degrees of Isomorphism Types and Countably Categorical Groups.Aleksander Ivanov - 2012 - Archive for Mathematical Logic 51 (1-2):93-98.
The Jump Operation for Structure Degrees.V. Baleva - 2006 - Archive for Mathematical Logic 45 (3):249-265.


Added to PP index

Total views
12 ( #681,039 of 2,280,568 )

Recent downloads (6 months)
2 ( #568,325 of 2,280,568 )

How can I increase my downloads?


My notes

Sign in to use this feature