I have a statement here I wish to prove and I would love some help on it 🙂
If $A$ and $B$ are denumerable sets, and $C$ is a finite set, then $A \cup B \cup C$ is denumerable
Here is my thoughts!
Since $A$ and $B$ are denumerable (countably infinite), then certainly we can write them as $A$ = {$a1, a2, a3…$} and we can also write $B$ as $B$ = {$b1, b2, b3…$}. My proof strategy is to prove that $A \cup B$ is denumerable and name it set $X$. Then I will proceed to demonstrate that $X \cup C$ where $C$ is finite is denumerable. Is this a valid approach?
Here I go!
The union of two denumerable sets are certainly denumerable as we can pair them off like this: {$(a1,b1), (a1,b2, (a1,b3) … (a2,b1), (a2,b2) ….$}. We can also come up with a bijective function $f$ from $A$ to $B$ but I am not sure on how to do that! We can call the union of sets $A$ and $B$ $X$.
Anyway, so now all we have to do is prove that the $X \cup C$ is denumerable and prove that correct?
Help would be appreciated! I feel as though my professor wouldn't give me full marks as this proof is very informal unfortunately! Anything I can do?
Thanks 🙂
Best Answer
You could do it all at once, but there’s nothing wrong with the idea of first proving that $X=A\cup B$ is countably infinite and then going on to prove that $X\cup C$ is as well. However, you’re off on the wrong foot in trying to prove that $X$ is countably infinite. Pairing up $A$ and $B$ isn’t going to help: what you need to do is pair up $A\cup B$ and $\Bbb Z^+$.
Writing $A=\{a_1,a_2,a_3,\dots\}=\{a_n:n\in\Bbb Z^+\}$ and $B=\{b_1,b_2,b_3,\dots\}=\{b_n:n\in\Bbb Z^+\}$ is a good start. Now let $X=A\cup B$. Informally you have $X=\{a_1,b_1,a_2,b_2,a_3,b_3\dots\}$, and it’s intuitive clear that this can be paired up with $\Bbb Z^+$:
$$\begin{array}{cc} 1&2&3&4&5&6&7&8&9&10&\dots\\ a_1&b_1&a_2&b_2&a_3&b_3&a_4&b_4&a_5&b_5&\dots \end{array}$$
The problem is to express this clearly enough so that if someone asks what $55$ corresponds to, you can actually answer. If you examine the table above closely enough, it’s apparent that even numbers in the top line match up with $b$’s, and odd numbers with $a$’s, and a little more examination reveals the rule: $2n$ matches up with $b_n$, and $2n-1$ matches up with $a_n$. You can now express this as a bijection from $\Bbb Z^+$ to $X$:
$$f(n)=\begin{cases} a_{\frac{n+1}2},&\text{if }n\text{ is odd}\\\\ b_{\frac{n}2},&\text{if }n\text{ is even}\;. \end{cases}$$
Now you need to prove that $X\cup C$ is countably infinite. Since we now know that $X$ is countably infinite, there’s no need to keep the notational baggage of $a_n$’s and $b_n$’s: let $X=\{x_n:n\in\Bbb Z^+\}$ (or, more informally, $\{x_1,x_2,x_3,\dots\}$). If $C=\varnothing$, then $X\cup C=X$ is certainly countably infinite, so we can assume that $C$ is non-empty, say $C=\{c_1,\dots,c_m\}$. Now the easiest way to list $X\cup C$ systematically is $\{c_1,c_2,\dots,c_m,x_1,x_2,x_3,\dots\}$. Lay out the correspondence with $\Bbb Z^+$ as we did above:
$$\begin{array}{cc} 1&2&3&\dots&m&m+1&m+2&m+3&\dots\\ c_1&c_2&c_3&\dots&c_m&x_1&x_2&x_3&\dots \end{array}$$
It’s not too hard not to write down a bijection $g$ from $\Bbb Z^+$ to $X\cup C$:
$$g(n)=\begin{cases} c_n,&\text{if }1\le n\le m\\\\ x_{n-m},&\text{if }n>m\;. \end{cases}$$