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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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


Can you count their elements?

share|cite|improve this answer

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|cite|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

Your Answer


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.