This question comes from problem 8.13 (b) of chapter 2 of Artin's Algebra (2nd edition).
By compatible, it means that:
Let $S$ be a set with a law of composition (i.e. a binary operation). A partition $P$ of $S$ is compatible with the law of composition if for every $i$ and $j$, there exists $k$ such that $$\Pi_i\Pi_j\subset\Pi_k$$ where $\Pi_i,\Pi_j,\Pi_k\in P$ and the product set $\Pi_i\Pi_j=\{ab\mid a\in\Pi_i,b\in\Pi_j\}$.
I can see that:
-
The partition $P=\{\{n\}\mid n\in\mathbb{Z}\}$ is compatible with the usual addition $+$.
-
For any $n\in\mathbb{Z^+}$, $\mathbb{Z}/n\mathbb{Z}$ (i.e. the integers modulo $n$) is a partition of $\mathbb{Z}$ that is compatible with the usual addition $+$.
Could anyone please give me some hint on how to prove that there exists no other partition which is compatible with $+$? (or if there is, how could one find all of them?)
Thanks in advance!
Best Answer
Fun exercise. I hope you've given it a good try yourself. As a hint, try to show the block containing $0$ is a subgroup. A complete solution is below.
I assume you're letting $(S, \circ) = (\mathbb{Z}, +)$. I'll write $\Pi_i + \Pi_j$ additively to avoid confusion.
Say $\Pi_0$ contains $0$. Then $\Pi_j \subset \Pi_0 + \Pi_j \subset \Pi_k$, forcing $j=k$ and $\Pi_j = \Pi_0 + \Pi_j$ for all $j$. In particular, $\Pi_0 = \Pi_0 + \Pi_0$, so $\Pi_0$ is closed under sums.
Now suppose $n \in \Pi_i$ and $-n \in \Pi_j$. Then $0 \in \Pi_i + \Pi_j \subset \Pi_k$, forcing $\Pi_k = \Pi_0$ and $\Pi_i + \Pi_j = \Pi_0$. When $i=0$, this says $\Pi_0 = \Pi_0 + \Pi_j \supset \Pi_j$, so $-n \in \Pi_0$ and $\Pi_0$ is closed under inverses.
Hence $\Pi_0$ is a subgroup. Thus $\Pi_0 = m\mathbb{Z}$ for some fixed $m \in \mathbb{Z}_{\geq 0}$.
Suppose $m=0$. If $\Pi_i$ contained more than 1 element, the above equation $\Pi_i + \Pi_j = \Pi_0$ furnishes a contradiction, so each $\Pi_i$ is a singleton and we're in your first case.
Now suppose $m>0$. Suppose $n \in \Pi_j$. Then $\Pi_j = m\mathbb{Z} + \Pi_j \supset n + m\mathbb{Z}$. Hence the congruence classes $n + m\mathbb{Z}$ for $0 \leq n < m$ are each contained in some $\Pi_j$, so the partition must be obtained by taking unions of congruence classes. But now suppose $\Pi_i$ were the union of at least two congruence classes. Then the equation $\Pi_i + \Pi_j = \Pi_0$ again furnishes a contradiction since $\Pi_0$ is only a single congruence class.
So there are indeed no more.