# Thread: Union of Countable Sets

1. ## Union of Countable Sets

Show that a countable union of countable sets is countable (take countable to mean either finite or countably infinite).

So I can see four cases:

Finite union of finite sets - this is easily proven to be countable

Countably infinite union of countably infinite sets - I've proved this by constructing a bijection to $\displaystyle \mathbb{N}$ x $\displaystyle \mathbb{N}$

Finite union of countably infinite sets - subset of the above, hence countable as well

Countably infinite union of finite sets - the last one is the one I'm having problem with.
The hint I got was to use Schröder-Bernstein's theorem, but I'm having trouble constructing two injections for the required bijections.

Thanks in advance for any help!

2. List the terms in the sets in the order they are decribed, i.e if we have a union of the sets A_n for each n in N, list the terms in the same order, i.e:
all the objects of A_1 first, second A_2 and so forth, the list must be countable cause you can count them.

If you want a more rigorous way, then the define the function:
f(j,i)=a_ij where a_ij in A_i, this is bijection from NxN->UA_n
the j represent the place of a_ij in A_i, ofcourse I assume there's some order you can invent on each set because they are finite sets.

3. How would you construct a bijection from the countably infinite union of finite sets to $\displaystyle \mathbb{N}$ x $\displaystyle \mathbb{N}$? Since the sets are all finite, wouldn't there be a problem here?

4. Hello,

Let $\displaystyle E_n$ be the countable sets.
Let $\displaystyle E=\bigcup_{n \in \mathbb{N}} E_n$

We know that there exist injective functions :
$\displaystyle \forall n \in \mathbb{N},~ \exists \varphi_n ~:~ E_n \to \mathbb{N}$, because $\displaystyle E_n$ is countable.
Now you have to find an injective function from E to $\displaystyle \mathbb{N}$

$\displaystyle \forall x \in E, ~ \exists n \text{ such that } x \in E_n$, by definition of a union.
Let $\displaystyle N(x)=\min \{n ~:~ x \in E_n\}$, for $\displaystyle x \in E$

Define $\displaystyle \phi ~:~ E \to \mathbb{N}^2$, $\displaystyle x \mapsto \left(N(x),\varphi_{N(x)}(x)\right)$

$\displaystyle \blacksquare$ : proof that $\displaystyle \phi$ is injective.
$\displaystyle \forall x,y \in E$, if $\displaystyle \phi(x)=\phi(y)$ then :
$\displaystyle \left\{\begin{array}{ll} N(x)=N(y) \quad (=k) \\ \varphi_k(x)=\varphi_k(y) \end{array}\right.$
Since $\displaystyle \varphi_k$ is injective, we can conclude that $\displaystyle x=y$
So $\displaystyle \phi$ is injective.
$\displaystyle \blacksquare$

But we know that since $\displaystyle \mathbb{N}^2$ is countable, there exists an injective mapping $\displaystyle \psi$ from $\displaystyle \mathbb{N}^2 \to \mathbb{N}$

$\displaystyle E \stackrel{\phi}{\longrightarrow} \mathbb{N}^2 \stackrel{\psi}{\longrightarrow} \mathbb{N}$

$\displaystyle \psi \circ \phi$ is injective as a composition of two injective functions.
So E is countable.

5. If we only had to construct a bijection from the union to N, we could use the function phi that you constructed alone, is that correct?
And also, when you prove there is an injection from E to N, do you have to prove there is a bijection or can you conclude automatically that E is countable?

6. Originally Posted by HiLine
If we only had to construct a bijection from the union to N, we could use the function phi that you constructed alone, is that correct?
Hmmm, no, I don't think so.
And the union is not necessarily in bijection with N. We know it's countable, but we don't know if it has the same cardinal as N (bijection)

And also, when you prove there is an injection from E to N, do you have to prove there is a bijection or can you conclude automatically that E is countable?
You can automatically conclude that E is countable with injective functions, which is why you don't have to bother with bijections (I find injections easier to deal with than bijections...)

Moreover, E_n is countable means that there exists an injection from E_n to N, not that there exists a bijection.
It's more general, since a bijection is an injection.

It's a messy explanation, but I hope it helps you...

7. It is not hard to show that $\displaystyle \varphi :\mathbb{Z}^ + \times \mathbb{Z}^ + \mapsto \mathbb{Z}^ + ,~\varphi (m,n) = \left( {2^{m - 1} } \right)\left( {2n - 1} \right)$ is a bijection.

8. Originally Posted by Moo
Hmmm, no, I don't think so.
Then if you were to construct a direct injection from E to N, not through NxN, what function would you construct?

Originally Posted by Moo
And the union is not necessarily in bijection with N. We know it's countable, but we don't know if it has the same cardinal as N (bijection)

You can automatically conclude that E is countable with injective functions, which is why you don't have to bother with bijections (I find injections easier to deal with than bijections...)

Moreover, E_n is countable means that there exists an injection from E_n to N, not that there exists a bijection.
It's more general, since a bijection is an injection.

It's a messy explanation, but I hope it helps you...
Oh I thought a countable set had to have the same cardinality as N. In fact it only has to have the same cardinality as a subset of N. Thanks a lot!

Originally Posted by Plato
It is not hard to show that $\displaystyle \varphi :\mathbb{Z}^ + \times \mathbb{Z}^ + \mapsto \mathbb{Z}^ + ,~\varphi (m,n) = \left( {2^{m - 1} } \right)\left( {2n - 1} \right)$ is a bijection.
That's a useful function. Thanks!

9. Originally Posted by HiLine
Oh I thought a countable set had to have the same cardinality as N. In fact it only has to have the same cardinality as a subset of N.
In fact, it is sufficient to find an injection $\displaystyle f:A \mapsto \mathbb{Z}^ +$ in order to prove that $\displaystyle A$ is countable.

10. Originally Posted by Plato
In fact, it is sufficient to find an injection $\displaystyle f:A \mapsto \mathbb{Z}^ +$ in order to prove that $\displaystyle A$ is countable.
If there is such an injection, we will have a bijection from A to the image of A, which is a subset of Z+.