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

-
When you say that you are being "asked to find this in a question", do you mean it is a homework question? –  Asaf Karagila Nov 25 '11 at 20:02
@1 yes i mean union –  user13791 Nov 25 '11 at 20:04
@2 this is not my homework question, but my homework question requires this. –  user13791 Nov 25 '11 at 20:04
It sounds to me as though this is a homework question. Either way, the answers should fit. Also, instead of @1 you can - and should - write the username it will then notify that user of your reply. –  Asaf Karagila Nov 25 '11 at 20:05

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

-
JavaMan's map allows you to count the elements of the union (thus witnessing its countability) by counting as follows: "First element of $A$, First element of $B$, Second element of $A$, Second element of $B$, ..." –  Austin Mohr Nov 25 '11 at 20:14

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.

-
The sum can also be defined in cardinalities. The sum of two sets is their disjoint union (take $\{0\}\times A\cup\{1\}\times B$, for example.) –  Asaf Karagila Nov 25 '11 at 21:33