论文标题
分类程度和可观的学位
Degrees of categoricity and treeable degrees
论文作者
论文摘要
我们给出了更大或等于$ \ Mathbf 0''$的可计算结构的强分类程度的表征。它们恰恰是\ emph {tredable}度 - 通过可计算树的最小程度路径 - 计算$ \ mathbf 0''$。作为推论，我们获得了几个分类程度的新示例。其中我们表明，每个度$ \ mathbf d $都带有$ \ mathbf 0^{{（α）} \ leq \ mathbf d \ leq \ leq \ mathbf 0^{（（α+1）} $ for $α$可计算的序数大于$ 2 $是刚性结构的强大分类。使用完全不同的技术，我们表明，每个度$ \ MATHBF D $都带有$ \ Mathbf 0'\ Leq \ Mathbf D \ Leq \ Mathbf 0''$是结构的分类程度。与上述示例一起，这回答了CSIMA和NG的问题。为了完成图片，我们表明有一个$ \ mathbf d $带有$ \ mathbf 0'<\ mathbf d <\ mathbf 0''$，这不是刚性结构的分类程度。
We give a characterization of the strong degrees of categoricity of computable structures greater or equal to $\mathbf 0''$. They are precisely the \emph{treeable} degrees -- the least degrees of paths through computable trees -- that compute $\mathbf 0''$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $\mathbf d$ with $\mathbf 0^{(α)}\leq \mathbf d\leq \mathbf 0^{(α+1)}$ for $α$ a computable ordinal greater than $2$ is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree $\mathbf d$ with $\mathbf 0'\leq \mathbf d\leq \mathbf 0''$ is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree $\mathbf d$ with $\mathbf 0'< \mathbf d< \mathbf 0''$ that is not the degree of categoricity of a rigid structure.
