zbMATH — the first resource for mathematics

Effective categoricity of abelian \(p\)-groups. (English) Zbl 1177.03046
In this paper the authors investigate algorithmic properties of \(p\)-groups and their characters, providing a connection between equivalence structures and abelian \(p\)-groups. The main focus of the paper is the categoricity of abelian \(p\)-groups. It is shown that every computably categorical abelian \(p\)-group is relatively computably categorical. (A structure \({\mathcal A}\) is relatively categorical if for every structure \({\mathcal B}\) isomorphic to \({\mathcal A}\), there is an isomorphism that is computable relative to the atomic diagram of \({\mathcal B}\).) Studying \(\Delta_2^0\)-isomorphisms of abelian \(p\)-groups, the authors characterize those groups that are relatively \(\Delta_2^0\)-categorical. (A structure \({\mathcal A}\) is relatively \(\Delta_2^0\)-categorical if for every structure \({\mathcal B}\) isomorphic to \({\mathcal A}\), there is an isomorphism that is \(\Delta_2^0\)-relative to the atomic diagram of \({\mathcal B}\).) The paper contains also a list of open problems.

03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
Full Text: DOI
[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.; Knight, J.F., Computable structures and the hyperarithmetical hierarchy, (2000), Elsevier Amsterdam · Zbl 0960.03001
[3] Ash, C.J.; Knight, J.; Manasse, M.; Slaman, T., Generic copies of countable structures, Annals of pure and applied logic, 42, 195-205, (1989) · Zbl 0678.03012
[4] Barker, E.J., Back and forth relations for reduced abelian \(p\)-groups, Annals of pure and applied logic, 75, 223-249, (1995) · Zbl 0842.03029
[5] Calvert, W.; Cenzer, D.; Harizanov, V.S.; Morozov, A., Effective categoricity of equivalence structures, Annals of pure and applied logic, 141, 61-78, (2006) · Zbl 1103.03037
[6] Calvert, W.; Harizanov, V.S.; Knight, J.F.; Miller, S., Index sets of computable structures, Algebra and logic, 45, 306-325, (2006) · Zbl 1164.03325
[7] Chisholm, J., Effective model theory vs. recursive model theory, Journal symbolic logic, 55, 1168-1191, (1990) · Zbl 0722.03030
[8] J. Chisholm, E. Fokina, S.S. Goncharov, V.S. Harizanov, J.F. Knight, S. Quinn, Intrinsic bounds on complexity at limit levels, Journal of Symbolic Logic (in press) · Zbl 1201.03019
[9] Fuchs, L., Infinite abelian groups, (1970), Academic Press New York · Zbl 0213.03501
[10] Goncharov, S.S., Autostability of models and abelian groups, Algebra and logic, 19, 23-44, (1980), (in Russian). pp. 13-27 (English translation) · Zbl 0468.03022
[11] Goncharov, S.S., The quantity of nonautoequivalent constructivizations, Algebra and logic, 16, 257-282, (1977), (in Russian). pp. 169-185 (English translation) · Zbl 0407.03040
[12] Goncharov, S.S.; Dzgoev, V.D., Autostability of models, Algebra and logic, 19, 45-58, (1980), (in Russian). pp. 28-37 (English translation) · Zbl 0468.03023
[13] Goncharov, S.S.; Harizanov, V.S.; Knight, J.F.; McCoy, C.F.D.; Miller, R.G.; Solomon, R., Enumerations in computable structure theory, Annals of pure and applied logic, 136, 219-246, (2005) · Zbl 1081.03033
[14] Goncharov, S.S.; Harizanov, V.S.; Knight, J.F.; Shore, R.A., \(\Pi_1^1\) relations and paths through \(\mathcal{O}\), Journal of symbolic logic, 69, 585-611, (2004) · Zbl 1107.03051
[15] Goncharov, S.; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Advances in mathematics, 175, 102-143, (2003) · Zbl 1031.03058
[16] Khisamiev, N.G., Constructive abelian \(p\)-groups, Siberian advances in mathematics, 2, 68-113, (1992), (English translation) · Zbl 0854.03037
[17] Khisamiev, N.G., (), 1177-1231
[18] Khoussainov, B.; Nies, A.; Shore, R.A., Computable models of theories with few models, Notre dame journal of formal logic, 38, 165-178, (1997) · Zbl 0891.03013
[19] LaRoche, P., Recursively presented Boolean algebras, Notices AMS, 24, A552-A553, (1977)
[20] Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity of trees of finite height, Journal of symbolic logic, 70, 151-215, (2005) · Zbl 1104.03026
[21] McCoy, C.F.D., \(\Delta_2^0\)-categoricity in Boolean algebras and linear orderings, Annals of pure and applied logic, 119, 85-120, (2003) · Zbl 1016.03036
[22] Metakides, G.; Nerode, A., Effective content of field theory, Annals of mathematical logic, 17, 289-320, (1979) · Zbl 0469.03028
[23] Miller, R., The computable dimension of trees of infinite height, Journal of symbolic logic, 70, 111-141, (2005) · Zbl 1098.03049
[24] Nurtazin, A.T., Strong and weak constructivizations and computable families, Algebra and logic, 13, 311-323, (1974), (in Russian). pp. 177-184 (English translation)
[25] Remmel, J.B., Recursively categorical linear orderings, Proceedings of the American mathematical society, 83, 387-391, (1981) · Zbl 0493.03022
[26] Remmel, J.B., Recursive isomorphism types of recursive Boolean algebras, Journal of symbolic logic, 46, 572-594, (1981) · Zbl 0543.03031
[27] Selivanov, V.L., Enumerations of families of general recursive functions, Algebra and logic, 15, 205-226, (1976), (in Russian). pp. 128-141 (English translation)
[28] Smith, R.L., Two theorems on autostability in \(p\)-groups, (), 302-311, University of Connecticut, Storrs
[29] Soare, R.I., ()
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.