# Prove that the union of two disjoint countable sets is countable

This is a question from my proofs course review list that I have had trouble understanding.

I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove a set is countable and furthermore, that the union of two countable sets is countable.

Please help me get started with the question by understanding this concept.

• – 6005 May 3 '14 at 20:16
• You should probably be aware of what a countable set is. (Did you forget it ?) A countable set is just a set such that you can count its elements. Obvious for finite sets. For infinite sets, the trick is to establish a bijection between the set and $N$ (naturals). – Yves Daoust May 3 '14 at 20:18
• Actually you just need an injective function from the set to $\Bbb N$ – Ellya May 3 '14 at 20:23
• Here is the solution I had sent to me by peers: A: f : A->Z (one to one) B: g : B->Z (one to one) f x g = A x B = Z x Z = one to one = countable Can someone decipher this for me? – user122661 May 3 '14 at 20:26

## 3 Answers

A formal proof would be something like this. If $A$ and $B$ are countable (and disjoint) sets, then there exist injective functions $f$ and $g$ from $A$ and $B$, respectively, to $\mathbb{N}$. Let $C=A\cup B$ and define a function $h:C\rightarrow\mathbb{N}$ as follows:

$$h(z) = \begin{cases}2f(z) & \text{if } z\in A\\ 2g(z)+1 & \text{if } z\in B\end{cases}$$

Then, if $x\neq y$, we clearly have $h(x)\neq h(y)$ since if $x,y\in A$ this follows from the fact that $f$ is injective (analogously for $x,y\in B$) and if $x\in A$ and $y\in B$, we have that $h(x)$ is even while $h(y)$ is odd (analogously for $x\in B$, $y\in A$). Hence $h$ is an injective function from $C$ to $\mathbb{N}$ and thus, by definition, $C$ is countable.

(In the following, countable means what is often referred to as countably infinite, i.e. countable and not finite)

A set $A$ is called countable if there exists a bijection $f$ between $A$ and the set of natural numbers $\mathbb{N}$. In other words, $A$ is countable if there is some mapping $f \,:\, A \to \mathbb{N}$ such that $f$ hits every element of $\mathbb{N}$ exactly once. Note that any such $f$ has a uniquely defined inverse $f^{-1}$.

It follows that there exists a bijection $f_{A,B}$ between any two countable sets $A$ and $B$, because if $f_A$ is a bijection from $A$ to $\mathbb{N}$, and $f_b$ a bijection from $B$ to $\mathbb{N}$, then $x \mapsto f_B^{-1}(f_A(x))$ is a bijection from $A$ to $B$.

Therefore, to show that the union of two arbitrary disjoint countable sets is countable, it suffices to show that the union of two specific disjoint countable sets $A,B$ is countable. This works because if $X,Y$ are disjoint and countable, by the above there are bijections $f_X \,:\, X \to A$, $f_Y \,:\, Y \to B$, and a bijection $g \,:\, A \cup B \to \mathbb{N}$. We can therefore define a biection from $f \,:\, X \cup Y$ to $\mathbb{N}$ by setting $$f(z) = \begin{cases} g(f_X(z)) &\text{if z \in X,} \\ g(f_Y(z)) &\text{if z \in Y.} \end{cases}$$ (I leave the proof that this actually is a bijection to you)

Since we can view $\mathbb{Z}$ as the disjoint union of $\mathbb{N} = \{0,1,\ldots\}$ and $\mathbb{Z} \setminus \mathbb{N} = \{\ldots,-2,-1\}$, it therefore suffices to

1. show that $\mathbb{Z} \setminus \mathbb{N}$ is countable, i.e. to find a bijection between $\{\ldots,-2,-1\}$ and $\{0,1,\ldots\}$, and

2. show that $\mathbb{Z}$ is countable.

• By the way, the standard definition of countable also encompasses finite sets. – mathse May 3 '14 at 21:40
• @mathse I hate the standard definition then ;-) But you're right, I should point out that my use of countable is what is often called "countably infinite". Will fix. – fgp May 3 '14 at 21:42

There are many ways to prove that set is countable. But the basic method is - enumerate it with some formula.

For example, two disjoint sets

$$A = \{2n-1\mid n-natural\}$$ $$B = \{2n\mid n-integer\}$$ enumerate it $$A_i=2i-1, i>0$$ $$B_i=2i$$ $A,B$ is countable. I say "$C = A\cup B$ is countable too". Formula will be not so simple as it was before, but it exist and easy to write.

$$C_i=\begin{cases} {i,i\gt0} \\{2i,i\le0}\end{cases}$$

Prove that every pair of disjoint countable sets gives another countable set in union.

• This is a funny answer. How does it answer the question, though? It seems like your answer discusses a specific example (in an "odd" way, though) and then rephrases what the OP asks for. – mathse May 3 '14 at 21:47
• @mathse I think specific examples usually helps for "understanding this concept". Anyway - those who read formulas with smile is my friends for life) – Ralor May 4 '14 at 4:12
• Yes, your approach is funny and if it were to be a proof of the proposition in question, I would give it zero points. – mathse May 4 '14 at 7:54
• @mathse I think you should give me zero points at least twice, because your answer seem to use the same idea. But you gave a solution, and I've tried to explain the concept (I wasn't able to give a solution like yours :D) – Ralor May 4 '14 at 8:09
• @Ralor You only gave a single example. Examples cannot replace proofs. – user144248 May 4 '14 at 10:08