Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Indexed Union of Countably Infinite Sets

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by lfroehli View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    12
    So then the infinite part is negligible?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by lfroehli View Post
    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}^+.
    Last edited by Plato; March 21st 2011 at 03:41 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2011
    Posts
    12
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Quote Originally Posted by lfroehli View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by lfroehli View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by lfroehli View Post
    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 m,n)\mapsto 2^{2m-1}(2n-1)" alt="\Psim,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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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").
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by MoeBlee View Post
    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}^+.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752
    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).
    Last edited by Deveno; March 25th 2011 at 09:45 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by Deveno View Post
    \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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752
    Quote Originally Posted by MoeBlee View Post
    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.....
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Intersection of two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2011, 06:30 PM
  2. Union of Two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2011, 06:25 PM
  3. countably infinite / uncountable sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 9th 2010, 12:18 PM
  4. Replies: 20
    Last Post: October 15th 2008, 10:30 AM

Search Tags


/mathhelpforum @mathhelpforum