TY - GEN

T1 - The strength of the Besicovitch-Davies theorem

AU - Kjos-Hanssen, Bjørn

AU - Reimann, Jan

PY - 2010

Y1 - 2010

N2 - A theorem of Besicovitch and Davies implies for Cantor space 2 ω that each Σ11(analytic) class of positive Hausdorff dimension contains a Π01(closed) subclass of positive dimension. We consider the weak (Muchnik) reducibility ≤w in connection with the mass problem S(U) of computing a set X ⊆ ω such that the Σ11 class U of positive dimension has a Π01(X) subclass of positive dimension. We determine the difficulty of the mass problems S(U) through the following results: (1) Y is hyperarithmetic if and only if {Y} ≤w S(U) for some U; (2) there is a U such that if Y is hyperarithmetic, then {Y} ≤w S(U); (3) if Y is Π11-complete then S(U) ≤w {Y} for all U.

AB - A theorem of Besicovitch and Davies implies for Cantor space 2 ω that each Σ11(analytic) class of positive Hausdorff dimension contains a Π01(closed) subclass of positive dimension. We consider the weak (Muchnik) reducibility ≤w in connection with the mass problem S(U) of computing a set X ⊆ ω such that the Σ11 class U of positive dimension has a Π01(X) subclass of positive dimension. We determine the difficulty of the mass problems S(U) through the following results: (1) Y is hyperarithmetic if and only if {Y} ≤w S(U) for some U; (2) there is a U such that if Y is hyperarithmetic, then {Y} ≤w S(U); (3) if Y is Π11-complete then S(U) ≤w {Y} for all U.

UR - http://www.scopus.com/inward/record.url?scp=77954879244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954879244&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13962-8_26

DO - 10.1007/978-3-642-13962-8_26

M3 - Conference contribution

AN - SCOPUS:77954879244

SN - 3642139612

SN - 9783642139611

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 229

EP - 238

BT - Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings

T2 - 6th Conference on Computability in Europe, CiE 2010

Y2 - 30 June 2010 through 4 July 2010

ER -