# Indexed Union of Countably Infinite Sets

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Mar 21st 2011, 12:34 PM
lfroehli
Indexed Union of Countably Infinite Sets
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.
• Mar 21st 2011, 12:41 PM
Plato
Quote:

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.
• Mar 21st 2011, 02:55 PM
lfroehli
So then the infinite part is negligible?
• Mar 21st 2011, 03:02 PM
Plato
Quote:

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}^+$.
• Mar 22nd 2011, 05:14 PM
lfroehli
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?
• Mar 23rd 2011, 07:03 AM
emakarov
Quote:

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.

Quote:

or find a bijective function from the domain to the codomain.
Every function is from the domain to the codomain. (Bigsmile) You probably mean from the set to a proper subset. Again, this would mean that the set is infinite, but not necessarily countable.

Quote:

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.
• Mar 23rd 2011, 07:07 AM
MoeBlee
Quote:

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.
• Mar 23rd 2011, 08:19 AM
Plato
Quote:

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:(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.
• Mar 23rd 2011, 08:42 AM
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").
• Mar 23rd 2011, 08:58 AM
Plato
Quote:

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}^+$.
• Mar 25th 2011, 09:18 AM
Deveno
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).
• Mar 25th 2011, 10:54 AM
Plato
Quote:

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.
• Mar 26th 2011, 11:42 AM
Deveno
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.
• Mar 28th 2011, 09:55 AM
MoeBlee
Quote:

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.
• Apr 1st 2011, 06:37 PM
Deveno
Quote:

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.....
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last