You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility

Article type: Research Article

Authors: Coskey, Samuel | Hamkins, Joel David | Miller, Russell;

Affiliations: York University & The Fields Institute, 222 College Street, Toronto, ON M5S 2N2, Canada | Department of Philosophy, New York University, 5 Washington Place, New York, NY 10003 & The Graduate Center of the City University of New York, Mathematics Program, 365 Fifth Avenue, New York, NY 10016, & College of Staten Island of CUNY, 2800 Victory Blvd., Staten Island, NY 10314, USA | The Graduate Center of The City University of New York, Mathematics Program, 365 Fifth Avenue, New York, NY 10016 & Queens College of CUNY, 65-30 Kissena Blvd., Flushing, NY 11367, USA

Note: [] E-mail: scoskey@nylogic.org boolesrings.org/scoskey

Note: [] E-mail: jhamkins@gc.cuny.edu jdh.hamkins.org

Note: [] E-mail: Russell.Miller@qc.cuny.edu qcpages.qc.cuny.edu/~rmiller

Note: [] The research of the first author is partially supported by the Natural Sciences and Engineering Research Council of Canada. The research of the second author has been partially supported by grants from the National Science Foundation, the Simons Foundation and the CUNY Research Foundation. The research of the third author has been partially supported by the Isaac Newton Institute and by grants from the National Science Foundation and the CUNY Research Foundation.

Keywords: equivalence relations, computable reducability

DOI: 10.3233/COM-2012-004

Journal: Computability, vol. 1, no. 1, pp. 15-38, 2012

Published: 2012
Get PDF

Abstract

The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility. We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel reducibility hierarchy from descriptive set theory. Meanwhile, the notion of computable reducibility appears well suited for an analysis of equivalence relations on the c.e. sets, and more specifically, on various classes of c.e. structures. This is a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. Here, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remains.

Show less