Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension

P. E. Alaev

Algebra i logika, Tome 54 (2015) no. 5, pp. 551-574

Résumé

An old classical result in computable structure theory is Ash's theorem stating that for every computable ordinal $\alpha\ge2$, under some additional conditions, a computable structure is $\Delta^0_\alpha$-categorical iff it has a computable $\Sigma_\alpha$ Scott family. We construct a counterexample revealing that the proof of this theorem has a serious error. Moreover, we show how the error can be corrected by revising the proof. In addition, we formulate a sufficient condition under which the $\Delta^0_\alpha$-dimension of a computable structure is infinite.

Détail

Keywords: computable structure, Ash's theorem, $\Delta^0_\alpha$-categorical structure, $\Sigma_\alpha$ Scott family, $\Delta^0_\alpha$-dimension of a computable structure.