Computably enumerable equivalence relations

DOI10.1023/A:1010521410739MaRDI QIDQ5939996zbMATH OpenOpenAlexFDO

Authors Su Gao, Peter M. Gerdes

Publication date 23 July 2001

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.0944

zbMATH Keywords

computably enumerable equivalence relationsreducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

Cited in

(46)

• On dark computably enumerable equivalence relations
• Jumps of computably enumerable equivalence relations
• Elementary theories and hereditary undecidability for semilattices of numberings
• Positive preorders
• Subrecursive equivalence relations and (non-)closure under lattice operations
• Completeness of the hyperarithmetic isomorphism equivalence relation
• Special classes of positive preorders
• Index sets for classes of positive preorders
• The theory of ceers computes true arithmetic
• Classifying equivalence relations in the Ershov hierarchy
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• The structure of computably enumerable preorder relations
• On computably enumerable structures
• On the degree structure of equivalence relations under computable reducibility
• Weakly precomplete equivalence relations in the Ershov hierarchy
• Graphs realised by r.e. equivalence relations
• Boolean algebras realized by c.e. equivalence relations
• On universal positive graphs
• Weakly precomplete computably enumerable equivalence relations
• Universal computably enumerable equivalence relations
• A survey on universal computably enumerable equivalence relations
• Finitary reducibility on equivalence relations
• The complexity of index sets of classes of computably enumerable equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• Linear orders realized by c.e. equivalence relations
• Equivalence Relations on Classes of Computable Structures
• Primitive recursive equivalence relations and their primitive recursive complexity
• Initial segments of the degrees of ceers
• On isomorphism classes of computably enumerable equivalence relations
• Computable embeddability for algebraic structures
• Agreement reducibility
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Word problems and ceers
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Classifying word problems of finitely generated algebras via computable reducibility
• Computable reducibility for computable linear orders of type
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• A note on joins and meets for positive linear preorders
• Computably discrete represented spaces
• Computably enumerable equivalence relations via primitive recursive reductions
• Analogues of the countable Borel equivalence relations in the setting of computable reducibility
• Defining algorithmically presented structures in first order logic
• Two results on complexities of decision problems of groups
• On the theory of computably enumerable linear preorders with concatenation
• Computable structure theory of partial combinatory algebras
• Reducibilities among equivalence relations induced by recursively enumerable structures

This page was built for publication: Computably enumerable equivalence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5939996)