How does one get all substructures of the Integers?

Question

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?

Answer 1

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.