Complexity of equivalence relations and preorders from computability theory

Journal of Symbolic Logic 79 (3):859-881 (2014)


We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on exponential time sets, which is${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is${\rm{\Sigma }}_4^0$.

Download options


    Upload a copy of this work     Papers currently archived: 72,766

External links

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

Through your library


Added to PP

19 (#588,071)

6 months
1 (#386,989)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Anti-Mitotic Recursively Enumerable Sets.Klaus Ambos-Spies - 1985 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (29-30):461-477.
Anti‐Mitotic Recursively Enumerable Sets.Klaus Ambos‐Spies - 1985 - Mathematical Logic Quarterly 31 (29‐30):461-477.

Add more references

Citations of this work

Add more citations

Similar books and articles

Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
A Brauerian Representation of Split Preorders.Z. Petric & K. Dosen - 2003 - Mathematical Logic Quarterly 49 (6):579.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
Maximal R.E. Equivalence Relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
On Enveloping Type-Definable Structures.Cédric Milliet - 2011 - Journal of Symbolic Logic 76 (3):1023 - 1034.
Isomorphism Testing For Equivalence Relations.Edward Szczypka - 1996 - Reports on Mathematical Logic:101-109.
? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Superrigidity and Countable Borel Equivalence Relations.Simon Thomas - 2003 - Annals of Pure and Applied Logic 120 (1-3):237-262.