Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762

 
 

 

Tarski's problem about the elementary theory of free groups has a positive solution


Authors: Olga Kharlampovich and Alexei Myasnikov
Journal: Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 101-108
MSC (1991): Primary 20E05, 20F10; Secondary 03B25, 03C68
DOI: https://doi.org/10.1090/S1079-6762-98-00047-X
Published electronically: December 14, 1998
MathSciNet review: 1662319
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that the elementary theories of all nonabelian free groups coincide and that the elementary theory of a free group is decidable. These results answer two old questions that were raised by A. Tarski around 1945.


References [Enhancements On Off] (What's this?)

  • 1. K. I. Appel, One-variable equations in free groups, Proc. Amer. Math. Soc. 19 (1968), 912-918. MR 38:1149
  • 2. G. Baumslag, A. Myasnikov, and V. Remeslennikov, Algebraic geometry over groups, 1996, submitted to Invent. Math., 1998.
  • 3. G. Baumslag, On generalised free products, Math. Zeitschr. 78 (1962), 423-438. MR 25:3980
  • 4. R. Bryant, The verbal topology of a group, Journal of Algebra 48 (1977), 340-346. MR 56:12131
  • 5. C. C. Chang and H. J. Keisler, Model theory, North-Holland, London and New York, 1973. MR 53:12927
  • 6. L. P. Comerford jr. and C. C. Edmunds, Quadratic equations over free groups and free products, Journal of Algebra 68 (1981), 276-297. MR 82k:20060
  • 7. -, Solutions of equations in free groups, Walter de Gruyter, Berlin and New York, 1989. MR 90a:20067
  • 8. Yu. L. Ershov and E. A. Palutin, Mathematical logic, Walter de Gruyter, Berlin and New York, 1989. MR 88i:03002
  • 9. R. I. Grigorchuk and P. F. Kurchanov, Some questions of group theory connected with geometry, Algebra, 7, Itogi Nauki i Tekhniki, VINITI AN SSSR, Moscow, 1989. (Russian) MR 92e:20002
  • 10. -, On quadratic equations in free groups, Contemp. Math., vol. 131 (1), pp. 101-108, Amer. Math. Soc., Providence, RI, 1992. MR 94m:20074
  • 11. V. Guba, Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems, Mat. Zametki 40 (1986), 321-324. (Russian) MR 88d:20060
  • 12. A. Hoare, A. Karrass, and D. Solitar, Subgroups of finite index of Fuchsian groups, Math. Z. 120 (1971), 289-298. MR 44:2837
  • 13. -, Subgroups of infinite index of Fuchsian groups, Math. Z. 125 (1972), 59-69. MR 45:2029
  • 14. O. Kharlampovich and A. Myasnikov, Irreducible affine varieties over a free group. 1: Irreducibility of quadratic equations and Nullstellensatz, J. of Algebra 200 (1998), 472-516. CMP 98:09
  • 15. -, Irreducible affine varieties over a free group. 2: Systems in triangular quasi-quadratic form and description of residually free groups, J. Algebra 200 (1998), 517-570. CMP 98:09
  • 16. A. A. Lorenc, The solution of systems of equations in one unknown in free groups, Dokl. Akad. Nauk SSSR 148 (1963), 262-266. (Russian) MR 32:1285
  • 17. R. C. Lyndon, The equation $a^2b^2 = c^2$ in free groups, Michigan Math. J. 6 (1959), 155-164. MR 21:1999
  • 18. -, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445-457. MR 27:1488
  • 19. -, Groups with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518-533. MR 27:1487
  • 20. -, Length functions in groups, Math. Scand. 12 (1963), 209-234. MR 29:1246
  • 21. -, Equations in groups, Bol. Soc. Bras. Mat. 11 (1980), 79-102. MR 82j:20070
  • 22. Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer, Berlin and New York, 1977. MR 58:28182
  • 23. G. S. Makanin, Decidability of the universal and positive theories of a free group, Izv. Akad. Nauk SSSR, Ser. Mat., 48(1) (1985), 735-749; English transl. in Math. USSR Izv. 25 (1985). MR 86c:03009
  • 24. -, Equations in a free group, Izv. Akad. Nauk SSSR, Ser. Mat., 46 (1982), 1199-1273; English transl. in Math. USSR Izv. 21 (1983). MR 84m:20040
  • 25. A. I. Mal'tsev, On some correspondence between rings and groups, Mat. Sbornik 50 (1960), 257-266. (Russian) MR 22:9448
  • 26. Yu. I. Merzlyakov, Positive formulae on free groups, Algebra i Logika 5(4) (1966), 25-42. (Russian) MR 36:5201
  • 27. A. G. Myasnikov and V. N. Remeslennikov, Exponential groups 2: Extension of centralizers and tensor completion of csa-groups, Interntional Journal of Algebra and Computation 6(6) (1996), 687-711. MR 97j:20039
  • 28. B. Plotkin, Varieties of algebras and algebraic varieties. Categories of algebraic varieties, Preprint, Hebrew University, Jerusalem, 1996.
  • 29. W. Quine, Concatenation as a basis for arithmetic, J. of Symb. Logic 11 (1946), 105-114. MR 8:307b
  • 30. A. Razborov, On systems of equations in a free group, Math. USSR Izvestiya 25(1) (1985), 115-162. MR 86c:20033
  • 31. -, On systems of equations in a free group, PhD Thesis, Steklov Math. Institute, Moscow, 1987.
  • 32. -, On systems of equations in free groups, Combinatorial and geometric group theory (Edinburgh, 1993), pp. 269-283, Cambridge University Press, 1995. MR 96c:20039
  • 33. V. N. Remeslennikov, $\exists$-free groups, Siberian Math. J. 30 (1989), 998-1001. MR 91f:03077
  • 34. G. S. Sacerdote, Elementary properties of free groups, Trans. of the AMS 178 (1973), 127-138. MR 47:8686
  • 35. W. Szmielew, Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203-271. MR 17:233e
  • 36. J. R. Stallings, Finiteness properties of matrix representations, Ann. Math. 124 (1986), 337-346. MR 88b:20105

Similar Articles

Retrieve articles in Electronic Research Announcements of the American Mathematical Society with MSC (1991): 20E05, 20F10, 03B25, 03C68

Retrieve articles in all journals with MSC (1991): 20E05, 20F10, 03B25, 03C68


Additional Information

Olga Kharlampovich
Affiliation: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke St. West, Montreal, QC, Canada H3A 2K6
Email: olga@Math.McGill.CA

Alexei Myasnikov
Affiliation: Department of Mathematics, City College, Convent Ave. & 138th St., New York, NY 10031
Email: Alexei@rio.sci.ccny.cuny.edu

DOI: https://doi.org/10.1090/S1079-6762-98-00047-X
Keywords: Free group, elementary theory, Tarski
Received by editor(s): May 25, 1998
Published electronically: December 14, 1998
Communicated by: Efim Zelmanov
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society