The Tarski Problems and Their Solutions
Affiliation(s)
1 Department of Mathematics Fairfield University, Fairfield, USA. 2 Department of Mathematics, United States Naval Academy, Annapolis, USA. 3 Department of Mathematics, University of Hamburg, Hamburg, Germany. 4 Department of Mathematics, Temple University, Philadelphis, USA.
1 Department of Mathematics Fairfield University, Fairfield, USA. 2 Department of Mathematics, United States Naval Academy, Annapolis, USA. 3 Department of Mathematics, University of Hamburg, Hamburg, Germany. 4 Department of Mathematics, Temple University, Philadelphis, USA.
ABSTRACT
Around 1945, Alfred Tarski proposed several questions concerning the elementary theory of non-abelian free groups. These remained open for 60 years until they were proved by O. Kharlampovich and A. Myasnikov and independently by Z. Sela. The proofs, by both sets of authors, were monumental and involved the development of several new areas of infinite group theory. In this paper we explain precisely the Tarski problems and what has been actually proved. We then discuss the history of the solution as well as the components of the proof. We then provide the basic strategy for the proof. We finish this paper with a brief discussion of elementary free groups.
Around 1945, Alfred Tarski proposed several questions concerning the elementary theory of non-abelian free groups. These remained open for 60 years until they were proved by O. Kharlampovich and A. Myasnikov and independently by Z. Sela. The proofs, by both sets of authors, were monumental and involved the development of several new areas of infinite group theory. In this paper we explain precisely the Tarski problems and what has been actually proved. We then discuss the history of the solution as well as the components of the proof. We then provide the basic strategy for the proof. We finish this paper with a brief discussion of elementary free groups.
KEYWORDS
Non-Abelian Free Group, Elementary Theory, Tarski Problems, Elementary Free Groups, Algebraic Geometry over Groups
Non-Abelian Free Group, Elementary Theory, Tarski Problems, Elementary Free Groups, Algebraic Geometry over Groups
Cite this paper
Fine, B. , Gaglione, A. , Rosenberger, G. and Spellman, D. (2015) The Tarski Problems and Their Solutions. Advances in Pure Mathematics, 5, 212-231. doi: 10.4236/apm.2015.54023.
Fine, B. , Gaglione, A. , Rosenberger, G. and Spellman, D. (2015) The Tarski Problems and Their Solutions. Advances in Pure Mathematics, 5, 212-231. doi: 10.4236/apm.2015.54023.
References
[1] Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: I. Irreducibility of Quadratic Equations and Nullstellensatz. Journal of Algebra, 200, 472-516.
http://dx.doi.org/10.1006/jabr.1997.7183 [2] Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: II. Systems in Triangular Quasi-Quadratic Form and Description of Residually Free Groups. Journal of Algebra, 200, 517-570. [3] Kharlamapovich, O. and Myasnikov, A. (2005) Implicit Function Theorem over Free Groups. Journal of Algebra, 290, 1-203.
http://dx.doi.org/10.1016/j.jalgebra.2005.04.001 [4] Kharlamapovich, O. and Myasnikov, A. (2005) Effective JSJ Decompositions. Contemporary Mathematics, 378, 87-212.
http://dx.doi.org/10.1090/conm/378/07012 [5] Kharlamapovich, O. and Myasnikov, A. (2006) Elementary Theory of Free Non-Abelian Groups. Journal of Algebra, 302, 451-552.
http://dx.doi.org/10.1016/j.jalgebra.2006.03.033 [6] Sela, Z. (2001) Diophantine Geometry over Groups I: Makanin-Razborov Diagrams. Publications Mathématiques de l’Institut des Hautes études Scientifiques, 93, 31-106.
http://dx.doi.org/10.1007/s10240-001-8188-y [7] Sela, Z. (2003) Diophantine Geometry over Groups II: Completions, Closures and Formal Solutions. Israel Journal of Mathematics, 134, 173-254.
http://dx.doi.org/10.1007/BF02787407 [8] Sela, Z. (2005) Diophantine Geometry over Groups III: Rigid and Solid Solutions. Israel Journal of Mathematics, 147, 1-73.
http://dx.doi.org/10.1007/BF02785359 [9] Sela, Z. (2004) Diophantine Geometry over Groups IV: An Iterative Procedure for Validation of a Sentence. Israel Journal of Mathematics, 143, 1-130.
http://dx.doi.org/10.1007/BF02803494 [10] Sela, Z. (2005) Diophantine Geometry over Groups V: Quantifier Elimination. Israel Journal of Mathematics, 150, 1-197. [11] Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (2014) The Elementary Theory of Groups. Walter de Gruyter, Berlin.
http://dx.doi.org/10.1515/9783110342031 [12] Bell, J.L. and Slomson, A.B. (1971) Models and Ultraproducts: An Introduction. 2nd Revised Printing, North-Holland, Amsterdam. [13] Chang, C.C. and Keisler, H.J. (1977) Model Theory. 2nd Edition, North-Holland, Amsterdam. [14] Magnus, W., Karrass, A. and Solitar, D. (1966) Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Interscience Publishers, John Wiley and Sons, Inc., New York, London, Sydney. [15] Lyndon, R.C. and Schupp, P.E. (1977) Combinatorial Group Theory. Springer-Verlag, Berlin.
http://dx.doi.org/10.1007/978-3-642-61896-3 [16] Merzlyakov, Y.I. (1966) Positive Formulas on Free Groups. Algebra i Logika, 5, 25-42. [17] Sacerdote, G.S. (1972) Elementary Properties of Free Groups. Transactions of the American Mathematical Society, 178, 127-138.
http://dx.doi.org/10.1090/S0002-9947-1973-0320146-4 [18] Baumslag, B. (1967) Residually Free Groups. Proceedings of the London Mathematical Society, 17, 635-645. [19] Gaglione, A. and Spellman, D. (1993) Even More Model Theory of Free Groups. In: Corson, J., Dixon, M., Evans, M. and Rohl, F., Eds., Infinite Groups and Group Rings, World Scientific Press, Singapore City, 37-40.
http://dx.doi.org/10.1142/9789814503723_0004 [20] Remeslennikov, V.N. (1989) ?-Free Groups. Siberian Mathematical Journal, 30, 998-1001.
http://dx.doi.org/10.1007/BF00970922 [21] Chiswell, I. (1976) Abstract Length Functions in Groups. Mathematical Proceedings of the Cambridge Philosophical Society, 80, 451-463.
http://dx.doi.org/10.1017/S0305004100053093 [22] Ciobanu, L., Fine, B. and Rosenberger, G. (2015) Classes of Groups Generalizing a Theorem of Benjamin Baumslag. To Appear-Comm. in Alg. [23] Lyndon, R.C. (1960) Groups with Parametric Exponents. Transactions of the American Mathematical Society, 96, 518-533.
http://dx.doi.org/10.1090/S0002-9947-1960-0151502-6 [24] Makanin, G.S. (1982) Equations in a Free Group (Russian). Izv. Akad. Nauk SSSR, Ser. Mat., 46, 1199-1273. Transl. in Math. USSR Izv., V. 21, 1983, MR 84m:20040. [25] Makanin, G.S. (1985) Decidability of the Universal and Positive Theories of a Free Group. Mathematics of the USSR-Izvestiya, 25, 75-88.
http://dx.doi.org/10.1070/IM1985v025n01ABEH001269 [26] Razborov, A.A. (1984) On Systems of Equations in Free Groups. Izv.Akad. Nauk SSSR, 48, 779-832. Englisg transl: Math, USSR Izv., 25, 115-162. [27] Baumslag, G., Myasnikov, A. and Remeslennikov, V. (2002) Discriminating Completions of Hyperbolic Groups. Geometriae Dedicata, 92, 115-143.
http://dx.doi.org/10.1023/A:1019687202544 [28] Baumslag, G., Myasnikov, A. and Remeslennikov, V. (1999) Algebraic Geometry over Groups I. Algebraic Sets and Ideal Theory. Journal of Algebra, 219, 16-79. http://dx.doi.org/10.1006/jabr.1999.7881 [29] Carstensen, C., Fine, B. and Rosenberger, G. (2012) Abstract Algebra. De Gruyter, Berlin. [30] Bryant, R. (1977) The Verbal Topology of a Group. Journal of Algebra, 48, 340-346.
http://dx.doi.org/10.1016/0021-8693(77)90312-X [31] Guba, V. (1986) Equivalence of Infinite Systems of Equations in Free Groups and Semigroups to Finite Subsystems. Mat. Zametki, 40, 321-324. [32] Lyndon, R.C. (1959) The Equation in Free Groups. Michigan Mathematical Journal, 6, 155-164. [33] Lorenc, A.A. (1963) The Solution of Systems of Equations in One Unknown in Free Groups. Dokl. Akad. Nauk SSSR, 148, 262-266. [34] Appel, K.I. (1968) One-Variable Equations in Free Groups. Proceedings of the American Mathematical Society, 19, 912-918.
http://dx.doi.org/10.1090/S0002-9939-1968-0232826-3 [35] Csorgo, P., Fine, B. and Rosenberger, G. (2002) On Certain Equations in Free Groups. Acta Sci. Math., 68, 95-105. [36] Comerford, L. and Edmonds, C. (1989) Solutions of Equations in Free Groups. Proceedings of Conference in Group Theory Singapore 1987, Springer-Verlag, Berlin, 347-355. [37] Grigorchuk, R.I. and Kurchanov, P.F. (1992) On Quadratic Equations in Free Groups. Contemporary Mathematics, 131, 159-171.
http://dx.doi.org/10.1090/conm/131.1/1175769 [38] Grigorchuk, R. and Kurchanov, P. (1990) Some Questions of Group Theory Related to Geometry. In Itogi Nauki i Techniki, Sovremennye problemy matematiki. Fundamental’nye napravlenia, VINITI, 58. Encyclopedia of math. sciences, English Translation in 1993. [39] Rips, E. and Sela, Z. (1997) Cyclic Splittings of Finitely Presented Groups and the Canonical JSJ Decomposition. Annals of Mathematics, 146, 53-109.
http://dx.doi.org/10.2307/2951832 [40] Howie, J. (2004) Some Results on One-Relator Surface Groups. Boletín de la Sociedad Matemática Mexicana, 10, 255-262. [41] Bogopolski, O. (2005) A Surface Groups Analogue of a Theorem of Magnus. Cont. Math, 352, 55-89. [42] Bogopolski, O. and Sviridov, K. (2008) A Magnus Theorem for Some One-Relator Groups. The Zieschang Gedenkschrift, 14, 63-73. [43] Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2013) Something for Nothing: Some Consequences of the Solution of the Tarski Problems. To Appear Proc. of Groups St Andrews. [44] Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2015) On Elementary Free Groups. To Appear Cont. Math. [45] Gaglione, A., Lipschutz, S. and Spellman, D. (2009) Almost Locally Free Groups and a Theorem of Magnus. Journal of Groups, Complexity, Cryptology, 1, 181-198. [46] Bumagin, I., Kharlampovich, O. and Myasnikov, A. (2007) The Isomorphism Problem for Finitely Generated Fully Residually Free Groups. Journal of Pure and Applied Algebra, 208, 961-977.
http://dx.doi.org/10.1016/j.jpaa.2006.03.025 [47] Fine, B., Kharlampovich, O., Myasnikov, A., Remeslennikov, V. and Rosenberger, G. (2012) Tame Automorphisms of Elementary Free Groups. Communications in Algebra, 1, 1-15. [48] Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (1998) A Classification of Fully Residually Free Groups of Rank Three or Less. Journal of Algebra, 200, 571-605.
http://dx.doi.org/10.1006/jabr.1997.7205 [49] Kharlamapovich, O. and Myasnikov, A. (1998) Hyperbolic Groups and Free Constructions. Transactions of the American Mathematical Society, 350, 571-613.
http://dx.doi.org/10.1090/S0002-9947-98-01773-5 [50] Sela, Z. (1995) The Isomorphism Problem for Hyperbolic Groups I. Annals of Mathematics, 141, 217-283.
http://dx.doi.org/10.2307/2118520 [51] Gildenhuys, D., Kharlampovich, O. and Myasnikov, A. (1995) CSA Groups and Separated Free Constructions. Bulletin of the Australian Mathematical Society, 52, 63-84.
http://dx.doi.org/10.1017/S0004972700014453 [52] Baumslag, G. (1962) On Generalised Free Products. Mathematische Zeitschrift, 78, 423-438.
http://dx.doi.org/10.1007/BF01195185 [53] Fine, B. and Rosenberger, G. (2011) Faithful Representations of Hyperbolic Limit Groups. Groups Complexity Cryptology, 3, 349-355. [54] Fine, B. and Rosenberger, G. (2013) Faithful Representations of Limit Groups II. Groups Complexity Cryptology, 5, 91-96.
http://dx.doi.org/10.1515/gcc-2013-0005
[1] Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: I. Irreducibility of Quadratic Equations and Nullstellensatz. Journal of Algebra, 200, 472-516.
http://dx.doi.org/10.1006/jabr.1997.7183 [2] Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: II. Systems in Triangular Quasi-Quadratic Form and Description of Residually Free Groups. Journal of Algebra, 200, 517-570. [3] Kharlamapovich, O. and Myasnikov, A. (2005) Implicit Function Theorem over Free Groups. Journal of Algebra, 290, 1-203.
http://dx.doi.org/10.1016/j.jalgebra.2005.04.001 [4] Kharlamapovich, O. and Myasnikov, A. (2005) Effective JSJ Decompositions. Contemporary Mathematics, 378, 87-212.
http://dx.doi.org/10.1090/conm/378/07012 [5] Kharlamapovich, O. and Myasnikov, A. (2006) Elementary Theory of Free Non-Abelian Groups. Journal of Algebra, 302, 451-552.
http://dx.doi.org/10.1016/j.jalgebra.2006.03.033 [6] Sela, Z. (2001) Diophantine Geometry over Groups I: Makanin-Razborov Diagrams. Publications Mathématiques de l’Institut des Hautes études Scientifiques, 93, 31-106.
http://dx.doi.org/10.1007/s10240-001-8188-y [7] Sela, Z. (2003) Diophantine Geometry over Groups II: Completions, Closures and Formal Solutions. Israel Journal of Mathematics, 134, 173-254.
http://dx.doi.org/10.1007/BF02787407 [8] Sela, Z. (2005) Diophantine Geometry over Groups III: Rigid and Solid Solutions. Israel Journal of Mathematics, 147, 1-73.
http://dx.doi.org/10.1007/BF02785359 [9] Sela, Z. (2004) Diophantine Geometry over Groups IV: An Iterative Procedure for Validation of a Sentence. Israel Journal of Mathematics, 143, 1-130.
http://dx.doi.org/10.1007/BF02803494 [10] Sela, Z. (2005) Diophantine Geometry over Groups V: Quantifier Elimination. Israel Journal of Mathematics, 150, 1-197. [11] Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (2014) The Elementary Theory of Groups. Walter de Gruyter, Berlin.
http://dx.doi.org/10.1515/9783110342031 [12] Bell, J.L. and Slomson, A.B. (1971) Models and Ultraproducts: An Introduction. 2nd Revised Printing, North-Holland, Amsterdam. [13] Chang, C.C. and Keisler, H.J. (1977) Model Theory. 2nd Edition, North-Holland, Amsterdam. [14] Magnus, W., Karrass, A. and Solitar, D. (1966) Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Interscience Publishers, John Wiley and Sons, Inc., New York, London, Sydney. [15] Lyndon, R.C. and Schupp, P.E. (1977) Combinatorial Group Theory. Springer-Verlag, Berlin.
http://dx.doi.org/10.1007/978-3-642-61896-3 [16] Merzlyakov, Y.I. (1966) Positive Formulas on Free Groups. Algebra i Logika, 5, 25-42. [17] Sacerdote, G.S. (1972) Elementary Properties of Free Groups. Transactions of the American Mathematical Society, 178, 127-138.
http://dx.doi.org/10.1090/S0002-9947-1973-0320146-4 [18] Baumslag, B. (1967) Residually Free Groups. Proceedings of the London Mathematical Society, 17, 635-645. [19] Gaglione, A. and Spellman, D. (1993) Even More Model Theory of Free Groups. In: Corson, J., Dixon, M., Evans, M. and Rohl, F., Eds., Infinite Groups and Group Rings, World Scientific Press, Singapore City, 37-40.
http://dx.doi.org/10.1142/9789814503723_0004 [20] Remeslennikov, V.N. (1989) ?-Free Groups. Siberian Mathematical Journal, 30, 998-1001.
http://dx.doi.org/10.1007/BF00970922 [21] Chiswell, I. (1976) Abstract Length Functions in Groups. Mathematical Proceedings of the Cambridge Philosophical Society, 80, 451-463.
http://dx.doi.org/10.1017/S0305004100053093 [22] Ciobanu, L., Fine, B. and Rosenberger, G. (2015) Classes of Groups Generalizing a Theorem of Benjamin Baumslag. To Appear-Comm. in Alg. [23] Lyndon, R.C. (1960) Groups with Parametric Exponents. Transactions of the American Mathematical Society, 96, 518-533.
http://dx.doi.org/10.1090/S0002-9947-1960-0151502-6 [24] Makanin, G.S. (1982) Equations in a Free Group (Russian). Izv. Akad. Nauk SSSR, Ser. Mat., 46, 1199-1273. Transl. in Math. USSR Izv., V. 21, 1983, MR 84m:20040. [25] Makanin, G.S. (1985) Decidability of the Universal and Positive Theories of a Free Group. Mathematics of the USSR-Izvestiya, 25, 75-88.
http://dx.doi.org/10.1070/IM1985v025n01ABEH001269 [26] Razborov, A.A. (1984) On Systems of Equations in Free Groups. Izv.Akad. Nauk SSSR, 48, 779-832. Englisg transl: Math, USSR Izv., 25, 115-162. [27] Baumslag, G., Myasnikov, A. and Remeslennikov, V. (2002) Discriminating Completions of Hyperbolic Groups. Geometriae Dedicata, 92, 115-143.
http://dx.doi.org/10.1023/A:1019687202544 [28] Baumslag, G., Myasnikov, A. and Remeslennikov, V. (1999) Algebraic Geometry over Groups I. Algebraic Sets and Ideal Theory. Journal of Algebra, 219, 16-79. http://dx.doi.org/10.1006/jabr.1999.7881 [29] Carstensen, C., Fine, B. and Rosenberger, G. (2012) Abstract Algebra. De Gruyter, Berlin. [30] Bryant, R. (1977) The Verbal Topology of a Group. Journal of Algebra, 48, 340-346.
http://dx.doi.org/10.1016/0021-8693(77)90312-X [31] Guba, V. (1986) Equivalence of Infinite Systems of Equations in Free Groups and Semigroups to Finite Subsystems. Mat. Zametki, 40, 321-324. [32] Lyndon, R.C. (1959) The Equation in Free Groups. Michigan Mathematical Journal, 6, 155-164. [33] Lorenc, A.A. (1963) The Solution of Systems of Equations in One Unknown in Free Groups. Dokl. Akad. Nauk SSSR, 148, 262-266. [34] Appel, K.I. (1968) One-Variable Equations in Free Groups. Proceedings of the American Mathematical Society, 19, 912-918.
http://dx.doi.org/10.1090/S0002-9939-1968-0232826-3 [35] Csorgo, P., Fine, B. and Rosenberger, G. (2002) On Certain Equations in Free Groups. Acta Sci. Math., 68, 95-105. [36] Comerford, L. and Edmonds, C. (1989) Solutions of Equations in Free Groups. Proceedings of Conference in Group Theory Singapore 1987, Springer-Verlag, Berlin, 347-355. [37] Grigorchuk, R.I. and Kurchanov, P.F. (1992) On Quadratic Equations in Free Groups. Contemporary Mathematics, 131, 159-171.
http://dx.doi.org/10.1090/conm/131.1/1175769 [38] Grigorchuk, R. and Kurchanov, P. (1990) Some Questions of Group Theory Related to Geometry. In Itogi Nauki i Techniki, Sovremennye problemy matematiki. Fundamental’nye napravlenia, VINITI, 58. Encyclopedia of math. sciences, English Translation in 1993. [39] Rips, E. and Sela, Z. (1997) Cyclic Splittings of Finitely Presented Groups and the Canonical JSJ Decomposition. Annals of Mathematics, 146, 53-109.
http://dx.doi.org/10.2307/2951832 [40] Howie, J. (2004) Some Results on One-Relator Surface Groups. Boletín de la Sociedad Matemática Mexicana, 10, 255-262. [41] Bogopolski, O. (2005) A Surface Groups Analogue of a Theorem of Magnus. Cont. Math, 352, 55-89. [42] Bogopolski, O. and Sviridov, K. (2008) A Magnus Theorem for Some One-Relator Groups. The Zieschang Gedenkschrift, 14, 63-73. [43] Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2013) Something for Nothing: Some Consequences of the Solution of the Tarski Problems. To Appear Proc. of Groups St Andrews. [44] Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2015) On Elementary Free Groups. To Appear Cont. Math. [45] Gaglione, A., Lipschutz, S. and Spellman, D. (2009) Almost Locally Free Groups and a Theorem of Magnus. Journal of Groups, Complexity, Cryptology, 1, 181-198. [46] Bumagin, I., Kharlampovich, O. and Myasnikov, A. (2007) The Isomorphism Problem for Finitely Generated Fully Residually Free Groups. Journal of Pure and Applied Algebra, 208, 961-977.
http://dx.doi.org/10.1016/j.jpaa.2006.03.025 [47] Fine, B., Kharlampovich, O., Myasnikov, A., Remeslennikov, V. and Rosenberger, G. (2012) Tame Automorphisms of Elementary Free Groups. Communications in Algebra, 1, 1-15. [48] Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (1998) A Classification of Fully Residually Free Groups of Rank Three or Less. Journal of Algebra, 200, 571-605.
http://dx.doi.org/10.1006/jabr.1997.7205 [49] Kharlamapovich, O. and Myasnikov, A. (1998) Hyperbolic Groups and Free Constructions. Transactions of the American Mathematical Society, 350, 571-613.
http://dx.doi.org/10.1090/S0002-9947-98-01773-5 [50] Sela, Z. (1995) The Isomorphism Problem for Hyperbolic Groups I. Annals of Mathematics, 141, 217-283.
http://dx.doi.org/10.2307/2118520 [51] Gildenhuys, D., Kharlampovich, O. and Myasnikov, A. (1995) CSA Groups and Separated Free Constructions. Bulletin of the Australian Mathematical Society, 52, 63-84.
http://dx.doi.org/10.1017/S0004972700014453 [52] Baumslag, G. (1962) On Generalised Free Products. Mathematische Zeitschrift, 78, 423-438.
http://dx.doi.org/10.1007/BF01195185 [53] Fine, B. and Rosenberger, G. (2011) Faithful Representations of Hyperbolic Limit Groups. Groups Complexity Cryptology, 3, 349-355. [54] Fine, B. and Rosenberger, G. (2013) Faithful Representations of Limit Groups II. Groups Complexity Cryptology, 5, 91-96.
http://dx.doi.org/10.1515/gcc-2013-0005