Comparing the isomorphism types of equivalence structures and preorders

Abstract

A general theme of computable structure theory is to investigate when structures have copies of a given complexity $\Gamma$. We discuss such problem for the case of equivalence structures and preorders. We show that there is a ${\Pi }_1^0$ equivalence structure with no ${\Sigma }_1^0$ copy, and in fact that the isomorphism types realized by the ${\Pi }_1^0$ equivalence structures coincide with those realized by the ${\Delta }_2^0$ equivalence structures. We also construct a ${\Sigma }_1^0$ preorder with no ${\Pi }_1^0$ copy.

13 pages

References in corpus (1)

• Computably Enumerable Equivalence Relations