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