Finding bases of uncountable free abelian groups is usually difficult

Greenberg, Noam; Turetsky, Dan; Westrick, Linda

doi:10.1090/tran/7232

Finding bases of uncountable free abelian groups is usually difficult
HTML articles powered by AMS MathViewer

by Noam Greenberg, Dan Turetsky and Linda Brown Westrick PDF

Trans. Amer. Math. Soc. 370 (2018), 4483-4508 Request permission

Abstract:

We investigate effective properties of uncountable free abelian groups. We show that identifying free abelian groups and constructing bases for such groups is often computationally hard, depending on the cardinality. For example, we show, under the assumption $V=L$, that there is a first-order definable free abelian group with no first-order definable basis.

References

J. E. Baumgartner, L. A. Harrington, and E. M. Kleinberg, Adding a closed unbounded set, J. Symbolic Logic 41 (1976), no. 2, 481–482. MR 434818, DOI 10.2307/2272248
William W. Boone, The word problem, Proc. Nat. Acad. Sci. U.S.A. 44 (1958), 1061–1065. MR 101267, DOI 10.1073/pnas.44.10.1061
Jacob Carson, Jesse Johnson, Julia Knight, Karen Lange, Charles McCoy, and John Wallbaum, The arithmetical hierarchy in the setting of $\omega _1$, Computability 2 (2013), no. 2, 93–105. MR 3153995, DOI 10.3233/COM-13022
M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI 10.1007/BF01456932
Rodney Downey and Alexander G. Melnikov, Effectively categorical abelian groups, J. Algebra 373 (2013), 223–248. MR 2995024, DOI 10.1016/j.jalgebra.2012.09.020
Paul C. Eklof, On the existence of $\kappa$-free abelian groups, Proc. Amer. Math. Soc. 47 (1975), 65–72. MR 379694, DOI 10.1090/S0002-9939-1975-0379694-0
Paul C. Eklof, Methods of logic in abelian group theory, Abelian group theory (Proc. Second New Mexico State Univ. Conf., Las Cruces, N.M., 1976) Lecture Notes in Math., Vol. 616, Springer, Berlin, 1977, pp. 251–269. MR 0465854
Paul C. Eklof, Shelah’s singular compactness theorem, Publ. Mat. 52 (2008), no. 1, 3–18. MR 2384838, DOI 10.5565/PUBLMAT_{5}2108_{0}1
Paul C. Eklof and Alan H. Mekler, Almost free modules, Revised edition, North-Holland Mathematical Library, vol. 65, North-Holland Publishing Co., Amsterdam, 2002. Set-theoretic methods. MR 1914985
Ekaterina Fokina, Sy-David Friedman, Julia Knight, and Russell Miller, Classes of structures with universe a subset of $\omega _1$, J. Logic Comput. 23 (2013), no. 6, 1249–1265. MR 3144883, DOI 10.1093/logcom/ext042
Sy D. Friedman, Negative solutions to Post’s problem. II, Ann. of Math. (2) 113 (1981), no. 1, 25–43. MR 604041, DOI 10.2307/1971132
A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003
László Fuchs, Infinite abelian groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York-London, 1970. MR 0255673
Noam Greenberg, The role of true finiteness in the admissible recursively enumerable degrees, Mem. Amer. Math. Soc. 181 (2006), no. 854, vi+99. MR 2213065, DOI 10.1090/memo/0854
Noam Greenberg, Joel David Hamkins, Denis Hirschfeldt, and Russell Miller (eds.), Effective mathematics of the uncountable, Lecture Notes in Logic, vol. 41, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2013. MR 3185552, DOI 10.1017/CBO9781139028592
Noam Greenberg, Asher M. Kach, Steffen Lempp, and Daniel D. Turetsky, Computability and uncountable linear orders I: Computable categoricity, J. Symb. Log. 80 (2015), no. 1, 116–144. MR 3320586, DOI 10.1017/jsl.2014.68
Noam Greenberg, Asher M. Kach, Steffen Lempp, and Daniel D. Turetsky, Computability and uncountable linear orders II: Degree spectra, J. Symb. Log. 80 (2015), no. 1, 145–178. MR 3320587, DOI 10.1017/jsl.2014.69
Noam Greenberg and Julia F. Knight, Computable structure theory on $\omega _1$ using admissibility, Effective mathematics of the uncountable, Lect. Notes Log., vol. 41, Assoc. Symbol. Logic, La Jolla, CA, 2013, pp. 50–80. MR 3205054
Noam Greenberg, Julia F. Knight, Alexander G. Melnikov, and Daniel D. Turetsky, Computable categoricity for uncountable structures, in preparation.
Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455–475. MR 130286, DOI 10.1098/rspa.1961.0132
Paul Hill, New criteria for freeness in abelian groups, Trans. Amer. Math. Soc. 182 (1973), 201–209. MR 325805, DOI 10.1090/S0002-9947-1973-0325805-5
R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0
Peter Koepke, Ordinal computability, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 280–289. MR 2545902, DOI 10.1007/978-3-642-03073-4_{2}9
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
G. Metakides and A. Nerode, Recursively enumerable vector spaces, Ann. Math. Logic 11 (1977), no. 2, 147–171. MR 446936, DOI 10.1016/0003-4843(77)90015-8
P. S. Novikov, The unsolvability of the problem of the equivalence of words in a group and several other problems in algebra, Czechoslovak Math. J. 6(81) (1956), 450–454 (Russian, with English summary). MR 121395
L. Pontrjagin, The theory of topological commutative groups, Ann. of Math. (2) 35 (1934), no. 2, 361–388. MR 1503168, DOI 10.2307/1968438
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
Saharon Shelah, Infinite abelian groups, Whitehead problem and some constructions, Israel J. Math. 18 (1974), 243–256. MR 357114, DOI 10.1007/BF02757281
Saharon Shelah, A compactness theorem for singular cardinals, free algebras, Whitehead problem and transversals, Israel J. Math. 21 (1975), no. 4, 319–349. MR 389579, DOI 10.1007/BF02757993
Bartel L. van der Waerden, Eine Bemerkung über die Unzerlegbarkeit von Polynomen, Math. Ann. 102 (1930), no. 1, 738–739 (German). MR 1512605, DOI 10.1007/BF01782374