Results 1 to 10 of 10

Math Help - Union of Countable Sets

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    123

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

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    56
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    123
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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.
    Last edited by Moo; January 22nd 2009 at 11:52 PM.
    Follow Math Help Forum on Facebook and Google+

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

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by HiLine View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2009
    Posts
    13

    Thumbs up

    Quote Originally Posted by Moo View Post
    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 View Post
    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 View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

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

  10. #10
    Newbie
    Joined
    Apr 2009
    Posts
    13

    Wink

    Quote Originally Posted by Plato View Post
    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+.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Countable Union/Intersection of Open/Closed sets
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: November 4th 2010, 02:11 PM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. analysis help (countable union of disjoint sets)
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 30th 2010, 05:40 PM
  4. Real Analysis: Union of Countable Infinite Sets Proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 14th 2010, 05:38 PM
  5. countable union of sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 28th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum