论文标题
比较等效结构和预订的同构类型
Comparing the isomorphism types of equivalence structures and preorders
论文作者
论文摘要
可计算结构理论的一般主题是研究结构何时具有给定复杂性$γ$的副本。我们讨论了等效结构和预订的情况。我们表明，有一个$π^0_1 $等价结构，没有$σ^0_1 $复制，实际上，$π^0_1 $等价结构与$δ^0_2 $等价结构所实现的同构类型相吻合。我们还构建了一个$σ^0_1 $预订，没有$π^0_1 $复制。
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 $Π^0_1$ equivalence structure with no $Σ^0_1$ copy, and in fact that the isomorphism types realized by the $Π^0_1$ equivalence structures coincide with those realized by the $Δ^0_2$ equivalence structures. We also construct a $Σ^0_1$ preorder with no $Π^0_1$ copy.
