Results 1 to 9 of 9

Math Help - pairwise disjoint subset question

  1. #1
    Senior Member
    Joined
    Jan 2010
    Posts
    273

    pairwise disjoint subset question

    A) Show that N contains infinitely many pairwise disjoint infinite subsets. [Hint: It was shown that N~ Nx N


    what is a pairwise disjoint infinite subset, can someone provide the definition of it?



    B) Prove that any infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: pairwise disjoint subset question

    Quote Originally Posted by wopashui View Post
    A) Show that N contains infinitely many pairwise disjoint infinite subsets. [Hint: It was shown that N~ Nx N


    what is a pairwise disjoint infinite subset, can someone provide the definition of it?



    B) Prove that any infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets.
    The basic idea is as was stated to you. If X is infinite then X is equipotent to X\times X, say that f:X\times X\to X is the bijection. We then have that \left\{\{x\}\times X\right\}_{x\in X} is an infinite collection of pairwise disjoint sets in X\times X, thus \left\{f(X\times\{x\})\right\}_{x\in X} is an infinite collection of pairwise disjoint subsets of X.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: pairwise disjoint subset question

    to answer the original poster, a pair-wise disjoint collection of sets is a family \{A_j\}_{j \in J} of sets such that:

    A_i \cap A_j \neq \emptyset \implies A_i = A_j\  \forall i,j \in J
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2010
    Posts
    273

    Re: pairwise disjoint subset question

    Quote Originally Posted by Deveno View Post
    to answer the original poster, a pair-wise disjoint collection of sets is a family \{A_j\}_{j \in J} of sets such that:

    A_i \cap A_j \neq \emptyset \implies A_i = A_j\  \forall i,j \in J
    so is this just mean a union of infinite many mutually exclusive sets?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2010
    Posts
    273

    Re: pairwise disjoint subset question

    Quote Originally Posted by Drexel28 View Post
    The basic idea is as was stated to you. If X is infinite then X is equipotent to X\times X, say that f:X\times X\to X is the bijection. We then have that \left\{\{x\}\times X\right\}_{x\in X} is an infinite collection of pairwise disjoint sets in X\times X, thus \left\{f(X\times\{x\})\right\}_{x\in X} is an infinite collection of pairwise disjoint subsets of X.
    this approach seems to work for both question, I do not understand the difference of part A and B? Need some explainations please!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: pairwise disjoint subset question

    Quote Originally Posted by wopashui View Post
    this approach seems to work for both question, I do not understand the difference of part A and B? Need some explainations please!
    In my example there is no need for the union to be countable. Give us an idea how to the second part, a little effort would be nice.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2010
    Posts
    273

    Re: pairwise disjoint subset question

    Quote Originally Posted by Drexel28 View Post
    In my example there is no need for the union to be countable. Give us an idea how to the second part, a little effort would be nice.
    for B) if S is an infinite set, we have 2 cases, S can be uncountable or countably infinite, if S uncountable, this is not possible, so we need to show that S is countable
    since S is infinite, then we have  f:N-->S , f is injective, so if we show that f is also a surjection, we have f is a bijectiion, i.e.  N~S . i.e we need to show that for all  s\in S there exisis  n_s\in N  s.tf(n_s)=s

    If we have f is a bijection, then by part A, we have part B

    so how can I do this?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,786
    Thanks
    1683
    Awards
    1

    Re: pairwise disjoint subset question

    Quote Originally Posted by wopashui View Post
    for B) if S is an infinite set, we have 2 cases, S can be uncountable or countably infinite, if S uncountable, this is not possible, so we need to show that S is countable?
    It is not necessary to consider cases to prove part B.
    If S is infinite then there is a countable subset T\subset S.
    Moreover, there is surjection f:S\to T.
    Then \left\{ {f^{ - 1} \left( {\{ x\} } \right):x \in T} \right\} is pairwise disjoint countable collection and S = \bigcup\limits_{x \in T} {f^{ - 1} \left( {\{ x\} } \right)} .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2010
    Posts
    273

    Re: pairwise disjoint subset question

    Hi, Plato, I don't understand what  f^{-1} comes from, and can a uncountable set has a countable subset, so if S is uncountable, can T be countable? Do I need part A to show part B?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 15th 2011, 09:13 PM
  2. collection of pairwise disjoint interval question
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: October 11th 2011, 07:35 PM
  3. subset question
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: October 4th 2011, 03:05 AM
  4. [SOLVED] Set related question ... find out if disjoint of not disjoint ...
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 9th 2011, 02:26 AM
  5. Proof on Openness of a Subset and a Function of This Subset
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 24th 2010, 09:04 PM

Search Tags


/mathhelpforum @mathhelpforum