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

Authors: Noam Greenberg, Dan Turetsky and Linda Brown Westrick
Journal: Trans. Amer. Math. Soc. 370 (2018), 4483-4508
MSC (2010): Primary 03C57; Secondary 03D60
DOI: https://doi.org/10.1090/tran/7232
Published electronically: December 14, 2017
MathSciNet review: 3811535
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 https://doi.org/10.2307/2272248
William W. Boone, The word problem, Proc. Nat. Acad. Sci. U.S.A. 44 (1958), 1061–1065. MR 101267, DOI https://doi.org/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 https://doi.org/10.3233/COM-13022
M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI https://doi.org/10.1007/BF01456932
Rodney Downey and Alexander G. Melnikov, Effectively categorical abelian groups, J. Algebra 373 (2013), 223–248. MR 2995024, DOI https://doi.org/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 https://doi.org/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) Springer, Berlin, 1977, pp. 251–269. Lecture Notes in Math., Vol. 616. MR 0465854
Paul C. Eklof, Shelah’s singular compactness theorem, Publ. Mat. 52 (2008), no. 1, 3–18. MR 2384838, DOI https://doi.org/10.5565/PUBLMAT_52108_01
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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/BF01206635

G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455–475. MR 130286, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0003-4843%2872%2990001-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 https://doi.org/10.1007/978-3-642-03073-4_29

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 https://doi.org/10.1016/0003-4843%2877%2990015-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 https://doi.org/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 https://doi.org/10.1090/S0002-9947-1960-0113807-4

Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970

Saharon Shelah, Infinite abelian groups, Whitehead problem and some constructions, Israel J. Math. 18 (1974), 243–256. MR 357114, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/BF01782374