UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS

DOI10.1017/jsl.2013.8zbMath1338.03076OpenAlexW2058701006MaRDI QIDQ2921020

Keng Meng Ng, Andrea Sorbi, Uri Andrews, Joseph S. Miller, Steffen Lempp, Luca San Mauro

Publication date: 30 September 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/jsl.2013.8

zbMATH Keywords

computably enumerable equivalence relationseffectively inseparable sets

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Completeness of the hyperarithmetic isomorphism equivalence relation ⋮ On dark computably enumerable equivalence relations ⋮ Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Fixpoints and relative precompleteness ⋮ Index sets for classes of positive preorders ⋮ Boolean algebras realized by c.e. equivalence relations ⋮ INITIAL SEGMENTS OF THE DEGREES OF CEERS ⋮ The theory of ceers computes true arithmetic ⋮ Agreement reducibility ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Word problems and ceers ⋮ ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR ⋮ A Friedberg enumeration of equivalence structures ⋮ Jumps of computably enumerable equivalence relations ⋮ On universal positive graphs ⋮ Computable reducibility for computable linear orders of type \(\omega \) ⋮ Classifying equivalence relations in the Ershov hierarchy ⋮ A Survey on Universal Computably Enumerable Equivalence Relations ⋮ The structure of computably enumerable preorder relations ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ Positive preorders ⋮ Weakly precomplete computably enumerable equivalence relations ⋮ On the degree structure of equivalence relations under computable reducibility ⋮ On \(\Delta_2^0\)-categoricity of equivalence relations ⋮ Graphs realised by r.e. equivalence relations ⋮ EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS ⋮ Computable embeddability for algebraic structures ⋮ Effective inseparability and its applications

Cites Work

• Unnamed Item
• The effective theory of Borel equivalence relations
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Relatively precomplete numerations and arithmetic
• Undecidable fragments of elementary theories
• Initial segments of one-one degrees
• Equivalence relations induced by extensional formulae: classification by means of a new fixed point property
• Periodicity in generations of automata
• Remarks on Uniformly Finitely Precomplete Positive Equivalences