On \(\Delta_2^0\)-categoricity of equivalence relations

DOI10.1016/j.apal.2015.04.003zbMath1386.03050OpenAlexW262335649MaRDI QIDQ2346952

Alexander G. Melnikov, Keng Meng Ng, Rodney G. Downey

Publication date: 26 May 2015

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.2015.04.003

zbMATH Keywords

isomorphismscategoricityequivalence structurescomputable mathematics

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (7)

Abelian \(p\)-groups and the halting problem ⋮ Computable torsion abelian groups ⋮ A Friedberg enumeration of equivalence structures ⋮ Generalization of Shapiro's theorem to higher arities and noninjective notations ⋮ Punctual categoricity relative to a computable oracle ⋮ Classifications of definable subsets ⋮ Degrees of bi-embeddable categoricity of equivalence structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Abelian \(p\)-groups and the halting problem
• The effective theory of Borel equivalence relations
• Computability of homogeneous models
• Computable models of theories with few models
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• Constructive models of complete solvable theories
• \(\Delta_{2}^{0}\)-categoricity in Boolean algebras and linear orderings
• Back and forth relations for reduced abelian \(p\)-groups
• Degrees of categoricity and the hyperarithmetic hierarchy
• Effectively categorical abelian groups
• Effective categoricity of equivalence structures
• Describing free groups
• Describing free groups, Part II: Π⁰₄ hardness and no Σ₂⁰ basis
• Limitwise monotonic sequences and degree spectra of structures
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• A Note on Positive Equivalence Relations
• Classes of Ulm type and coding rank-homogeneous trees in other structures
• Computable completely decomposable groups
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• Recursively Categorical Linear Orderings
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• LIMITWISE MONOTONIC FUNCTIONS AND THEIR APPLICATIONS

This page was built for publication: On \(\Delta_2^0\)-categoricity of equivalence relations