|
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.
Received: 08.02.2015
Citation:
P. E. Alaev, “Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension”, Algebra Logika, 54:5 (2015), 551–574; Algebra and Logic, 54:5 (2015), 353–369
Linking options:
https://www.mathnet.ru/eng/al712 https://www.mathnet.ru/eng/al/v54/i5/p551
|
Statistics & downloads: |
Abstract page: | 191 | Full-text PDF : | 45 | References: | 70 | First page: | 35 |
|