论文标题
关于代数结构的可容纳分类
On bi-embeddable categoricity of algebraic structures
论文作者
论文摘要
在几类可计数结构中，众所周知，每个高氧化结构都具有可计算的表现，直到双重性能。在本文中，我们研究了两个类别的双线性阶订单和布尔代数类别的双层结构之间的嵌入的复杂性。我们表明，如果$ \ Mathcal l $是Hausdorff等级$ n $的可计算线性顺序，那么对于它的每份可容纳的副本，就可以从原子图中$ 2N-1 $跳跃。我们此外表明，这是最好的选择：让$ \ Mathcal l $是Hausdorff等级的可计算线性顺序$ n \ geq 1 $，然后是$ \ Mathbf 0^{（2n-2）} $没有计算其之间的嵌入及其之间的所有可计算的Bi-Embedbebableableabledabledabledabled。对于不是超级原子的布尔代数，我们获得了这一点，其所有可计算的双轴副本之间都没有高氧化度计算嵌入。另一方面，如果可计算的布尔代数是超原子，则具有最少可计算的序列$α$，因此$ \ mathbf 0^{（α）} $计算其所有可计算的Bi-Exbeddable副本之间的嵌入。此证明中使用的主要技术是Ash和骑士对结构定理的新变体。
In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if $\mathcal L$ is a computable linear order of Hausdorff rank $n$, then for every bi-embeddable copy of it there is an embedding computable in $2n-1$ jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let $\mathcal L$ be a computable linear order of Hausdorff rank $n\geq 1$, then $\mathbf 0^{(2n-2)}$ does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal $α$ such that $\mathbf 0^{(α)}$ computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knight's pairs of structures theorem.
