Indexed Union of Countably Infinite Sets

**lfroehli** · March 21st 2011, 12:34 PM

Prove that if $\Lambda$ is countably infinite and $B_{\lambda}$ is countably infinite for each $\lambda \in \Lambda$ , then $\bigcup_{\lambda \in \Lambda}B_\lambda$ is countably infinite.

I was taught that in order to show that a set is countably infinite, we need to either find a proper subset with the same cardinality, or find a bijective function from the domain to the codomain. However, I'm not sure how to attack this proof; I don't know if I'm supposed to use the above method since I'm not just proving that one set is countably infinite.

**Plato** · March 21st 2011, 12:41 PM

Originally Posted by lfroehli

Prove that if $\Lambda$ is countably infinite and $B_{\lambda}$ is countably infinite for each $\lambda \in \Lambda$ , then $\bigcup_{\lambda \in \Lambda}B_\lambda$ is countably infinite.

This theorem is usually stated as: A countable union of countable sets is countable.
If we can find an injection from $\bigcup\limits_\Lambda {B_\lambda } \to \mathbb{Z}^ +$ that is all the this proof requires.

**lfroehli** · March 21st 2011, 02:55 PM

So then the infinite part is negligible?

**Plato** · March 21st 2011, 03:02 PM

Originally Posted by lfroehli

So then the infinite part is negligible?

Actually that given condition would make the proof a lot easier.
You see for each $B_\lambda$ there is a bijection $B_\lambda\leftrightarrow\mathbb{Z}^+$ .

**lfroehli** · March 22nd 2011, 05:14 PM

This seems to be where I always get stuck with proofs that deal with infinite sets. I know that I need to find a bijection, but does that mean that I have to give a specific example of a bijection, or do I just need to somehow show that one exists without specifically giving an example?

**emakarov** · March 23rd 2011, 07:03 AM

Originally Posted by lfroehli

I was taught that in order to show that a set is countably infinite, we need to either find a proper subset with the same cardinality

This would imply that the set is infinite, but not necessarily countable.

or find a bijective function from the domain to the codomain.

Every function is from the domain to the codomain.

You probably mean from the set to a proper subset. Again, this would mean that the set is infinite, but not necessarily countable.

I know that I need to find a bijection, but does that mean that I have to give a specific example of a bijection, or do I just need to somehow show that one exists without specifically giving an example?

Either works unless there are specific directions from your instructor.

See this thread and the Wikipedia article.

**MoeBlee** · March 23rd 2011, 07:07 AM

Originally Posted by lfroehli

does that mean that I have to give a specific example of a bijection [...]?

It depends on what the exercise asks for. Ordinarily, we work in classical mathematics, where to prove existence it is not required to show a specific example. If the exercise asks for you to prove that there exists a bijection, then all you have to do is prove is that there exists a bijection.

However, if the context is constructive mathematics, then any proof of existence requires showing a specific example. But you can pretty much suppose that the context isn't constructive mathematics unless it were explicity stated to be.

**Plato** · March 23rd 2011, 08:19 AM

Originally Posted by lfroehli

does that mean that I have to give a specific example of a bijection, or do I just need to somehow show that one exists without specifically giving an example?

Actually it is a bit of both of those. For each $\lambda\in\Lambda$ there is a bijection $\Phi _\lambda :\mathbb{Z}^ + \leftrightarrow B_\lambda.$

As a lemma: there is a bijection between $Z^+\times Z^+\to Z^+$ define $\Psi<img src=$ m,n)\mapsto 2^{2m-1}(2n-1)" alt="\Psi

m,n)\mapsto 2^{2m-1}(2n-1)" />.
For this question we will use $\Theta=\Psi^{-1}.$

Now if $\displaystyle x\in\bigcup\limits_\Lambda {B_\lambda}$ then $\left( {\exists \eta \in \Lambda } \right)\left( {\exists m \in \mathbb{Z}^ + } \right)\left[ {x = x_{\eta ,m} } \right]$

But also $\Lambda$ is countably infinite there is a bijection
$f:\Lambda \leftrightarrow \mathbb{Z}^ +$

Now we are ready to construct a bijection $\bigcup\limits_\Lambda {B_\lambda } \leftrightarrow \mathbb{Z}^ +$ .

$\Omega: x\mapsto \Theta\left(f(\eta),m\right)$ .
Now it is FUN to show that $\Omega$ is a bijection.

**MoeBlee** · March 23rd 2011, 08:42 AM

Not to dispute that proof, but merely to point out that Phi is a choice function, thus the proof shows existence but does not give a specific example (as you say, it is "a bit of both", perhaps in the sense of "given some choice function, we then define our desired bijection").

**Plato** · March 23rd 2011, 08:58 AM

Originally Posted by MoeBlee

