Results 1 to 5 of 5

Math Help - Proof of Union of Power Sets

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    8

    Proof of Union of Power Sets

    Prove that \cup_{i=0}^{k} P_{i}  x P_{k-i}  \rightarrow P_{k}(X \cup Y) is a bijection (For X and Y disjoint sets) defined by (A,B) --> (AUB). (by P_k(X) I mean the power set of X, that is all of the possible subsets of X of cardinality k)

    Deduce that:

     {m+n \choose k} = \sum_{i = 0}^{k} {m \choose i} {n \choose k- i}

    I have what (I think) are the makings of a proof of both parts but I'm really stuck.

    If we take A⊆X and B⊆Y where A∪B ⊆X∪Y. Consider C⊆X∪Y which can be broken up into: C=C∩X+C∩Y since X and Y are disjoint. Then we can then map: f:P(X) P(Y)→P(X∪Y) by f(A,B)= A∪B. Which has inverse f^(-1) (C)=(C∩X,C∩Y). If we look at sets of a particular size: if |A|= i and |B|= k-i then since X and Y are disjoint, and since they are disjoint we know |A∪B|= k We also know that since A is a subset of X and B is a subset of Y and in particular A is a subset of X with cardinality i and B is a subset of Y of cardinality k-i we know that A∈P_i (X) and B∈P_(k-i) (Y).

    Inversely if If we take |C|=k then |C∩X+C∩Y|=k and |C∩X|+|C∩Y|=k. We now consider P_i (X) P_(k-i) (Y)→P_k (X∪Y) as an injection we have to modify the domain for it to be a bijection. Looking at inverse function above with a new cardinality we take f^(-1):P_k (X∪Y)→ \cup_{i=0}^{k}P_i (X) P_(k-i) (Y) 〗 by g(C)=(C∩X),(C∩Y) since this has to map to the union of all of the P_i (X) P_(k-i) (Y)as i varies from 0 to k in order to be well defined (since C∈P_k (X∪Y) and can have cardinalities between 0 and k. And now with a well defined inverse we can amend the domain of the original function such that: ⋃_(i=0)^k〖P_i (X) P_(k-i) (Y)→P_k (X∪Y)〗 by f(A,B)= A∪B as stated in the beginning which is now not just an injection but also a bijection.

    For the second part I have:

    We define ((m+n)k)=|P_k (Z) | where |Z|=m+n in the same vein the right hand side can be re-written: ∑_(i=0)^k: (mi)(n(k-i)) =∑_(i=0)^k〖|P_i (X) ||P_(k-i) (Y)|〗 where |X|=m & |Y|=n. We can rewrite Z=X∪Y so now the problem looks like this: |P_k (X∪Y) |=∑_(i=0)^k▒〖|P_i (X) ||P_(k-i) (Y)|〗. P_k (X∪Y)is the union of all the subsets of (X∪Y) of cardinality k. So the cardinality of that is the number of possible subsets of size k. And I have no idea.

    (Sorry I'm not very good with trying to do math symbols online. To make it easier here's a link to an image of what I wrote: http://pic100.picturetrail.com/VOL71.../383315256.jpg

    It's also attached (Hopefully) I originally wrote it in a .docx file but I can't seem to upload it here anyway...

    Thanks for any help. I'm really quite stuck!
    Attached Thumbnails Attached Thumbnails Proof of Union of Power Sets-math-problem.jpg  
    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
    Quote Originally Posted by jmcq View Post
    Prove that \cup_{i=0}^{k} P_{i}  x P_{k-i}  \rightarrow P_{k}(X \cup Y) is a bijection (For X and Y disjoint sets) defined by (A,B) --> (AUB). (by P_k(X) I mean the power set of X, that is all of the possible subsets of X of cardinality k)

    Deduce that:

     {m+n \choose k} = \sum_{i = 0}^{k} {m \choose i} {n \choose k- i}

    I have what (I think) are the makings of a proof of both parts but I'm really stuck.

    If we take A⊆X and B⊆Y where A∪B ⊆X∪Y. Consider C⊆X∪Y which can be broken up into: C=C∩X+C∩Y since X and Y are disjoint. Then we can then map: f:P(X) P(Y)→P(X∪Y) by f(A,B)= A∪B. Which has inverse f^(-1) (C)=(C∩X,C∩Y). If we look at sets of a particular size: if |A|= i and |B|= k-i then since X and Y are disjoint, and since they are disjoint we know |A∪B|= k We also know that since A is a subset of X and B is a subset of Y and in particular A is a subset of X with cardinality i and B is a subset of Y of cardinality k-i we know that A∈P_i (X) and B∈P_(k-i) (Y).

    Inversely if If we take |C|=k then |C∩X+C∩Y|=k and |C∩X|+|C∩Y|=k. We now consider P_i (X) P_(k-i) (Y)→P_k (X∪Y) as an injection we have to modify the domain for it to be a bijection. Looking at inverse function above with a new cardinality we take f^(-1):P_k (X∪Y)→ \cup_{i=0}^{k}P_i (X) P_(k-i) (Y) 〗 by g(C)=(C∩X),(C∩Y) since this has to map to the union of all of the P_i (X) P_(k-i) (Y)as i varies from 0 to k in order to be well defined (since C∈P_k (X∪Y) and can have cardinalities between 0 and k. And now with a well defined inverse we can amend the domain of the original function such that: ⋃_(i=0)^k〖P_i (X) P_(k-i) (Y)→P_k (X∪Y)〗 by f(A,B)= A∪B as stated in the beginning which is now not just an injection but also a bijection.

    For the second part I have:

    We define ((m+n)k)=|P_k (Z) | where |Z|=m+n in the same vein the right hand side can be re-written: ∑_(i=0)^k: (mi)(n(k-i)) =∑_(i=0)^k〖|P_i (X) ||P_(k-i) (Y)|〗 where |X|=m & |Y|=n. We can rewrite Z=X∪Y so now the problem looks like this: |P_k (X∪Y) |=∑_(i=0)^k▒〖|P_i (X) ||P_(k-i) (Y)|〗. P_k (X∪Y)is the union of all the subsets of (X∪Y) of cardinality k. So the cardinality of that is the number of possible subsets of size k. And I have no idea.

    (Sorry I'm not very good with trying to do math symbols online. To make it easier here's a link to an image of what I wrote: http://pic100.picturetrail.com/VOL71.../383315256.jpg

    It's also attached (Hopefully) I originally wrote it in a .docx file but I can't seem to upload it here anyway...

    Thanks for any help. I'm really quite stuck!
    I'm not really sure what this is saying. Do you mean f:\bigcup_{n=0}^{k}\left\{\mathcal{P}_n(X)\times\m  athcal{P}_{k-n}(Y)\right\}\mapsto\mathcal{P}_k\left(X\cup Y\right)? Ok, so assume that f\left(A,B\right)=f\left(C,D\right) then A\cup B=C\cup D. So, if x\in A\cup B then x\in A\text{ or }x\in B. It can't be in both so assume it's in A. Then, x\in C\cup D but since x\in A\subseteq X we see that x\notin D\implies x\in C and so A\subseteq C. Using the exact same idea we see that A=C,B=D\implies (A,B)=(C,D) and the conclusion follows.

    To see that it's surjective let M\in\mathcal{P}_K\left(X\cup Y\right), then M=A\cup B where A\subseteq X,B\subseteq Y and \text{card }A+\text{card }B=k\implies \text{card B}=k-\text{card }A. It clearly follows that A\in\mathcal{P}_{\text{card }A}(X),B\in\mathcal{P}_{k-\text{card }A}(Y) and the conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    8
    Thanks and Yes f:\bigcup_{i=0}^{k}\left\{\mathcal{P}_i(X)\times\m  athcal{P}_{k-i}(Y)\right\}\mapsto\mathcal{P}_k\left(X\cup Y\right)<br />

    Is what I am supposed to be showing is bijective.

    So let me get this straight (sorry I'm a little slow) you're showing that it's injective by showing that f(A,b) = f(C,D) implies (A,B) = (C,D) (which is the definition of injective, I get that much. I don't see why this implies that AUB = CUD. Also I'm not sure where the conclusion that x is not an element of D comes from. The biggest problem with my understanding, is I'm not sure how it relates to the "power set" function. We were given the hint:

    If A\subseteq X and B\subseteq Y , we can join them to make the subset A\cup B of X\cup Y . On the other hand, given C\subseteq \left(X\cup Y\right) , we can break it up into C\cap X and C\cap Y .

    This gives a bijection  from [Math]{\mathcal{P} (X)\times\mathcal{P} (Y)}\mapsto\mathcal{P}\left(X\cup Y\right)[/tex], namely, f:(A,B) = A\cup B and

    f^-1: (C) = (C\cap X, C\cap Y )

    Now look at sets of a particular size. If |A| = i and |B| =k-i, then | (A\cup B)| =k (A and B are disjoint). Inversely if |C| =k, what can you say about | C\cap X| and | C\cap Y|? Take it from here...

    Which is what I tried to do but seem to be wandering in the dark.

    On the second part of the question I know that it is basically the cardinality of the first part and that I have to prove that the Cardinality of the RHS (which is a Union) is the cardinality of the LHS (which is a Sum of products) but I'm also lost there...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jmcq View Post
    Thanks and Yes f:\bigcup_{i=0}^{k}\left\{\mathcal{P}_i(X)\times\m  athcal{P}_{k-i}(Y)\right\}\mapsto\mathcal{P}_k\left(X\cup Y\right)<br />

    Is what I am supposed to be showing is bijective.

    So let me get this straight (sorry I'm a little slow) you're showing that it's injective by showing that f(A,b) = f(C,D) implies (A,B) = (C,D) (which is the definition of injective, I get that much. I don't see why this implies that AUB = CUD. Also I'm not sure where the conclusion that x is not an element of D comes from. The biggest problem with my understanding, is I'm not sure how it relates to the "power set" function. We were given the hint:

    If A\subseteq X and B\subseteq Y , we can join them to make the subset A\cup B of X\cup Y . On the other hand, given C\subseteq \left(X\cup Y\right) , we can break it up into C\cap X and C\cap Y .

    This gives a bijection from [Math]{\mathcal{P} (X)\times\mathcal{P} (Y)}\mapsto\mathcal{P}\left(X\cup Y\right)[/tex], namely, fA,B) = A\cup B and

    f^-1: (C) = (C\cap X, C\cap Y )

    Now look at sets of a particular size. If |A| = i and |B| =k-i, then | (A\cup B)| =k (A and B are disjoint). Inversely if |C| =k, what can you say about | C\cap X| and | C\cap Y|? Take it from here...

    Which is what I tried to do but seem to be wandering in the dark.

    On the second part of the question I know that it is basically the cardinality of the first part and that I have to prove that the Cardinality of the RHS (which is a Union) is the cardinality of the LHS (which is a Sum of products) but I'm also lost there...
    I think you're making this much harder than it need be.

    You agree that f(A,B)=f(C,D)\implies (A,B)=(C,D) proves injectivity right?

    Well, f(A,B)=A\cup B and f(C,D)=C\cup D so we see that f(A,B)=f(C,D)\implies A\cup B=C\cup D. But, X\cap Y=\varnothing. So, if x\in A\cup B it has to either be in A or B but not both (since A<br />
\subseteq X and B\subseteq Y). Thus, for all cases we make a modified argument of the following: assume x\in A then x\in A\cup B=C\cup D and so x\in C\cup D but since D\cap A\subseteq X\cap Y=\varnothing we see that x\notin D and so it must be that x\in C. Thus, A\subseteq C. Doing this four times proves that A=B,C=D and since an ordered tuple is equal if and only if it's coordinates are equal we see that this implies that (A,B)=(C,D). Injectivity follows.

    For surjectivity, we let M\in\mathcal{P}_k(X\cup Y). Using the fact that X\cap Y=\varnothing we may conclude that M=A\cup B where A\subseteq X,B\subseteq Y and A\cap B=\varnothing. But, we know that k=\text{card }A\cup B=\text{card }A+\text{card }B+\text{card }A\cap B=\text{card }A+\text{card }B (using the fact, once again, that A and B are disjoint). Thus, \text{card }B=k-\text{card }A. We see then A is a subset of X of size \ell and B is a subset of size k-\ell. And thus X\in\mathcal{P}_\ell(X) and B\in\mathcal{P}_{k-\ell}(Y). So, A\times B\in\mathcal{P}_\ell(X)\times\mathcal{P}_{k-\ell}(Y) and so A\times B\in\bigcup_{n=0}^{k}\left\{\mathcal{P}_{n}(X)\tim  es\mathcal{P}_{k-n}(Y)\right\}. Therefore, f(A,B)=A\cup B=M. Since M was arbitrary we know that f is surjective.

    Bijectivity follows by combination.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    Posts
    8
    Ah I see how you did that now >.<. Thanks!

    Now on to the second part of the question. I guess I'll have another look at it. Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Union of open sets proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 26th 2011, 04:04 PM
  2. A proof for the union of a family of sets..
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 20th 2010, 09:38 PM
  3. Real Analysis: Union of Countable Infinite Sets Proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 14th 2010, 06:38 PM
  4. Proof that union of two connected non disjoint sets is connected
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 27th 2009, 09:22 AM
  5. Power Sets Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 20th 2007, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum