# Union of Two countably infinite sets

• Mar 22nd 2011, 06:15 PM
andirc5192
Union of Two countably infinite sets
If A and B are both countably infinite then prove that $A\bigcup B$ is countably inifinite.

I was working on this problem with a friend and we know that this means that there is a bijection of both sets, but where do we go from there?
• Mar 22nd 2011, 06:25 PM
TheEmptySet
Quote:

Originally Posted by andirc5192
If A and B are both countably infinite then prove that $A\bigcup B$ is countably inifinite.

I was working on this problem with a friend and we know that this means that there is a bijection of both sets, but where do we go from there?

Since A and B are both countable we know that there exists a bijection from the integers to the sets.

Let $A = \{a_1,a_2,a_3, \cdots$ and
Let $B = \{b_1,b_2,b_3, \cdots$

let $f:A \to \mathbb{N} \quad f(a_i)=i$ and
let $g:B \to \mathbb{N} \quad f(b_i)=i$

Now let $h:A \cup B \to \mathbb{N}$

$h(x)=\begin{cases}2i-1, \text{if } x \in A \\ 2i, \text{if } x \in B \end{cases}$

Now show that this is both 1-1 and onto