The strength of the Besicovitch-Davies theorem

Bjørn Kjos-Hanssen; Jan Reimann

doi:10.1007/978-3-642-13962-8_26

The strength of the Besicovitch-Davies theorem

Bjørn Kjos-Hanssen, Jan Reimann

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

A theorem of Besicovitch and Davies implies for Cantor space 2 ^ω that each Σ¹₁(analytic) class of positive Hausdorff dimension contains a Π⁰₁(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 Σ¹₁ class U of positive dimension has a Π⁰₁(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 Π¹₁-complete then S(U) ≤_w {Y} for all U.

Original language	English (US)
Title of host publication	Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings
Pages	229-238
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-13962-8_26
State	Published - 2010
Event	6th Conference on Computability in Europe, CiE 2010 - Ponta Delgada, Azores, Portugal Duration: Jun 30 2010 → Jul 4 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6158 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th Conference on Computability in Europe, CiE 2010
Country/Territory	Portugal
City	Ponta Delgada, Azores
Period	6/30/10 → 7/4/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Kjos-Hanssen, B., & Reimann, J. (2010). The strength of the Besicovitch-Davies theorem. In Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings (pp. 229-238). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6158 LNCS). https://doi.org/10.1007/978-3-642-13962-8_26

@inproceedings{640f7675dc92432f945f0984cc0db5b8,

title = "The strength of the Besicovitch-Davies theorem",

abstract = "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.",

author = "Bj{\o}rn Kjos-Hanssen and Jan Reimann",

year = "2010",

doi = "10.1007/978-3-642-13962-8_26",

language = "English (US)",

isbn = "3642139612",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "229--238",

booktitle = "Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings",

note = "6th Conference on Computability in Europe, CiE 2010 ; Conference date: 30-06-2010 Through 04-07-2010",

}

Kjos-Hanssen, B & Reimann, J 2010, The strength of the Besicovitch-Davies theorem. in Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6158 LNCS, pp. 229-238, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, 6/30/10. https://doi.org/10.1007/978-3-642-13962-8_26

The strength of the Besicovitch-Davies theorem. / Kjos-Hanssen, Bjørn; Reimann, Jan.
Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings. 2010. p. 229-238 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6158 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

The strength of the Besicovitch-Davies theorem

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this