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

Kharlampovich, Olga; Myasnikov, Alexei

doi:10.1090/S1079-6762-98-00047-X

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 Free Access

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.

K. I. Appel, One-variable equations in free groups, Proc. Amer. Math. Soc. 19 (1968), 912–918. MR 232826, DOI https://doi.org/10.1090/S0002-9939-1968-0232826-3

G. Baumslag, A. Myasnikov, and V. Remeslennikov, Algebraic geometry over groups, 1996, submitted to Invent. Math., 1998.

Gilbert Baumslag, On generalised free products, Math. Z. 78 (1962), 423–438. MR 140562, DOI https://doi.org/10.1007/BF01195185

Roger M. Bryant, The verbal topology of a group, J. Algebra 48 (1977), no. 2, 340–346. MR 453878, DOI https://doi.org/10.1016/0021-8693%2877%2990312-X

C. C. Chang and H. J. Keisler, Model theory, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Studies in Logic and the Foundations of Mathematics, Vol. 73. MR 0409165

Leo P. Comerford Jr. and Charles C. Edmunds, Quadratic equations over free groups and free products, J. Algebra 68 (1981), no. 2, 276–297. MR 608536, DOI https://doi.org/10.1016/0021-8693%2881%2990265-9

Leo P. Comerford Jr. and Charles C. Edmunds, Solutions of equations in free groups, Group theory (Singapore, 1987) de Gruyter, Berlin, 1989, pp. 347–356. MR 981853

Yu. L. Ershov and E. A. Palyutin, Matematicheskaya logika, 2nd ed., “Nauka”, Moscow, 1987 (Russian). MR 921654

R. I. Grigorchuk and P. F. Kurchanov, Some problems in group theory that are connected with geometry, Algebra, 7 (Russian), Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1990, pp. 191–256, 257–261, 263 (Russian). MR 1099153

R. I. Grigorchuk and P. F. Kurchanov, On quadratic equations in free groups, Proceedings of the International Conference on Algebra, Part 1 (Novosibirsk, 1989) Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI, 1992, pp. 159–171. MR 1175769, DOI https://doi.org/10.1007/bf01058681

V. S. Guba, Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems, Mat. Zametki 40 (1986), no. 3, 321–324, 428 (Russian). MR 869922

A. Howard M. Hoare, Abraham Karrass, and Donald Solitar, Subgroups of finite index of Fuchsian groups, Math. Z. 120 (1971), 289–298. MR 285619, DOI https://doi.org/10.1007/BF01109993

A. Howard M. Hoare, Abraham Karrass, and Donald Solitar, Subgroups of infinite index in Fuchsian groups, Math. Z. 125 (1972), 59–69. MR 292948, DOI https://doi.org/10.1007/BF01111114

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.

---, 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.

A. A. Lorenc, Solution of systems of equations in one unknown in free groups, Dokl. Akad. Nauk SSSR 148 (1963), 1253–1256 (Russian). MR 0183809

R. C. Lyndon, The equation $a^{2}b^{2}=c^{2}$ in free groups, Michigan Math. J. 6 (1959), 89–95. MR 103218

Roger C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445–457. MR 151503, DOI https://doi.org/10.1090/S0002-9947-1960-0151503-8

Roger C. Lyndon, Groups with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518–533. MR 151502, DOI https://doi.org/10.1090/S0002-9947-1960-0151502-6

Roger C. Lyndon, Length functions in groups, Math. Scand. 12 (1963), 209–234. MR 163947, DOI https://doi.org/10.7146/math.scand.a-10684

Roger C. Lyndon, Equations in groups, Bol. Soc. Brasil. Mat. 11 (1980), no. 1, 79–102. MR 607019, DOI https://doi.org/10.1007/BF02584882

Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. MR 0577064

G. S. Makanin, Decidability of the universal and positive theories of a free group, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 4, 735–749 (Russian). MR 755956

G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273, 1344 (Russian). MR 682490

A. I. Mal′cev, Some correspondences between rings and groups, Mat. Sb. (N.S.) 50 (92) (1960), 257–266 (Russian). MR 0118677

Ju. I. Merzljakov, Positive formulae on free groups, Algebra i Logika Sem. 5 (1966), no. 4, 25–42 (Russian). MR 0222149

A. G. Myasnikov and V. N. Remeslennikov, Exponential groups. II. Extensions of centralizers and tensor completion of CSA-groups, Internat. J. Algebra Comput. 6 (1996), no. 6, 687–711. MR 1421886, DOI https://doi.org/10.1142/S0218196796000398

B. Plotkin, Varieties of algebras and algebraic varieties. Categories of algebraic varieties, Preprint, Hebrew University, Jerusalem, 1996.

W. Quine, Concatenation as a basis for arithmetic, J. of Symb. Logic 11 (1946), 105–114.

A. A. Razborov, Systems of equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 4, 779–832 (Russian). MR 755958

---, On systems of equations in a free group, PhD Thesis, Steklov Math. Institute, Moscow, 1987.

Alexander A. Razborov, On systems of equations in free groups, Combinatorial and geometric group theory (Edinburgh, 1993) London Math. Soc. Lecture Note Ser., vol. 204, Cambridge Univ. Press, Cambridge, 1995, pp. 269–283. MR 1320290

V. N. Remeslennikov, $\exists $-free groups, Sibirsk. Mat. Zh. 30 (1989), no. 6, 193–197 (Russian); English transl., Siberian Math. J. 30 (1989), no. 6, 998–1001 (1990). MR 1043446, DOI https://doi.org/10.1007/BF00970922

George S. Sacerdote, Elementary properties of free groups, Trans. Amer. Math. Soc. 178 (1973), 127–138. MR 320146, DOI https://doi.org/10.1090/S0002-9947-1973-0320146-4

W. Szmielew, Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203–271.

John R. Stallings, Finiteness properties of matrix representations, Ann. of Math. (2) 124 (1986), no. 2, 337–346. MR 855299, DOI https://doi.org/10.2307/1971282