The effective theory of Borel equivalence relations

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

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 , 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 77,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2013-12-18

Downloads
47 (#255,437)

6 months
2 (#324,005)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

[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