# Check proof of union of denumerable sets is denumerable too

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.

• When getting acquainted with the subject, one may want to show very soon that the existence of a surjection is enough when the set is infinite--then your function $h$ is enough to prove the claim. – Did Sep 1 '14 at 19:32
• I prefer to go from $A\cup B$ to $\mathbb{Z}^+$. Use the inverse of your procedure to deal with any $a\in A$. Also to deal with any $b\in B\setminus A$. This gives a bijection to an infinite subset of $\mathbb{Z}^+$. Then map this infinite subset bijectively to $\mathbb{Z}^+$ by sending the $n$-th element to $n$. – André Nicolas Sep 1 '14 at 19:49

Suppose that both $$A$$ and $$B$$ are not the empty set. Let $$f:\mathbb{N}\rightarrow A$$ and $$g:\mathbb{N}\rightarrow B$$ be ennumerations of $$A$$ and $$B$$; that is, $$f$$ and $$g$$ are surjective functions from $$\mathbb{N}$$ onto $$A$$ and $$B$$, respectively. The function $$h:\mathbb{N}\rightarrow A\cup B$$ defined by: for each $$n\in\mathbb{N}$$
$$h(n)=\begin{cases} f(k)\quad\text{if }n=2k\\ g(k)\quad\text{if }n=2k+1 \end{cases}$$
This proof is valid even when $$A\cap B\not=\varnothing$$; a point in their intersection might have several preimages, but as well as any other element in $$A$$ or $$B$$. There is no problem with the definition of $$h$$, and I think it is clear that $$h$$ is surjective.