3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your approach only works if A and B are disjoint. Replace A by A-B. $\endgroup$ – Rene Schipperus Jan 25 '17 at 1:09
  • 2
    $\begingroup$ In case you are familiar with the other common set notations, I'll elaborate on Rene's answer. 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$. $\endgroup$ – The Count Jan 25 '17 at 1:13
  • $\begingroup$ @TheCount: Thank you for the help. I have made an edit to my post. Does it logically follow, or have I missed something? $\endgroup$ – infinitylord Jan 25 '17 at 1:49
  • $\begingroup$ Looks pretty good to me. To avoid having this be an unanswered question, I will make my comment into an answer. $\endgroup$ – The Count Jan 25 '17 at 2:09
  • $\begingroup$ I would just like to add that $A-B$ may be empty and then the conclusion follows trivially. $\endgroup$ – CantorStudent Feb 19 '17 at 22:24
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

For a slightly different approach: you say 'For $C$ to be countably infinite, we need to find a bijection between $C$ and the natural numbers.' This isn't strictly speaking true; you just need to show that a bijection exists.

The most straightforward way of doing that in this case is probably to use the Cantor-Schröder-Bernstein theorem which states that if there is an injection from $X$ to $Y$ and an injection from $Y$ to $X$, then there's a bijection between $X$ and $Y$. Your original construction (inverted) shows an injection from $A\cup B$ to $\mathbb{N}$, and the countability of $A$ provides an injection from $\mathbb{N}$ to $A\cup B$ (why?), so you can infer the bijection you're looking for.

$\endgroup$

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.