The effective theory of Borel equivalence relations☆ Export

@article{citeulike:6038797, abstract = {The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver  [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on inlMMLBox , the power set of ω , and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on inlMMLBox . In this article we examine the effective content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene's O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington (see  [5] and [16] ) establishing for any recursive ordinal α the existence of inlMMLBox singletons whose α -jumps are Turing incomparable.}, author = {Fokina, Ekaterina B. and Friedman, Sy-David and T\"{o}rnquist, Asger}, citeulike-article-id = {6038797}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.apal.2009.10.002}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0168007209001961}, day = {27}, doi = {10.1016/j.apal.2009.10.002}, issn = {01680072}, journal = {Annals of Pure and Applied Logic}, month = {October}, posted-at = {2009-10-30 01:01:14}, title = {The effective theory of Borel equivalence relations☆}, url = {http://dx.doi.org/10.1016/j.apal.2009.10.002}, year = {2009} }

TY - JOUR ID - citeulike:6038797 L3 - citeulike-article-id:6038797 N2 - The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver  [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on inlMMLBox , the power set of ω , and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on inlMMLBox . In this article we examine the effective content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington (see  [5] and [16] ) establishing for any recursive ordinal α the existence of inlMMLBox singletons whose α -jumps are Turing incomparable. JF - Annals of Pure and Applied Logic SN - 01680072 TI - The effective theory of Borel equivalence relations☆ AU - Fokina, Ekaterina AU - Friedman, Sy-David AU - Törnquist, Asger PY - 2009/10/27/ UR - http://dx.doi.org/10.1016/j.apal.2009.10.002 ER -