Comparing the isomorphism types of equivalence structures and preorders

2020/01/22 by Nikolay Bazhenov, Bazhenov, Nikolay, Luca San Mauro +1
Computer Science · #Computability, Logic, AI Algorithms #semigroups and automata theory #Advanced Algebra and Logic

paper · pdf · doi:10.48550/arxiv.2001.08017

Abstract

A general theme of computable structure theory is to investigate when structures have copies of a given complexity Γ. We discuss such problem for the case of equivalence structures and preorders. We show that there is a Π⁰₁ equivalence structure with no Σ⁰₁ copy, and in fact that the isomorphism types realized by the Π⁰₁ equivalence structures coincide with those realized by the Δ⁰₂ equivalence structures. We also construct a Σ⁰₁ preorder with no Π⁰₁ copy.

Related

• Generically Computable Equivalence Structures and Isomorphisms
• Isomorphism Spectra and Computably Composite Structures
• The Isomorphism Problem On Classes of Automatic Structures
• An Improved Homomorphism Preservation Theorem From Lower Bounds in\n Circuit Complexity
• Minimal Equivalence Relations in Hyperarithmetical and Analytical\n Hierarchies