Splitting the natural numbers into two sets $A$ and $B$ such that for distinct elements $m,n\in A$ we have $m+n\in B$ and vice-versa.

Question

Why it is impossible to split the natural numbers into two sets $A$ and $B$ such that for distinct elements $m, n \in A$ we have $m + n \in B$ and vice-versa?

Also, does vice-versa means that there are distinct elements such that $x + y \in A$?

How do I show the proof?

Answer 1

Vice versa means that for distinct $m,n \in B$, $m+n \in A$.

I guess you have to work through some cases.

For instance, suppose that $1 \in A$ and $2 \in A$. Then $3 \in B$.

• If $4 \in A$, we have $5, 6 \in B$, i.e. $8, 9 \in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
• If $4 \in B$, we have $7 \in A$, i.e. $8, 9 \in B$, i.e. $11, 12, 13 \in A$ which is a contradiction since $12=1+11$.

Answer 2

It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.

Suppose the set $S=\{1,2,3,4,5,6,7,8,9,10\}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.

Consider the complete graph with vertex set $V=\{0,1,3,4,9,10\}$. For $x,y\in V$, color the edge $xy$ red if $|x-y|\in A$, blue if $|x-y|\in B$. Then there are three vertices $x\lt y\lt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,n\in S$, and $m\ne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+n\in A$; if they are all blue, then $m,n,m+n\in B$.

Answer 3

Theorem [Schur, 1916]. For any partition of the set of positive integers in finite pieces, there are integers $x$ and $y$ with $x \neq y$ such that the set $\{x,y,x+y\}$ is contained in the same piece.

Proof. We define a $\Delta-$set as a set of natural numbers of the form $\{a_{i}-a_{j} \, | \, j<i<\omega\}$, where $\{ a_{i} \}_{i<\omega}$ is an increasing sequence of natural numbers.

Fact: The set of positive integers is a $\Delta-$set.

Let $A=\{a_{i}-a_{j} \, | \, j<i<\omega\}$ be any fixed $\Delta-$set and let $c: A \rightarrow r$ be a finite coloration of $A$. Now, let $\pi: [\mathbb{N}]^{2} \rightarrow r$ be the finite coloration of $[\mathbb{N}]^{2}$ given by $\pi (\{i,j\}) = c (a_{i}-a_{j})$ when $j<i$.

Thus, the Ramsey's theorem implies that there exist $H \in [\mathbb{N}]^{\omega}$ such that $\pi$ is constant on $[H]^{2}$. Therefore, for all $i,j,k \in H$ with $k<j<i$ we have that $\{i,j,k\}$ is monochromatic for $\pi$, hence if $x=a_{i}-a_{j}$, $y=a_{j}-a_{k}$ and $z=a_{i}-a_{k}$ then $x,y,z \in A$ are such that $z=x+y$ and $\{x,y,x+y\}$ is monochromatic for $c$. $\; \; \;\square$

Corollary. There are not sets $A \neq \emptyset$ and $B \neq \emptyset$ of positive integers, with $A \cap B = \emptyset$ and $A \cup B = \mathbb{N} - \{0\}$, such that either $x+y\in B$ for all $x,y \in A$ with $x\neq y$ or $x+y\in A$ for all $x,y \in B$ with $x\neq y$.