Jumps of computably enumerable equivalence relations

DOI10.1016/j.apal.2017.12.001zbMath1406.03055OpenAlexW2772134068MaRDI QIDQ1693042

Andrea Sorbi, Uri Andrews

Publication date: 11 January 2018

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2017.12.001

zbMATH Keywords

computably enumerable equivalence relationcomputable reducibility on equivalence relationshalting jump

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Recursive ordinals and ordinal notations (03F15) Theory of numerations, effectively presented structures (03D45)

Related Items

Fixpoints and relative precompleteness ⋮ Uniformly computably separable algebras with effectively splittable families of negative congruences ⋮ The theory of ceers computes true arithmetic ⋮ ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR ⋮ Minimal equivalence relations in hyperarithmetical and analytical hierarchies ⋮ The structure of computably enumerable preorder relations ⋮ Weakly precomplete equivalence relations in the Ershov hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Relatively precomplete numerations and arithmetic
• Classical recursion theory. Vol. II
• Positive equivalences
• Equivalence Relations That Are $\Sigma^0_3$ Complete for Computable Reducibility
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• A Note on Positive Equivalence Relations
• Classifying positive equivalence relations
• Equivalence relations induced by extensional formulae: classification by means of a new fixed point property
• Periodicity in generations of automata
• Theorie der Numerierungen I
• Remarks on Uniformly Finitely Precomplete Positive Equivalences
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• Isomorphism relations on computable structures
• Computably enumerable equivalence relations