You're right, that was misleading. Let me restate the remark in a more useful form. First, $m$-equivalence is determined by constant-size neighbourhoods iff $(\Z,<,A,S,P)$ has quantifier elimination. Now, for any set $A$, the following are equivalent: (1) $(\Z,<,A,S,P)$ has quantifier elimination, and no definable elements; (2) every finite string that occurs in $A$ occurs in all sufficintly long intervals. It's not immediately obvious that there are nonperiodic sets $A$ with this property, but one such is the Thue-Morse sequence, extended to $\Z$ by putting $-n-1\in A$ iff $n\in A$. So, ... — Emil Jeřábek May 9 '15 at 18:11

Can anyone give an elementary forcing-free proof that if we choose $A$ by coin flips, then almost surely $\langle\Z,<,A\rangle$ has no definable elements? — Joel David Hamkins May 8 '15 at 13:59

@Robinson: but $(\Z/2\Z) \times A_5$ is not isomorphic as a group to $SL(2,5)$, no? — Damien Robert Apr 11 '14 at 1:02