# Sum of two countably infinite sets

What is the sum of two countably infinite sets? Another countably infinite set? I am asked to find this in a question.

#### Solutions Collecting From Web of "Sum of two countably infinite sets"

Hint: Assuming “sum” means “union”, let $A = \{a_1, a_2, \dots\}$ and $B = \{b_1 , b_2, \dots\}$ be two countable sets. Consider the map

$$f(n) = \left\{ \begin{array}{ccc} b_{n/2} & & n \text{ is even} \\ a_{\frac{n+1}{2}} & & n \text{ is odd} \end{array} \right.$$

Show that $f(n)$ is a bijection from $\mathbb{N} \to A \cup B$.

Spoiler:

Can you count their elements?
1,3,5,7…
2,4,6,8…

For the operation suggested in the question, the proper name is ‘union’, not sum. The sum of two sets (the Minkowski sum) can be defined as

$$A+B=\{a+b : a \in A, b \in B\}.$$

In this case, it can be proved that if $A,B$ are countable, then so is $A+B$. First, note that $A \times B \simeq \Bbb{N}\times \Bbb{N}\simeq \Bbb{N}$ ( $\simeq$ means that they have the same cardinal number).

Then the function $f: A\times B \to A+B$ defined by $f(a,b)=a+b$ is surjective by definition. This means that $\operatorname{card}(A \times B) \geq \operatorname{card}(A+B)$, therefore $A+B$ is countably infinite also.