|
Ash’s theorem on Δ0α-categorical structures and a condition for infinite Δ0α-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 α⩾2, under some additional conditions, a computable structure is Δ0α-categorical iff it has a computable Σα 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 Δ0α-dimension of a computable structure is infinite.
Keywords:
computable structure, Ash's theorem, Δ0α-categorical structure, Σα Scott family, Δ0α-dimension of a computable structure.
Received: 08.02.2015
Citation:
P. E. Alaev, “Ash’s theorem on Δ0α-categorical structures and a condition for infinite Δ0α-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: | 214 | Full-text PDF : | 54 | References: | 79 | First page: | 35 |
|