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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Log. Found. Math., 144, Elsevier, Amsterdam (2000).
C. J. Ash, J. F. Knight, M. Manasse, and T. Slaman, “Generic copies of countable structures,” Ann. Pure Appl. Log., 42, No. 3, 195-205 (1989).
J. Chisholm, “Effective model theory vs. recursive model theory,” J. Sym. Log., 55, No. 3, 1168-1191 (1990).
S. S. Goncharov, “Autostability and computable families of constructivizations,” Algebra and Logic, 14, No. 6, 392-409 (1975).
S. S. Goncharov, “The quantity of nonautoequivalent constructivizations,” Algebra and Logic, 16, No. 3, 169-185 (1977).
O. Kudinov, “An autostable 1-decidable model without a computable Scott family of ∃-formulas,” Algebra and Logic 35, No. 4, 255-260 (1996).
C. J. Ash, Categoricity in hyperarithmetical degrees, Ann. Pure Appl. Log., 34, No. 1, 1-14 (1987).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
S. Goncharov, V. Harizanov, J. Knight, C. McCoy, R. Miller, and R. Solomon, “Enumerations in computable structure theory,” Ann. Pure Appl. Log., 136, No. 3, 219-246 (2005).
J. Chisholm, E. B. Fokina, S. S. Goncharov, V. S. Harizanov, J. F. Knight, and S. Quinn, “Intrinsic bounds on complexity and definability at limit levels,” J. Symb. Log., 74, No. 3, 1047-1060 (2009).
S. S. Goncharov and V. D. Dzgoev, “Autostability of models,” Algebra and Logic, 19, No. 1, 28-37 (1980).
P. E. Alaev, “Autostable I-algebras,” Algebra and Logic, 43, No. 5, 285-306 (2004).
S. S. Goncharov, “Autostability of models and Abelian groups,” Algebra and Logic, 19, No. 1, 13-27 (1980).
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the Grants Council (under RF President) for State Aid of Leading Scientific Schools (grant NSh-860.2014.1) and by RFBR (project No. 14-01-00376).
Translated from Algebra i Logika, Vol. 54, No. 5, pp. 551-574, September-October, 2015.
Rights and permissions
About this article
Cite this article
Alaev, P.E. Ash’s Theorem on Δ 0 α -Categorical Structures and a Condition for Infinite Δ 0 α -Dimension. Algebra Logic 54, 353–369 (2015). https://doi.org/10.1007/s10469-015-9357-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-015-9357-2