The complexity of index sets of classes of computably enumerable equivalence relations

Journal of Symbolic Logic 81 (4):1375-1395 (2016)
  Copy   BIBTEX

Abstract

Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the index set of the effectively inseparable ceers is${\rm{\Pi }}_4^0$complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a${\rm{\Sigma }}_3^0$complete preordering relation, a fact that is used to show that the preordering relation$ \le _c $on ceers is a${\rm{\Sigma }}_3^0$complete preordering relation.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

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

Classes bounded by incomplete sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
Index sets in the arithmetical Hierarchy.Ulrike Brandt - 1988 - Annals of Pure and Applied Logic 37 (2):101-110.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.

Analytics

Added to PP
2017-04-24

Downloads
2 (#1,634,744)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Relatively precomplete numerations and arithmetic.Franco Montagna - 1982 - Journal of Philosophical Logic 11 (4):419 - 430.
A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Mathematical Logic Quarterly 33 (1):43-46.
A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):43-46.

Add more references