Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this 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
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. –  Asaf Karagila Nov 25 '11 at 20:05
add comment

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
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$, ..." –  Austin Mohr Nov 25 '11 at 20:14
add comment

Spoiler:

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.