Effectively Existentially-Atomic Structures
Effectively Existentially-Atomic Structures
复制标题
有效存在的原子结构
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Montalbán
中科院分区：
文献类型：
--
作者：
A. Montalbán
本文所研究的存在-原子结构和有效存在-原子结构的概念其实并不新鲜。本文的目的是从可计算理论的角度对它们进行筛选，考察它们的性质，并证明一些关于它们的新结果。这些结构是最简单的结构，仅凭这一点，就值得对它们进行分析。正如我们将看到的，它们是最简单的，因为在不同的拷贝之间寻找同构是多么的复杂，也因为它们的描述是多么的复杂。尽管它们很简单，但它们在以下意义上是非常普遍的：如果进行足够的跳跃，每个结构都是存在的原子，跳跃的次数（本质上）是结构的斯科特秩。简单性和普遍性之间的平衡是它们的重要之处。
The notions we study in this paper, those of existentially-atomic structure and effectively existentially-atomic structure, are not really new. The objective of this paper is to single them out, survey their properties from a computability-theoretic viewpoint, and prove a few new results about them. These structures are the simplest ones around, and for that reason alone, it is worth analyzing them. As we will see, they are the simplest ones in terms of how complicated it is to find isomorphisms between different copies and in terms of the complexity of their descriptions. Despite their simplicity, they are very general in the following sense: every structure is existentially atomic if one takes enough jumps, the number of jumps being (essentially) the Scott rank of the structure. That balance between simplicity and generality is what makes them important.