The effective theory of Borel equivalence relations

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

The effective theory of Borel equivalence relations. / Fokina, E.B.; Friedman, S.-D.; Törnquist, Asger Dag.

I: Annals of Pure and Applied Logic, Bind 161, Nr. 7, 01.04.2010, s. 837-850.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Fokina, EB, Friedman, S-D & Törnquist, AD 2010, 'The effective theory of Borel equivalence relations', Annals of Pure and Applied Logic, bind 161, nr. 7, s. 837-850. https://doi.org/10.1016/j.apal.2009.10.002

APA

Fokina, E. B., Friedman, S-D., & Törnquist, A. D. (2010). The effective theory of Borel equivalence relations. Annals of Pure and Applied Logic, 161(7), 837-850. https://doi.org/10.1016/j.apal.2009.10.002

Vancouver

Fokina EB, Friedman S-D, Törnquist AD. The effective theory of Borel equivalence relations. Annals of Pure and Applied Logic. 2010 apr. 1;161(7):837-850. https://doi.org/10.1016/j.apal.2009.10.002

Author

Fokina, E.B. ; Friedman, S.-D. ; Törnquist, Asger Dag. / The effective theory of Borel equivalence relations. I: Annals of Pure and Applied Logic. 2010 ; Bind 161, Nr. 7. s. 837-850.

Bibtex

@article{0f3c2410b63d4f98b8e967fdb5cc141e,
title = "The effective theory of Borel equivalence relations",
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 P (ω), the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on P (ω). 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,16]) establishing for any recursive ordinal α the existence of Π singletons whose α-jumps are Turing incomparable.",
author = "E.B. Fokina and S.-D. Friedman and T{\"o}rnquist, {Asger Dag}",
year = "2010",
month = apr,
day = "1",
doi = "10.1016/j.apal.2009.10.002",
language = "English",
volume = "161",
pages = "837--850",
journal = "Annals of Pure and Applied Logic",
issn = "0168-0072",
publisher = "Elsevier",
number = "7",

}

RIS

TY - JOUR

T1 - The effective theory of Borel equivalence relations

AU - Fokina, E.B.

AU - Friedman, S.-D.

AU - Törnquist, Asger Dag

PY - 2010/4/1

Y1 - 2010/4/1

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 P (ω), the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on P (ω). 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,16]) establishing for any recursive ordinal α the existence of Π singletons whose α-jumps are Turing incomparable.

AB - 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 P (ω), the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on P (ω). 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,16]) establishing for any recursive ordinal α the existence of Π singletons whose α-jumps are Turing incomparable.

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

U2 - 10.1016/j.apal.2009.10.002

DO - 10.1016/j.apal.2009.10.002

M3 - Journal article

AN - SCOPUS:77649273539

VL - 161

SP - 837

EP - 850

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

SN - 0168-0072

IS - 7

ER -

ID: 61336526