2
$\begingroup$

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$)

  • 1
    The enumeration of compatible partitions in the answer is incomplete. For example, $\{1\}\cup\{2,4,\dots\}\cup\{3,5,\dots\}$ is not included.2012-12-22

1 Answers 1

0

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 (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.