Union of Countable Sets

**h2osprey** · January 21st 2009, 09:01 PM

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 $\mathbb{N}$ x $\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!

**InvisibleMan** · January 22nd 2009, 12:34 AM

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.

**h2osprey** · January 22nd 2009, 05:16 AM

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

**Moo** · January 22nd 2009, 11:38 PM

Hello,

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

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

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

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

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

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

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

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

**HiLine** · April 27th 2009, 09:31 PM

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?

**Moo** · April 28th 2009, 01:11 AM

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...

**Plato** · April 28th 2009, 02:58 AM

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

**HiLine** · April 28th 2009, 06:59 AM

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 $\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!

**Plato** · April 28th 2009, 07:15 AM

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 $f:A \mapsto \mathbb{Z}^ +$ in order to prove that $A$ is countable.

**HiLine** · April 28th 2009, 07:31 AM

Originally Posted by Plato

In fact, it is sufficient to find an injection $f:A \mapsto \mathbb{Z}^ +$ in order to prove that $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+.

Thread: Union of Countable Sets

LinkBack

Thread Tools

Display

Union of Countable Sets

Similar Math Help Forum Discussions

Countable Union/Intersection of Open/Closed sets

[SOLVED] Countable union of closed sets/countable interesection of open sets

analysis help (countable union of disjoint sets)

Real Analysis: Union of Countable Infinite Sets Proof

countable union of sets

Search Tags