What is the sum of two countably infinite sets? Another countably infinite set? I am asked to find this in a question.
Sum of two countably infinite sets
-
1It 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. – 2011-11-25
3 Answers
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$.
-
3JavaMan'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$, ..." – 2011-11-25
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.
-
0The 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.) – 2011-11-25