2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ When you say that you are being "asked to find this in a question", do you mean it is a homework question? $\endgroup$ – Asaf Karagila Nov 25 '11 at 20:02
  • $\begingroup$ @1 yes i mean union $\endgroup$ – user13791 Nov 25 '11 at 20:04
  • $\begingroup$ @2 this is not my homework question, but my homework question requires this. $\endgroup$ – user13791 Nov 25 '11 at 20:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Nov 25 '11 at 20:05
7
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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$, ..." $\endgroup$ – Austin Mohr Nov 25 '11 at 20:14
1
$\begingroup$

Spoiler:

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Asaf Karagila Nov 25 '11 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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