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

Kharlampovich, Olga¹ ; Myasnikov, Alexei²

¹ Department of Mathematics and Statistics, McGill University, 805 Sherbrooke St. West, Montreal, QC, Canada H3A 2K6
² Department of Mathematics, City College, Convent Ave. & 138th St., New York, NY 10031

Electronic research announcements of the American Mathematical Society, Tome 04 (1998), pp. 101-108

Résumé

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.

Détail

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

Bibliographie

[1] Appel, K. I. One-variable equations in free groups Proc. Amer. Math. Soc. 1968 912 918

[2] Baumslag, Gilbert On generalised free products Math. Z. 1962 423 438

[3] Bryant, Roger M. The verbal topology of a group J. Algebra 1977 340 346

[4] Chang, C. C., Keisler, H. J. Model theory 1973

[5] Comerford, Leo P., Jr., Edmunds, Charles C. Quadratic equations over free groups and free products J. Algebra 1981 276 297

[6] Comerford, Leo P., Jr., Edmunds, Charles C. Solutions of equations in free groups 1989 347 356

[7] Ershov, Yu. L., Palyutin, E. A. Matematicheskaya logika 1987 337

[8] Grigorchuk, R. I., Kurchanov, P. F. Some problems in group theory that are connected with geometry 1990

[9] Grigorchuk, R. I., Kurchanov, P. F. On quadratic equations in free groups 1992 159 171

[10] Guba, V. S. Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems Mat. Zametki 1986

[11] Hoare, A. Howard M., Karrass, Abraham, Solitar, Donald Subgroups of finite index of Fuchsian groups Math. Z. 1971 289 298

[12] Hoare, A. Howard M., Karrass, Abraham, Solitar, Donald Subgroups of infinite index in Fuchsian groups Math. Z. 1972 59 69

[13] Lorenc, A. A. Solution of systems of equations in one unknown in free groups Dokl. Akad. Nauk SSSR 1963 1253 1256

[14] Lyndon, R. C. The equation 𝑎²𝑏² Michigan Math. J. 1959 89 95

[15] Lyndon, Roger C. Equations in free groups Trans. Amer. Math. Soc. 1960 445 457

[16] Lyndon, Roger C. Groups with parametric exponents Trans. Amer. Math. Soc. 1960 518 533

[17] Lyndon, Roger C. Length functions in groups Math. Scand. 1963 209 234

[18] Lyndon, Roger C. Equations in groups Bol. Soc. Brasil. Mat. 1980 79 102

[19] Lyndon, Roger C., Schupp, Paul E. Combinatorial group theory 1977

[20] Makanin, G. S. Decidability of the universal and positive theories of a free group Izv. Akad. Nauk SSSR Ser. Mat. 1984 735 749

[21] Makanin, G. S. Equations in a free group Izv. Akad. Nauk SSSR Ser. Mat. 1982

[22] Mal′Cev, A. I. Some correspondences between rings and groups Mat. Sb. (N.S.) 1960 257 266

[23] Merzljakov, Ju. I. Positive formulae on free groups Algebra i Logika Sem. 1966 25 42

[24] Myasnikov, A. G., Remeslennikov, V. N. Exponential groups. II. Extensions of centralizers and tensor completion of CSA-groups Internat. J. Algebra Comput. 1996 687 711

[25] Collar, A. R. On the reciprocation of certain matrices Proc. Roy. Soc. Edinburgh 1939 195 206

[26] Razborov, A. A. Systems of equations in a free group Izv. Akad. Nauk SSSR Ser. Mat. 1984 779 832

[27] Razborov, Alexander A. On systems of equations in free groups 1995 269 283

[28] Remeslennikov, V. N. ∃-free groups Sibirsk. Mat. Zh. 1989 193 197

[29] Sacerdote, George S. Elementary properties of free groups Trans. Amer. Math. Soc. 1973 127 138

[30] Maclane, Saunders Steinitz field towers for modular fields Trans. Amer. Math. Soc. 1939 23 45

[31] Stallings, John R. Finiteness properties of matrix representations Ann. of Math. (2) 1986 337 346