Not to dispute that proof, but merely to point out that Phi is a choice function, thus the proof shows existence but does not give a specific example (as you say, it is "a bit of both", perhaps in the sense of "given some choice function, we then define our desired bijection").

That is of course correct. I trying to get around not dealing with a specific $\Lambda$ .
Actually there maybe more problems than that.
In most analysis textbooks, it is shown that $\displaystyle\bigcup\limits_\Lambda {B_\lambda}$ can be written as the union of pair-wise disjoint sets. Then we construct an injection to $\mathbb{Z}^+$ .

**Deveno** · March 25th 2011, 09:18 AM

as i understand it "all countable sets are set-isomorphic". so to exhibit the bijection in question, what is really needed is a bijection:

$\prod\limits_{\mathbb{Z}^+} {\mathbb{Z}^+} \leftrightarrow \mathbb{Z}^ +$ .

hopefully you can see that the infinite cartersian product has a bijection:

$\prod\limits_{\mathbb{Z}^+} {\mathbb{Z}^+} \leftrightarrow \mathbb{Z}^ + \times \mathbb{Z}^ +$

(send the index to the first coordinate, and the element of the indexed set to the second coordinate)

and that in turn, there is a bijection:

$\mathbb{Z}^ + \times \mathbb{Z}^+ \leftrightarrow \mathbb{Z}^ +$

(Cantor's first diagonal method comes in handy, here, but other bijections are possible).

now, just send an element of the index in the union to its corresponding copy of $\mathbb{Z}$ (send the ith index element to the ith factor) and send the element of each set $B_\lambda$ to its corresponding element of $\mathbb{Z}$

(it's possible that we may wind up sending elements which lie in two or more $B_\lambda$ to multiple elements of $\mathbb{Z}$ , in which case we just keep the first assignment, strike out repetitions, and re-number accordingly).

**Plato** · March 25th 2011, 10:54 AM

Originally Posted by Deveno

$\prod\limits_{\mathbb{Z}^+} {\mathbb{Z}^+} \leftrightarrow \mathbb{Z}^ +$ .

hopefully you can see that the infinite cartersian product has a bijection:

$\prod\limits_{\mathbb{Z}^+} {\mathbb{Z}^+} \leftrightarrow \mathbb{Z}^ += \times \mathbb{Z}^ +$

How are we to understand $\prod\limits_{\mathbb{Z}^+}{\mathbb{Z}^+}~?$ .
Is is it the set of all sequences of positive integers?
That set is uncountable.
In fact the set $2^{Z^+}=\{f:~f:Z^+\to\{0,1\}\}$ is uncountable.

**Deveno** · March 26th 2011, 11:42 AM

oh dear, you are right (Cantor's 2nd diagonal argument works for that just as well as for the real numbers).

in fact, what i meant was what the OP actually posted, i was just trying to get away from an infinite union of copies of Z, which would, of course, just be Z again. so what i should have used was a disjoint union, not the product.

my apologies.

**MoeBlee** · March 28th 2011, 09:55 AM

Originally Posted by Deveno

all countable sets are set-isomorphic

What do you mean by that? An isomorphism involves two structures, not just two sets. Do you mean isomorphic with regard to the the structure <set membership>? Then, no, not all such structures where the sets are countable are isomorphic.

What we do have is that any two denumerable (i.e., countably infinite) sets are equinumerous.

**Deveno** · April 1st 2011, 06:37 PM

Originally Posted by MoeBlee

What do you mean by that? An isomorphism involves two structures, not just two sets. Do you mean isomorphic with regard to the the structure <set membership>? Then, no, not all such structures where the sets are countable are isomorphic.

What we do have is that any two denumerable (i.e., countably infinite) sets are equinumerous.

a set-isomorphism is just a fancy word for bijection. membership induces additional structure on sets (making a poset out of P(X)). "isomorphism" is essentially a categorical notion, not limited just to "sets with structure".

explicitly, if you have a bijection between set A and set B, then saying whether of not A and B are the "same set" depends on your notion of "same". the typical categorical notion is that two sets of the same cardinality are indistiguishable.

i mean, sure the reverse inclusion tower Z-->2Z-->4Z-->8Z--> differs from 2Z-->4Z-->8Z--> in that one has "an extra set", but you have no way of knowing that what is called "two" in the second tower is known by the name "one" in the first tower.

but your answer intrigues me. are you aware of an example of two countably infinte sets with no lattice isomorphism of power sets between them? i'd be interested in seeing it.....

Thread: Indexed Union of Countably Infinite Sets

LinkBack

Thread Tools

Display

Indexed Union of Countably Infinite Sets

Similar Math Help Forum Discussions

Intersection of two countably infinite sets

Union of Two countably infinite sets

countably infinite / uncountable sets

[SOLVED] Finding the union and intersection of indexed sets.

Search Tags