# Union of Countable Sets

• Jan 21st 2009, 09:01 PM
h2osprey
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!
• Jan 22nd 2009, 12:34 AM
InvisibleMan
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.
• Jan 22nd 2009, 05:16 AM
h2osprey
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?
• Jan 22nd 2009, 11:38 PM
Moo
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.
• Apr 27th 2009, 09:31 PM
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?
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?
• Apr 28th 2009, 01:11 AM
Moo
Quote:

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)

Quote:

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...
• Apr 28th 2009, 02:58 AM
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.
• Apr 28th 2009, 06:59 AM
HiLine
Quote:

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?

Quote:

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!

Quote:

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!
• Apr 28th 2009, 07:15 AM
Plato
Quote:

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.
• Apr 28th 2009, 07:31 AM
HiLine
Quote:

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+. :)