I need to prove:
If $A$ and $B$ are denumerable sets then so is their union $A\cup B$.
In this case, denumerable is defined as:
A set $X$ is said to be denumerable if there is a bijection $\mathbb{Z}^+\rightarrow X$.
My attempt:
$A \text{ denumerable } \implies f:\mathbb{Z^+} \rightarrow A$
$B \text{ denumerable } \implies g:\mathbb{Z^+} \rightarrow B$
I need to construct a bijective function, $h:\mathbb{Z}^+\rightarrow A\cup B$.
So, define $h$:
$h(i)=\left\{ \begin{align}
& f(n+1), & \text{ if } i=2n+1, \text{ for } n \in \{0,1,2,\dots\} \\
& g(n), & \text{ if } i=2n, \text{ for } n \in \{ 1,2,3,\dots\}
\end{align} \right.$
Then, $h$ is bijective because both $f$ and $g$ are bijective by definition.
Hence, $A \cup B$ is denumerable, as required.
However, this only works if $A$ and $B$ are disjoint.
So, in the case that $A$ and $B$ are not disjoint:
$A\cup B = A \cup (B-A)$ and $A \cap (B-A) = \emptyset$
I'm not sure what to do next.
If I can show that $B-A$ is denumerable, then I can use the above workings to conclude that $A\cup B$ is denumerable too. So I will attempt to construct a bijection $\mathbb{Z}^+\rightarrow B-A$:
I know that $(B-A)\subset B$, so, there exists an inclusion function $i:(B-A)\rightarrow B$, which is an injection. I thought of $g^{-1}\circ i$ but that's just an injection $(B-A) \rightarrow \mathbb{Z^+}$.
How can I build the required bijection ? I also would like to seek feedback if there are other parts of my work that could be written better.
Best Answer
Starting with two bijections,
$\quad f:\mathbb{Z^+} \rightarrow A, \; g:\mathbb{Z^+} \rightarrow B$
we can use recursion to define a function $h:\mathbb{Z^+} \rightarrow A \cup B$ as follows:
Set $h(1) = f(1)$.
Assume $h$ has been defined on the segment $[1,n)$ with $n \ge 2$ and define $$ h(n)=\begin{cases} f\bigr(\,\text{min}(\,f^{-1}\text{<}A \setminus h[1,n)\,\text{>})\,\bigr)\quad\text{if }n \text{ is odd}\\ g\bigr(\,\text{min}(\,g^{-1}\text{<}B \setminus h[1,n)\,\text{>})\,\bigr)\quad\text{if }n \text{ is even}\\ \end{cases} $$
So by recursive definition we've specified our function $h:\mathbb{Z^+} \rightarrow A \cup B$.
One can use induction to show that $h$ is injective.
One can use induction to show that the range of $h$ includes $A$.
One can use induction to show that the range of $h$ includes $B$.
So $h$ is a bijection.