Intrinsic bounds on complexity and definability at limit levels. (English) Zbl 1201.03019

A structure is called computably categorical if every computable structure isomorphic to it is computably isomorphic to it. The structure is called relatively computably categorical iff this statement is true for all oracles. For example, a dense linear ordering without endpoints is relatively computably categorical. Long ago, Goncharov showed that a structure \({\mathcal A}\) is relatively computably categorical iff it has a c.e. Scott family. Further, there are structures that are computably categorical without such families and hence the notions differ. This material was extended to \(\Delta_\alpha^0\)-categoricity and \(\Sigma_\alpha^0\)-Scott families by Ash and Knight, where \(\alpha\) is a (notation for a) computable ordinal. S. Goncharov, V. Harizanov, J. Knight, C. McCoy, R. Miller and R. Solomon [Ann. Pure Appl. Logic 136, No. 3, 219–246 (2005; Zbl 1081.03033)] showed that for limit ordinals there exist \(\Delta_\alpha^0\)-categorical structures which are not relatively \(\Delta_\alpha^0\)-categorical, and the present paper completes the picture by showing this for \(\alpha\) a limit ordinal. The method uses codings of families, and an “\(\alpha\)-system argument”.


03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories


Zbl 1081.03033


Full Text: DOI


[1] DOI: 10.1016/0168-0072(89)90015-8 · Zbl 0678.03012
[2] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
[3] DOI: 10.1090/S0002-9947-1990-0955487-0
[4] A construction for recursive linear orderings 56 pp 673– (1991) · Zbl 0742.03013
[5] A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings 49 pp 563– (1984) · Zbl 0585.03015
[6] DOI: 10.1002/malq.19960420139 · Zbl 0859.03016
[7] Algebra and Logic 16 pp 129– (1977)
[8] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[9] relations and paths through 69 pp 585– (2004)
[10] Techniques and counterexamples in almost categorical recursive model theory (1982)
[11] DOI: 10.1016/j.apal.2005.02.001 · Zbl 1081.03033
[12] Algebra and Logic 16 pp 257– (1977)
[13] Effective model theory vs. recursive model theory 55 pp 1168– (1990)
[14] Algebra and Logic 15 pp 205– (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.