need references regarding the elementary theory of free semigroup and free abelian groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:29:44Z http://mathoverflow.net/feeds/question/55256 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55256/need-references-regarding-the-elementary-theory-of-free-semigroup-and-free-abelia need references regarding the elementary theory of free semigroup and free abelian groups dan 2011-02-12T23:35:09Z 2011-02-13T02:04:24Z <p>Recently, I read that two free abelian groups \$S\$ and \$T\$ have the same elementary theory if and only if rank\$S\$=rank\$T\$. Does anyone have a reference with a proof of this? Also, what is known about the elementary theory of non-abelian free semigroups? I know that non-abelian free groups of finite rank have the same elementary theory; does this imply the analogous statement for free semigroups? Thanks!</p> http://mathoverflow.net/questions/55256/need-references-regarding-the-elementary-theory-of-free-semigroup-and-free-abelia/55268#55268 Answer by HW for need references regarding the elementary theory of free semigroup and free abelian groups HW 2011-02-13T01:07:18Z 2011-02-13T01:07:18Z <p>It is easy to prove that non-isomorphic free abelian groups (of finite rank) have distinct elementary theories, by exhibiting specific sentences that hold in one but not the other. For instance, \$\mathbb{Z}\$ is distinguished by the property that for some element \$y\$ (eg \$y=1\$), either \$x\$ or \$x+y\$ is even. In other words, the sentence</p> <p>\$\exists y~\forall x~\exists z~(x=2z) \vee (x+y=2z) \$</p> <p>holds in \$\mathbb{Z}\$ but not in \$\mathbb{Z}^n\$ for any \$n>1\$. The same idea can be used to distinguish \$\mathbb{Z}^m\$ and \$\mathbb{Z}^n\$ for any \$m\neq n\$.</p> http://mathoverflow.net/questions/55256/need-references-regarding-the-elementary-theory-of-free-semigroup-and-free-abelia/55269#55269 Answer by Mark Sapir for need references regarding the elementary theory of free semigroup and free abelian groups Mark Sapir 2011-02-13T01:24:16Z 2011-02-13T02:04:24Z <p>Two finitely generated free semigroups of different ranks have different elementary theories. Indeed, the set of elements \$x\$ such that \$\forall z,t \neg(x=zt)\$ is exactly the set of generators of the free semigroup. So the rank of a finitely generated free semigroup is elementary definable. </p> <p>For the free Abelian group of rank \$n\$ the formula distinguishing it from any free Abelian group of rank \$\gt n\$ is this:</p> <p>\$\$\exists x_1,...,x_{2^n} \forall y \exists z: yx_1=z^2 \vee yx_2=z^2 \vee ... \vee yx_{2^n}=z^2\$\$ (we enumerate the subsets of the set of generators and for the subset number \$i\$ we denote the product of generators from that subset by \$x_i\$). It is easy to see that this formula holds in every free Abelian group of rank \$\le n\$ and does not hold if the rank is \$\gt n\$. For \$n=1\$ this is the same formula as in the answer of Henry Wilton. </p> <p>The standard reference for elementary classification of Abelian groups is Szmielew, W. Elementary properties of Abelian groups. Fund. Math. 41 (1955), 203–271. A shorter proof can be found in Kargapolov, M. I. On the elementary theory of Abelian groups. Algebra i Logika Sem. 1 1962/1963 no. 6, 26–36 and Eklof, Paul C.; Fischer, Edward R. The elementary theory of abelian groups. Ann. Math. Logic 4 (1972), 115–171 and Zakon, Elias Model-completeness and elementary properties of torsion free abelian groups. Canad. J. Math. 26 (1974), 829–840 (for torsion-free groups). </p>