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.

  • $\begingroup$ 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. $\endgroup$ – Did Sep 1 '14 at 19:32
  • $\begingroup$ 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$. $\endgroup$ – 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.


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.