RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2015 Volume 54, Number 5, Pages 551–574 (Mi al712)

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

P. E. Alaevab

a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia

Abstract: 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.

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

UDC: 510.5+510.6

Received: 08.02.2015

DOI: 10.17377/alglog.2015.54.501


 English version:
Algebra and Logic, 2015, 54:5, 353–369

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025