6
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ It's already answered, but to emphasize: it's unrelated. For free semigroups (or free monoids, or free abelian semigroups/monoids, or free magmas, and many others), it's quite trivial as one can characterize generators as non-products (or non-products-except-using-the-unit). For abelian groups, it's an easy trick, but definitely a trick (counting the maximal number of elements whose pairwise differences are non-squares). $\endgroup$
    – YCor
    Feb 3, 2020 at 16:42

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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