Elementary equivalence of $\mathbb{Z}^{n}$

Question

I have a question in model theory where I need to prove that $\mathbb{Z}^{n} \not\equiv \mathbb{Z}^{m}$ (= not elementarily equivalent) if $n\neq m$ in the language of groups $L = \{\circ ,^{-1},0 \}$.

I tried some sentences about generators but of course that FOL can't say something about basis... can someone help me?

Answer 1

The idea I have is to look at the coordinates of each element after they are reduced modulo $2$, and ask about the set of odd coordinates.

As usual, say that an element $x$ is divisible by $2$ if $(\exists z)[z+z=x]$. Say that a set of elements $X = \{x_1, \ldots, x_k\}$ is pairwise distinct modulo $2$ if no pairwise difference $x_i-x_j$ is divisible by $2$.

In $\mathbb{Z}^k$ we can find a set of $2^k-1$ elements that are not divisible by $2$ and are pairwise distinct modulo $2$, but not a set of $2^k$ such elements. These elements are in correspondence with the nonempty subsets of $k$ - the set tells which coordinates should be odd.

This answer is a direct generalization of Isomorphism between direct sum of $\mathbb{Z}$ and $\mathbb{Z}$ . We could also replace "difference" with "sum", so the groups in the question are not elementarily equivalent even in the language with only addition and equality.

I mentioned in a comment: one way to get started on these problems is to first prove (without counting generators) that the two groups are not isomorphic - that often involves some "algebraic obstacle" that can be expressed as a first-order sentence. In this case, we have $\mathbb{Z}^n$ as a natural substructure of $\mathbb{Z}^m$ when $n < m$. So disproving the elementary equivalence amounts to showing that the Tarski-Vaught test fails (although that test is formally stronger, and asks about an elementary embedding). Thus, if the groups are not elementarily equivalent, we expect that the algebraic obstacle will, as a matter of practice, be found as the counterexample formula for the Tarski-Vaught test.

Answer 2

Suppose that $n<m$. Consider the first-order sentence that says "There are $n$ elements $x_1,\ldots,x_n$ such that, for every element $y$, one of the $2^n$ elements $z_j$ (explicitly written out in our first order sentence, since $n$ is fixed) obtained by adding some combination of the $x_i$ to $y$ can be written as $z_j = w \circ w$ for some $w$." This sentence is true in $\mathbb{Z}^n$ but not $\mathbb{Z}^m$.