How does one get all substructures of the Integers? Consider the L-structure:
$$ \mathcal Z = (\mathbb Z; 0,-,+)$$
I wanted to find all substructures (because I was trying to find out if it was possible to have an algorithm for finding all substructures of a given L-structure so I started with an example).
Then a friend told me that all and only the substructures are of the form:
$$ n \mathbb Z = \{ k \in \mathbb Z \mid  \exists k' \in \mathbb Z, k=n\cdot k'  \}$$
for $n \in \mathbb{N}$, e.g. $5 \mathbb Z = \{ 0,5,-5,10,-10,...\}$.
Hence, the set of substructures of $\mathcal{Z}$ is:
$$ Substructures = \{ n \mathbb Z \mid n \in \mathbb N \}.$$
My question is why is it that any other random subset of the integers is not possibly a substructure?
I assume it must not satisfy closure (or relation, though this set doesn't have one). But how does one prove this?
 A: This is less mysterious than it may first appear: we can simply prove directly that any substructure has that form.
Suppose $A$ is a substructure of $\mathcal{Z}=(\mathbb{Z};0,-,+)$. Then there are a couple possibilities:


*

*$A=\{0\}$. This is just $0\mathbb{Z}$, so this fits the pattern.

*$A\not=\{0\}$. In this case $A$ contains some positive element (why?). Let $m$ be the smallest positive element of $A$ (why is there such a thing?).

*We now can show (how?) that $m\mathbb{Z}\subseteq A$; I claim that in fact $A=m\mathbb{Z}$. 

*Suppose $A\not=m\mathbb{Z}$. Then there is some $a\in A$ which is not a multiple of $m$. Let $b$ be the largest multiple of $m$ which is less than $a$. Then:


*

*What can you say about $a-b$ vis-a-vis the substructure $A$?

*Why is this a problem? (Think about our assumption on $m$ ...)

A follow-up exercise: show that if we drop "$-$" from our language, things get messier. Can you classify the substructures of $(\mathbb{Z}; 0,+)$?


"De-logicing" things for a bit, if you're familiar with group theory, notice that this is really just an instance of the following fact:

Every subgroup of a cyclic group is cyclic.

Incidentally, looking back at the follow-up exercise, we see the importance of the language in these questions: any substructure of $(\mathbb{Z};0,-,+)$ is a subgroup, but there are substructures of $(\mathbb{Z};0,+)$ which are not groups (e.g. $\mathbb{N}$) but merely submonoids!
The "flavor" of logic often makes things feel mysterious at first, but you should always look for a "concrete(r)" connection - often, and especially in model theory, a connection to some more familiar fact of abstract algebra.
Incidentally, this is why abstract algebra is often considered a prerequisite for model theory: it's not that you actually need it, but rather that it gives you a good foundation on which to fall back from time to time.
