Abstract
We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Becker, H., and A. S. Kechris, The Descriptive Set Theory of Polish Group Actions, London Mathematical Society Lecture Note Serious 232, Cambridge University Press, 1996.
Bernardi, C., and A. Sorbi, 'Classifying positive equivalence relations', J.Sym bolic Logic 48 (1983), 529-538.
Ershov, Yu. L., 'Positive equivalence relations' (English translation), Algebra and Logic 10 (1973), 378-394.
Friedman, H., and L. Stanley, 'A Borel reducibility theory for classes of countable structures', J.Sym bolic Logic 54 (1989), 894-914.
Lachlan, A.H., 'A note on positive equivalence relations', Zeitschr. f. math. Logik und Grundlagen d. Math. 33 (1987), 43-46.
Miller, C.F., III, On Group-theoretic Decision Problems and Their Classification, Annals of Mathematics Studies, No. 68, Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1971.
Nies, A., 'Computably enumerable equivalence relations modulo finite differences', Math. Log. Quart. 40 (1994), 490-518.
Rabin, M.O., 'Computable unsolvability of group theoretic problems', Ann. Math. 67 (1958), 172-194.
Rogers, H., Theory of Computable Functions and Effective Computability, MIT Press, 1987.
Visser, A., 'Numerations, lambda-calculus and arithmetic', in To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism (J.P. Seldin and J.R. Hindley, eds.), Academic Press, New York, 1980, 259-284.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gao, S., Gerdes, P. Computably Enumerable Equivalence Relations. Studia Logica 67, 27–59 (2001). https://doi.org/10.1023/A:1010521410739
Issue Date:
DOI: https://doi.org/10.1023/A:1010521410739