Annals of Pure and Applied Logic 161 (7):837-850 (2010)

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 , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . 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 establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2009.10.002
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,464
Through your library

References found in this work BETA

[Omnibus Review].Thomas Jech - 1992 - Journal of Symbolic Logic 57 (1):261-262.
Descriptive Set Theory.Richard Mansfield - 1981 - Journal of Symbolic Logic 46 (4):874-876.
Countable Borel Equivalence Relations.S. Jackson, A. S. Kechris & A. Louveau - 2002 - Journal of Mathematical Logic 2 (01):1-80.
Descriptive Set Theory.Yiannis Nicholas Moschovakis - 1982 - Studia Logica 41 (4):429-430.
New Directions in Descriptive Set Theory.Alexander S. Kechris - 1999 - Bulletin of Symbolic Logic 5 (2):161-174.

View all 7 references / Add more references

Citations of this work BETA

On Δ 2 0 -Categoricity of Equivalence Relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
Implicit Definability in Arithmetic.Stephen G. Simpson - 2016 - Notre Dame Journal of Formal Logic 57 (3):329-339.

View all 10 citations / Add more citations

Similar books and articles

On Borel Equivalence Relations in Generalized Baire Space.Sy-David Friedman & Tapani Hyttinen - 2012 - Archive for Mathematical Logic 51 (3-4):299-304.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Borel Equivalence Relations Which Are Highly Unfree.Greg Hjorth - 2008 - Journal of Symbolic Logic 73 (4):1271-1277.
Borel Structures and Borel Theories.Greg Hjorth & André Nies - 2011 - Journal of Symbolic Logic 76 (2):461 - 476.
Continuous Versus Borel Reductions.Simon Thomas - 2009 - Archive for Mathematical Logic 48 (8):761-770.
The Borel Complexity of Isomorphism for Theories with Many Types.David Marker - 2007 - Notre Dame Journal of Formal Logic 48 (1):93-97.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
Analytic Equivalence Relations and the Forcing Method.Jindřich Zapletal - 2013 - Bulletin of Symbolic Logic 19 (4):473-490.
Analytic Equivalence Relations and Bi-Embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.


Added to PP index

Total views
45 ( #253,650 of 2,520,436 )

Recent downloads (6 months)
1 ( #405,718 of 2,520,436 )

How can I increase my downloads?


My notes