# Thread: Proof of Union of Power Sets

1. ## Proof of Union of Power Sets

Prove that $\displaystyle \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:

$\displaystyle {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)→$\displaystyle \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: (m¦i)(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!

2. Originally Posted by jmcq
Prove that $\displaystyle \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:

$\displaystyle {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)→$\displaystyle \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: (m¦i)(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 $\displaystyle 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 $\displaystyle f\left(A,B\right)=f\left(C,D\right)$ then $\displaystyle A\cup B=C\cup D$. So, if $\displaystyle x\in A\cup B$ then $\displaystyle x\in A\text{ or }x\in B$. It can't be in both so assume it's in $\displaystyle A$. Then, $\displaystyle x\in C\cup D$ but since $\displaystyle x\in A\subseteq X$ we see that $\displaystyle x\notin D\implies x\in C$ and so $\displaystyle A\subseteq C$. Using the exact same idea we see that $\displaystyle A=C,B=D\implies (A,B)=(C,D)$ and the conclusion follows.

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

3. Thanks and Yes $\displaystyle 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)$

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 $\displaystyle A\subseteq X$ and $\displaystyle B\subseteq Y$ , we can join them to make the subset $\displaystyle A\cup B$ of $\displaystyle X\cup Y$ . On the other hand, given $\displaystyle C\subseteq \left(X\cup Y\right)$ , we can break it up into $\displaystyle C\cap X$ and $\displaystyle 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) = $\displaystyle A\cup B$ and

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

Now look at sets of a particular size. If |A| = i and |B| =k-i, then |$\displaystyle (A\cup B)$| =k (A and B are disjoint). Inversely if |C| =k, what can you say about |$\displaystyle C\cap X$| and |$\displaystyle 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...

4. Originally Posted by jmcq
Thanks and Yes $\displaystyle 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)$

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 $\displaystyle A\subseteq X$ and $\displaystyle B\subseteq Y$ , we can join them to make the subset $\displaystyle A\cup B$ of $\displaystyle X\cup Y$ . On the other hand, given $\displaystyle C\subseteq \left(X\cup Y\right)$ , we can break it up into $\displaystyle C\cap X$ and $\displaystyle 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) = $\displaystyle A\cup B$ and

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

Now look at sets of a particular size. If |A| = i and |B| =k-i, then |$\displaystyle (A\cup B)$| =k (A and B are disjoint). Inversely if |C| =k, what can you say about |$\displaystyle C\cap X$| and |$\displaystyle 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 $\displaystyle f(A,B)=f(C,D)\implies (A,B)=(C,D)$ proves injectivity right?

Well, $\displaystyle f(A,B)=A\cup B$ and $\displaystyle f(C,D)=C\cup D$ so we see that $\displaystyle f(A,B)=f(C,D)\implies A\cup B=C\cup D$. But, $\displaystyle X\cap Y=\varnothing$. So, if $\displaystyle x\in A\cup B$ it has to either be in $\displaystyle A$ or $\displaystyle B$ but not both (since $\displaystyle A \subseteq X$ and $\displaystyle B\subseteq Y$). Thus, for all cases we make a modified argument of the following: assume $\displaystyle x\in A$ then $\displaystyle x\in A\cup B=C\cup D$ and so $\displaystyle x\in C\cup D$ but since $\displaystyle D\cap A\subseteq X\cap Y=\varnothing$ we see that $\displaystyle x\notin D$ and so it must be that $\displaystyle x\in C$. Thus, $\displaystyle A\subseteq C$. Doing this four times proves that $\displaystyle 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 $\displaystyle (A,B)=(C,D)$. Injectivity follows.

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

Bijectivity follows by combination.

5. 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.