线性序的可计算表示

《Journal of Logic and Computation》：Computable presentations of linear orders

　　

摘要

本文探讨可计算线性序的表现形式下的计算可约性。特别是，本文研究了由固定线性序 $\mathbf{P}(\mathcal{L})$ 由该线性序的c-度构成的度结构。其中该线性序 $\mathcal{L}$? 为以下之一：$\omega ?k$?、${\omega }^2$?、$\omega +{\omega }^{?}$?、$\zeta$ 或 $\omega ?\eta$?。本文的主要目标是识别这些偏序集之间的结构差异，重点关注最小度、极小度、普遍度、最小覆盖及其可能数量的存在性。在显著的差异中，结构 $\mathbf{P}(\zeta )$ 包含具有最小覆盖但不是强最小覆盖的度，而这种现象在 $\mathbf{P}(\omega )$? 中不会出现。