Results 1 to 6 of 6

Math Help - countable union of sets

  1. #1
    Junior Member
    Joined
    Oct 2007
    From
    Nova Scotia
    Posts
    48

    countable union of sets

    We're given n surjections fn= : {1,2,...,N} -> En. for all n in the Natural Numbers.
    We have to prove that E= the union of all En is countable by defining a surjection from the natural numbers to the union of sets.

    Since all the En have at most N elements, could I just define my surjection from {1,2,...,nN} and my function would be
    F(i)={i for i in E
    {s0 for i not in E
    where so is a fixed element in E

    E here could cover all of the Natural Numbers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by frankdent1 View Post
    We're given n surjections fn= : {1,2,...,N} -> En. for all n in the Natural Numbers.
    We have to prove that E= the union of all En is countable by defining a surjection from the natural numbers to the union of sets.

    Since all the En have at most N elements, could I just define my surjection from {1,2,...,nN} and my function would be
    F(i)={i for i in E
    {s0 for i not in E
    where so is a fixed element in E

    E here could cover all of the Natural Numbers.
    Given a natural number k, let n be the quotient and r the remainder when k is divided by N. So k=nN+r, with 0≤r<N. Define F by F(k) = f_n(r+1). Then as k goes from nN to nN+(N-1), F(k) will go through all the values of f_n. Therefore the range of F (as k goes through all the natural numbers) will be the union of the sets E_n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2007
    From
    Nova Scotia
    Posts
    48
    Quote Originally Posted by Opalg View Post
    Given a natural number k, let n be the quotient and r the remainder when k is divided by N. So k=nN+r, with 0≤r<N. Define F by F(k) = f_n(r+1). Then as k goes from nN to nN+(N-1), F(k) will go through all the values of f_n. Therefore the range of F (as k goes through all the natural numbers) will be the union of the sets E_n.
    So what happends when k goes from 1 to N-1. for k=1, n=0 and r=1 meaning f_k = f_0 (2). Shouldn't we be starting from f_1 (1) since i'm using the functions f_n ={ i for i in E_n
    {s0 fixed for i not in E_n
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by frankdent1 View Post
    So what happens when k goes from 1 to N-1. for k=1, n=0 and r=1 meaning f_k = f_0 (2). Shouldn't we be starting from f_1 (1) since i'm using the functions f_n ={ i for i in E_n
    {s0 fixed for i not in E_n
    You're right, the numbers don't quite match up at the start of the sequence. Try this modification: Given a natural number k, let n be the quotient and r the remainder when k-1 is divided by N. So k=nN+(r+1), with 0≤r<N. Now define F as before by F(k) = f_n(r+1).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2007
    From
    Nova Scotia
    Posts
    48
    Quote Originally Posted by Opalg View Post
    You're right, the numbers don't quite match up at the start of the sequence. Try this modification: Given a natural number k, let n be the quotient and r the remainder when k-1 is divided by N. So k=nN+(r+1), with 0≤r<N. Now define F as before by F(k) = f_n(r+1).
    This makes sense only if we use F(k) = f_n+1 (r+1)
    Because when k=1, r=0 and n=0 so we would use F(1) = f_0 (1). but f_0 is not defined, it should be f_1

    Am I right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by frankdent1 View Post
    This makes sense only if we use F(k) = f_n+1 (r+1)
    Because when k=1, r=0 and n=0 so we would use F(1) = f_0 (1). but f_0 is not defined, it should be f_1

    Am I right?
    Yes, I think that finally nails it.
    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, 03: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, 02:59 PM
  3. analysis help (countable union of disjoint sets)
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 30th 2010, 06:40 PM
  4. Real Analysis: Union of Countable Infinite Sets Proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 14th 2010, 06:38 PM
  5. Union of Countable Sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 28th 2009, 08:31 AM

Search Tags


/mathhelpforum @mathhelpforum