Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

how does one describe all partitions on the integers that are compatible with the operation +?

By compatible it is means that for any 2 sets in the partition $A,B\in P$, and every combination of elements (one element from each set) all of these summations are contained in a single set $C$ in the partition. ($a\in A , b\in B \Rightarrow c\in C$)

share|cite|improve this question
$\mathbb Z / n \mathbb Z$? I'm not sure I understand your question. – Rudy the Reindeer Dec 15 '12 at 21:47
yes. i could see that they all work. i was wondering if there were more. – pad Dec 15 '12 at 22:11
The enumeration of compatible partitions in the answer is incomplete. For example, $\{1\}\cup\{2,4,\dots\}\cup\{3,5,\dots\}$ is not included. – Hu Zhengtang Dec 22 '12 at 1:03
up vote 0 down vote accepted

I believe there are only $\aleph_0$ such partitions.

Clearly every partition by equivalence $mod(p)$ for some $p\in\mathbb{N}$ works. (if $a\in A, b\in B,c \in C $ then if $a+b \equiv_p c$ it easily follows that $A+B=C$). For example $\{ 1,4,7..\},\{ 2,5,8..\}$ and $\{3,6,9..\}$ works.

Now lets prove that all partitions which work look "somewhat" like that!

  1. in such a partition, every set $A$ is equal to $ \{i|i = pk+ c,k\in\mathbb{N}\} $ for some $c,p$: Take the smallest element $c\in A$ and the smallest $p$ such that $p\in\{a-b|a,b\in A\}$ clearly $\{ a+pk|k\in \mathbb{N}\}\subseteq A$ if there is an element $b \in A$ not in this set then $\exists k$ such that $a+pk-b<p$ (because $b \equiv_p t$ for $t$ different than 0) in contrast to the way we choose $p$ .

  2. Every subset either contains a single element or is equal to $ \{i|i = pk+ c,k\in\mathbb{N}\} $ for the same $p$ in all sets. If $ A=\{i|i = pk+ c,k\in\mathbb{N}\} $ and $ B=\{j| j = qk+ r,k\in\mathbb{N}\} $ (assume $p$ is the smallest such difference for any subset in this partion) then we get that in $A+B$ there is an even smaller one! (if you need explanation to that step comment, but it is exactly with the same reasons used to prove 1.)

From here we can understand that either there is a set $A=\{i,i+1,i+1... \}$ and all integers smaller than $i$ are in a sets containing single elements. Or we have a $mod(p)$ partition.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.