solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看4367次
Classifying equivalence relations in the Ershov hierarchy. (arXiv:1810.03559v1 [math.LO])
来源于:arXiv
Computably enumerable equivalence relations (ceers) received a lot of
attention in the literature. The standard tool to classify ceers is provided by
the computable reducibility $\leq_c$. This gives rise to a rich
degree-structure. In this paper, we lift the study of $c$-degrees to the
$\Delta^0_2$ case. In doing so, we rely on the Ershov hierarchy. For any
notation $a$ for a non-zero computable ordinal, we prove several algebraic
properties of the degree-structure induced by $\leq_c$ on the
$\Sigma^{-1}_{a}\smallsetminus \Pi^{-1}_a$ equivalence relations. A special
focus of our work is on the (non)existence of infima and suprema of
$c$-degrees. 查看全文>>