Degrees of categoricity of computable structures. (English) Zbl 1184.03026
Summary: Defining the degree of categoricity of a computable structure \({\mathcal{M}}\) to be the least degree \(\mathbf d\) for which \({\mathcal{M}}\) is \(\mathbf d\)-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that, for all \(n\), degrees d.c.e. in and above \(\mathbf 0^{(n)}\) can be so realized, as can the degree \(\mathbf 0^{(\omega)}\).
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03C35 | Categoricity and completeness of theories |
| 03D28 | Other Turing degree structures |
References:
| [1] | Cholak P., Goncharov S.S., Khoussainov B., Shore R.A.: Computably categorical structures and expansions by constants. J. Symb. Log. 64, 13–37 (1999) · Zbl 0928.03040 · doi:10.2307/2586747 |
| [2] | Fröhlich A., Shepherdson J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. A 248(950), 407–432 (1956) · Zbl 0070.03502 · doi:10.1098/rsta.1956.0003 |
| [3] | Goncharov S.S.: Problem of the number of non-self-equivalent constructivizations. Algebra Log. 19, 401–414 (1980) · Zbl 0476.03046 · doi:10.1007/BF01669323 |
| [4] | Goncharov, S.S.: Nonequivalent constructivizations. In: Proceedings of Mathematical Institute of the Siberian Branch Academy of Sciences, Nauka, Novosibirsk (1982) · Zbl 0543.03017 |
| [5] | Goncharov, S.S.: Autostable models and algorithmic dimensions. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds.) Handbook of Recursive Mathematics, vol. 1, pp. 261–287. Elsevier, Amsterdam (1998) · Zbl 0958.03030 |
| [6] | Goncharov S.S., Khoussainov B.: Complexity of categorical theories with computable models. Algebra Log. 43(6), 365–373 (2004) · Zbl 1097.03027 · doi:10.1023/B:ALLO.0000048826.92325.02 |
| [7] | Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R.: Enumerations in computable structure theory. Ann. Pure Appl. Log. 136(3), 219–246 (2005) · Zbl 1081.03033 · doi:10.1016/j.apal.2005.02.001 |
| [8] | Harizanov V.S.: Pure computable model theory. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds) Handbook of Recursive Mathematics, vol. 1, pp. 3–114. Elsevier, Amsterdam (1998) · Zbl 0952.03037 |
| [9] | Harizanov, V.S., Miller, R., Morozov, A.: Automorphism spectra of computable structures (to appear) |
| [10] | Harrison, J.: Doctoral dissertation, Stanford University (1967) |
| [11] | Hirschfeldt D.R., Khoussainov B., Shore R.A., Slinko A.M.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Log. 115, 71–113 (2002) · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2 |
| [12] | Kreisel G., Shoenfield J., Wang H.: Number theoretic concepts and recursive well-orderings. Arch. Math. Log. Grundl. 5, 42–64 (1960) · Zbl 0129.00402 · doi:10.1007/BF01977642 |
| [13] | Marker D.: Non-{\(\Sigma\)} n -axiomatizable almost strongly minimal theories. J. Symb. Log. 54, 921–927 (1989) · Zbl 0698.03021 · doi:10.2307/2274752 |
| [14] | Miller R.: d-Computable categoricity for algebraic fields. J. Symb. Log. 74(4), 1325–1351 (2009) · Zbl 1202.03044 · doi:10.2178/jsl/1254748694 |
| [15] | Moschovakis Y.N.: Descriptive Set Theory, vol. 100 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam (1980) · Zbl 0517.03025 |
| [16] | Richter L.J.: Degrees of structures. J. Symb. Log. 46, 723–731 (1981) · Zbl 0512.03024 · doi:10.2307/2273222 |
| [17] | Soare R.I.: Recursively Enumerable Sets and Degrees. Springer, New York (1987) · Zbl 0667.03030 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
