Comparing the isomorphism types of equivalence structures and preorders


الملخص بالإنكليزية

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^0_1$ equivalence structure with no $Sigma^0_1$ copy, and in fact that the isomorphism types realized by the $Pi^0_1$ equivalence structures coincide with those realized by the $Delta^0_2$ equivalence structures. We also construct a $Sigma^0_1$ preorder with no $Pi^0_1$ copy.

تحميل البحث