Abstract

This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is m-complete $\Sigma _{2}^{0}$ relative to O