2
$\begingroup$

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

  • 1
    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.2011-11-25

3 Answers 3

7

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

  • 3
    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$, ..."2011-11-25
1

Spoiler:

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

1

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.

  • 0
    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.)2011-11-25