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 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 10.1007/BF01195185
- Roger M. Bryant, The verbal topology of a group, J. Algebra 48 (1977), no.Β 2, 340β346. MR 453878, DOI 10.1016/0021-8693(77)90312-X
- C. C. Chang and H. J. Keisler, Model theory, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. 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 10.1016/0021-8693(81)90265-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 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 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 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, DOI 10.1307/mmj/1028998143
- Roger C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445β457. MR 151503, DOI 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 10.1090/S0002-9947-1960-0151502-6
- Roger C. Lyndon, Length functions in groups, Math. Scand. 12 (1963), 209β234. MR 163947, DOI 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 10.1007/BF02584882
- Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. 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 10.1142/S0218196796000398
- B. Plotkin, Varieties of algebras and algebraic varieties. Categories of algebraic varieties, Preprint, Hebrew University, Jerusalem, 1996.
- A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195β206. MR 8, DOI 10.1017/S0370164600012281
- 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 10.1007/BF00970922
- George S. Sacerdote, Elementary properties of free groups, Trans. Amer. Math. Soc. 178 (1973), 127β138. MR 320146, DOI 10.1090/S0002-9947-1973-0320146-4
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23β45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- John R. Stallings, Finiteness properties of matrix representations, Ann. of Math. (2) 124 (1986), no.Β 2, 337β346. MR 855299, DOI 10.2307/1971282
- K. I. Appel, One-variable equations in free groups, Proc. Amer. Math. Soc. 19 (1968), 912β918.
- G. Baumslag, A. Myasnikov, and V. Remeslennikov, Algebraic geometry over groups, 1996, submitted to Invent. Math., 1998.
- G. Baumslag, On generalised free products, Math. Zeitschr. 78 (1962), 423β438.
- R. Bryant, The verbal topology of a group, Journal of Algebra 48 (1977), 340β346.
- C. C. Chang and H. J. Keisler, Model theory, North-Holland, London and New York, 1973.
- L. P. Comerford jr. and C. C. Edmunds, Quadratic equations over free groups and free products, Journal of Algebra 68 (1981), 276β297.
- β, Solutions of equations in free groups, Walter de Gruyter, Berlin and New York, 1989.
- Yu. L. Ershov and E. A. Palutin, Mathematical logic, Walter de Gruyter, Berlin and New York, 1989.
- 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)
- β, On quadratic equations in free groups, Contemp. Math., vol. 131 (1), pp. 159β171, Amer. Math. Soc., Providence, RI, 1992.
- V. Guba, Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems, Mat. Zametki 40 (1986), 321β324. (Russian)
- A. Hoare, A. Karrass, and D. Solitar, Subgroups of finite index of Fuchsian groups, Math. Z. 120 (1971), 289β298.
- β, Subgroups of infinite index of Fuchsian groups, Math. Z. 125 (1972), 59β69.
- 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, The solution of systems of equations in one unknown in free groups, Dokl. Akad. Nauk SSSR 148 (1963), 262β266. (Russian)
- R. C. Lyndon, The equation $a^2b^2 = c^2$ in free groups, Michigan Math. J. 6 (1959), 155β164.
- β, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445β457.
- β, Groups with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518β533.
- β, Length functions in groups, Math. Scand. 12 (1963), 209β234.
- β, Equations in groups, Bol. Soc. Bras. Mat. 11 (1980), 79β102.
- Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer, Berlin and New York, 1977.
- 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).
- β, Equations in a free group, Izv. Akad. Nauk SSSR, Ser. Mat., 46 (1982), 1199β1273; English transl. in Math. USSR Izv. 21 (1983).
- A. I. Malβtsev, On some correspondence between rings and groups, Mat. Sbornik 50 (1960), 257β266. (Russian)
- Yu. I. Merzlyakov, Positive formulae on free groups, Algebra i Logika 5(4) (1966), 25β42. (Russian)
- 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.
- 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. Razborov, On systems of equations in a free group, Math. USSR Izvestiya 25(1) (1985), 115β162.
- β, On systems of equations in a free group, PhD Thesis, Steklov Math. Institute, Moscow, 1987.
- β, On systems of equations in free groups, Combinatorial and geometric group theory (Edinburgh, 1993), pp. 269β283, Cambridge University Press, 1995.
- V. N. Remeslennikov, $\exists$-free groups, Siberian Math. J. 30 (1989), 998β1001.
- G. S. Sacerdote, Elementary properties of free groups, Trans. of the AMS 178 (1973), 127β138.
- W. Szmielew, Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203β271.
- J. R. Stallings, Finiteness properties of matrix representations, Ann. Math. 124 (1986), 337β346.
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
MR Author ID:
191704
Email:
olga@Math.McGill.CA
Alexei Myasnikov
Affiliation:
Department of Mathematics, City College, Convent Ave. & 138th St., New York, NY 10031
MR Author ID:
670299
Email:
Alexei@rio.sci.ccny.cuny.edu
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