Electronic Research Announcements

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

Author(s): Olga Kharlampovich; Alexei Myasnikov
Journal: Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 101-108.
MSC (1991): Primary 20E05, 20F10; Secondary 03B25, 03C68
Posted: December 14, 1998
Retrieve article in: PDF DVI PostScript

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.

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

Retrieve articles in Electronic Research Announcements with MSC (1991): 20E05, 20F10, 03B25, 03C68

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: 10.1090/S1079-6762-98-00047-X
PII: S 1079-6762(98)00047-X
Keywords: Free group, elementary theory, Tarski
Received by editor(s): May 25, 1998
Posted: December 14, 1998
Communicated by: Efim Zelmanov
Copyright of article: Copyright 1998, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1079-6762

Previous volume \| Table of contents \| Next volume Articles in press \| Most recent volume \| All volumes Previous Article \| Next Article

Currently published by the American Institute of Mathematical Sciences as Electronic Research Announcements in Mathematical Sciences


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS