Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

For the free Abelian group of rank $n$ the formula distinguishing it from any free Abelian group of rank $\gt n$ is this:

$$\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.

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

share|improve this answer

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

$\exists y~\forall x~\exists z~(x=2z) \vee (x+y=2z) $

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.