Let $A, B$ be countably infinite sets. Prove that the union of $A$ and $B$ is also countably infinite.
I'm aware that this question already exists on stack exchange, but I'm trying it a different way and am having difficulty finishing it.
Let the union of $A$ and $B$ be denoted by $C$. For $C$ to be countably infinite, we need to find a bijection between $C$ and the natural numbers. Let $f(n)$ be the bijective function mapping the natural numbers to $A$, and $g(n)$ be the bijective function mapping the natural numbers to $B$. Define $h(n)$ to be the function mapping the natural numbers to $C$ given by:
$$h(2n) = f(n)$$
$$h(2n-1) = g(n)$$
To show that $h(n)$ is bijective, we need to show that it is both surjective and injective. I was able to do the surjective part without problem, but am having trouble proving injectivity.
Attempt:
if $n_1, n_2$ are even, then $n_j = 2k_j$ for some other natural numbers $k_j$. Thus,
$$h(2k_1) = h(2k_2)$$
$$f(k_1) = f(k_2)$$
$$k_1 = k_2$$
since $f(n)$ is bijective. Simlarly, if $n_1, n_2$ are odd, then $n_j = 2k_j – 1$ for some natural numbers $k_j$. So,
$$h(2k_1 – 1) = h(2k_2 – 1)$$
$$g(k_1) = g(k_2)$$
$$k_1 = k_2$$
since $g(n)$ is bijective. However, we could also have the case that $n_1$ is even and $n_2$ is odd. Then,
$$h(n_1) = h(n_2)$$
$$h(2k_1) = h(2k_2 – 1)$$
$$f(k_1) = g(k_2)$$
this is where I get stuck. If I can show this, I've shown that $h(n)$ is injective, and in turn, bijective. For reference, this site uses a very similar technique, but seems to completely disregard injectivity for some reason.
http://planetmath.org/unionofcountablesets
EDIT:
Let $A' = A \text{\ } B$. It is clear that $A' \cup B = A \cup B$, as:
if $c \in A' \cup B$, then $c \in A'$ or $c \in B$. If $c \in B$, then $c \in A \cup B$. If $c \in A'$, then, by definition, $c \in A$, so that $c \in A \cup B$.
It is also clear that $A'$ must be a countable set, as $A$ is countable and $A'$ has, at most, the same number of elements as $A$. If $A'$ is finite, then $A' \cup B$ is countably infinite, as we have added only a finite number of elements to $B$ (is this obvious enough to take as fact without proof?). If $A'$ is countably infinite, then redefine $f(n)$ to be a bijective function from natural numbers to $A'$. The cases of surjectivity and injectivity above are unchanged. Now, if $$f(k_1) = g(k_2)$$ we have that for some $a \in A'$ and $b \in B$, $a = b$. This contradicts the fact that $A'$ and $B$ are disjoint, so we must have that $h(2k_1) \ne h(2k_2 – 1)$ for any natural numbers $k_j$. Therefore, $h(n)$ is bijective. QED.
Best Answer
Here's a hint:
In case you are familiar with the other common set notations, I'll elaborate on Rene's comment, to get you started. Since $A$ and $B$ are countable, then $A\backslash B$ is either finite or countable and is disjoint to $B$. Show that $B\cup(A\backslash B)$ is countable, and then note that this set is identically equal to $A\cup B$.