Fragments of the theory of the enumeration degrees
Fragments of the theory of the enumeration degrees
复制标题
DOI：
10.1016/j.aim.2021.107686
复制
发表时间：
2021-06
影响因子：
1.7
通讯作者：
S. Lempp;T. Slaman;M. Soskova
中科院分区：
文献类型：
--
作者：
S. Lempp;T. Slaman;M. Soskova
证明了有限分配格可以作为区间强嵌入计数度中，即存在一个与该格同构的计数度区间[a0，a1]，且任意计数度B≤ a1都在这个区间内或a0之下.作为推论，我们得出D e的嵌入问题是不可判定的，而嵌入问题的推广（嵌入问题的一个子问题）是可判定的.
We prove that every finite distributive lattice can be strongly embedded into the enumeration degrees as an interval, ie, that there is an interval [a 0, a 1] of enumeration degrees isomorphic to the lattice, and any enumeration degree b≤ a 1 lies in this interval or below a 0. As corollaries, we conclude that the∃∀∃-theory of D e is undecidable, while the extension of embeddings problem (a subproblem of the∀∃-theory) is decidable.