Checking if a set is definable in a given structure

Question

I am trying to find out whether the integers divisible by certain numbers are definable in the structure of $\mathbb{Z}$.

but I really have no clue how to even begin, I've been sitting at my desk for such a long time now. :( I would really appreciate if anybody had an idea about this?

Thanks so much, Lin

Answer 1

Remember that any definable subset of a structure $\mathcal{A}$ must be preserved by all automorphisms: if $D\subseteq\mathcal{A}$ is definable and $\alpha$ is an automorphism of $\mathcal{A}$ we must have $D=\{\alpha(d):d\in D\}$. If you haven't seen this before, it's a good exercise (use induction on complexity). This gives us a powerful tool for proving undefinability: simply exhibit an automorphism which doesn't preserve the set (or function or relation for that matter) in question!

So first let's consider the problem of understanding $Aut(\mathcal{M})$:

What are the automorphisms of $\mathcal{M}$?

As a hint, note that the automorphisms of the simpler structure $(\mathbb{Z};<)$ are just the shift maps $\alpha_z:x\mapsto x+z$ for $z\in\mathbb{Z}$. So you just need to figure out which shifts preserve the additional structure of $\mathcal{M}$.

HINT: think about least common multiples ...

The automorphisms of $\mathcal{M}$ are exactly the maps of the form $$\alpha_z: x\mapsto x+28z$$ for $z\in\mathbb{Z}$.

Now can you find an automorphism of $\mathcal{M}$ which does not preserve $11\mathbb{Z}$?

For example, the map $x\mapsto x+28$ sends $11\in11\mathbb{Z}$ to $39\not\in11\mathbb{Z}$.

---

It's worth noting that this "automorphism trick" is not always applicable. For example, the structure $(\mathbb{Z};0,<)$ has no automorphisms at all but of course "most" of its subsets are not definable (it has uncountably many subsets but only countably many definable subsets). In general we have to use more complicated techniques - key terms include "quantifier elimination" (and its weaker-but-more-common cousin "model completeness") and "Ehrenfeucht-Fraisse games."

On the other hand, this "automorphism trick" is not limited to first-order logic specifically. There are other logics of interest (e.g. second-order logic, infinitary logic(s), and a whole slew of others) and it works for them too: "isomorphism-invariance" is generally considered one of the criteria something has to satisfy in order to be a logic.

So the "automorphism trick" is simultaneously rather limited and surprisingly broad!