Enumerations in computable structure theory.(English)Zbl 1081.03033

In the paper under review the authors show that for each computable successor ordinal $$\alpha$$ there is a computable structure that is $$\Delta_{\alpha}^0$$-categorical, but not relatively $$\Delta_{\alpha}^0$$-categorical. Further, it is shown that for each computable successor ordinal $$\alpha$$ and each natural number $$n\geq 1$$ there is a computable structure with exactly $$n$$ computable copies, up to $$\Delta_{\alpha}^0$$-isomorphism. Finally, the authors prove that for each computable successor ordinal $$\alpha$$ there is a structure with copies in just the degrees of sets $$X$$ such that $$\Delta_{\alpha}^0(X)$$ is not $$\Delta_{\alpha}^0$$. It follows, in particular, that for each natural number $$n\geq 1$$ there is a structure with copies in just the non-low$$_n$$ degrees.

MSC:

 03C57 Computable structure theory, computable model theory 03D45 Theory of numerations, effectively presented structures
Full Text:

References:

 [1] Ash, C.J., Categoricity in hyperarithmetical degrees, Annals of pure and applied logic, 34, 1-14, (1987) · Zbl 0617.03016 [2] Ash, C.J., A construction for recursive linear orderings, Journal of symbolic logic, 56, 673-683, (1991) · Zbl 0742.03013 [3] Ash, C.J.; Knight, J.F., Pairs of recursive structures, Annals of pure and applied logic, 46, 211-234, (1990) · Zbl 0712.03020 [4] Ash, C.J.; Knight, J.F., Computable structures and the hyperarithmetical hierarchy, (2000), Elsevier Amsterdam · Zbl 0960.03001 [5] Ash, C.; Knight, J.; Manasse, M.; Slaman, T., Generic copies of countable structures, Annals of pure and applied logic, 42, 195-205, (1989) · Zbl 0678.03012 [6] Ash, C.J.; Nerode, A., Intrinsically recursive relations, (), 26-41 · Zbl 0467.03041 [7] Barker, E., Intrinsically $$\Sigma_\alpha^0$$ relations, Annals of pure and applied logic, 39, 105-130, (1988) · Zbl 0651.03034 [8] Chisholm, J., Effective model theory vs. recursive model theory, Journal of symbolic logic, 55, 1168-1191, (1990) · Zbl 0722.03030 [9] Cholak, P.; Goncharov, S.; Khoussainov, B.; Shore, R.A., Computably categorical structures and expansions by constants, Journal of symbolic logic, 64, 13-37, (1999) · Zbl 0928.03040 [10] Ershov, Yu.L., The theory of numberings, (1977), Nauka Moscow, (in Russian) · Zbl 0427.03037 [11] Ershov, Yu.L.; Goncharov, S.S., Constructive models, (2000), Siberian School of Algebra and Logic, Kluwer Academic/Plenum Publishers, (English translation) · Zbl 0954.03036 [12] Goncharov, S.S., The quantity of nonautoequivalent constructivizations, Algebra and logic, 16, 257-282, (1977), (in Russian), 169-185 (English translation) · Zbl 0407.03040 [13] Goncharov, S.S., Computable single-valued numerations, Algebra and logic, 19, 507-551, (1980), (in Russian), 325-356 (English translation) · Zbl 0514.03029 [14] Harizanov, V.S., Pure computable model theory, (), 3-114 · Zbl 0952.03037 [15] C.R. Karp, Languages with expressions of infinite length, Ph.D. Dissertation, University of Southern California, 1959 · Zbl 0127.00901 [16] Keisler, H.J., Model theory for infinitary logic, (1971), North-Holland Amsterdam · Zbl 0222.02064 [17] Khoussainov, B.; Shore, R.A., Effective model theory: the number of models and their complexity, (), 193-239 · Zbl 0940.03045 [18] M.S. Manasse, Techniques and counterexamples in almost categorical recursive model theory, Ph.D. Dissertation, University of Wisconsin, Madison, 1982 [19] Marchenkov, S.S., The computable enumerations of families of general recursive functions, Algebra and logic, 11, 588-607, (1972), (in Russian), 326-336 (English translation) [20] McCoy, C.F.D., Finite computable dimension does not relativize, Archive for mathematical logic, 41, 309-320, (2002) · Zbl 1023.03040 [21] Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, (), 329-341 · Zbl 0166.26003 [22] Selivanov, V.L., Enumerations of families of general recursive functions, Algebra and logic, 15, 205-226, (1976), (in Russian), 128-141 (English translation) [23] Slaman, T.A., Relative to any nonrecursive set, Proceedings of the American mathematical society, 126, 2117-2122, (1998) · Zbl 0894.03017 [24] Soskov, I.N., Intrinsically hyperarithmetical sets, Mathematical logic quarterly, 42, 469-480, (1996) · Zbl 0859.03016 [25] Wehner, S., Enumerations, countable structures and Turing degrees, Proceedings of the American mathematical society, 126, 2131-2139, (1998) · Zbl 0906.03044
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.