# The power set of a union

1. Dec 23, 2008

### jojo12345

It seems intuitive that the power set of a union of sets P(XunionY) is not a subset of the union of the two respective power sets P(X)unionP(Y). For finite sets the former will have more elements than the latter.

However, I can't figure out what is wrong with the following line of reasoning:

For a set S
( S in P(XunionY) ) implies ( S is a subset of XunionY ) implies (1)
for some x
( x in S implies x in XunionY ) implies (2)
( x not in S OR x in X OR x in Y ) implies (3)
( ( x in S implies x in X ) OR (x in S implies x in Y) ) implies (4)
( ( S is a subset of X ) or ( S is a subset of Y ) ) (5)

I could continue, but I'm nearly certain I have made a mistake somewhere already. I can't figure out where. I suspect that (3) is incorrect, but I don't see why I can't make the substitution I made namely:

(A implies B) iff (notA OR B)

Also, I know that (5) is incorrect. Perhaps (5) doesn't follow from (4).

2. Dec 23, 2008

### Moo Of Doom

Indeed (5) does not follow from (4), since for that, we need one or the other to be true for ALL x not for some x (for any particular x, one or the other is true, but for different x's it might not be the same one that is true).

3. Dec 23, 2008

You must use the fact that X and Y are both nonempty somewhere, since if one of them is empty then the power set of the union and the union of power sets are equal.

To do that, do something with one element from each of the sets.

4. Dec 23, 2008

### jambaugh

If the set C, a subset of AuB has some elements which are in A and some elements which are in B then C is in the power set of the union but not in the union of the power sets.

The union of the power sets contains sets which are either subsets of A or are subsets of B but not necessarily subsets of the union.

5. Dec 23, 2008

### jojo12345

Thank you very much. I should have included the universal quantifier from the beginning. My negligence of this fact, as well as not making clear that X and Y were nowhere empty, were my fallacies. The universal quantifier won't "distribute" over the OR. I appreciate everyone's response.

6. Dec 23, 2008

As a concrete example, if $$x \in X$$ and $$y \in Y$$, then $$\{x, y\} \in \mathcal{P}(X \cup Y)$$ but $$\{x, y\} \notin \mathcal{P}X \cup \mathcal{P}Y$$.

7. Dec 24, 2008

### HallsofIvy

If $x \in X$ but $x \notin Y$ and $y\in Y$ but $y\notin X$.

More simply, for a counter-example to "the power set of X union Y is a subset of the Power set of X union the power set of Y", take X= {x}, Y= {y}. Then $X\cup Y= {x, y}$ so its power set is $\phi, \left{x}\right}, \left{y\right}, \left{x,y\right}$ while the power set of X is $\phi, \left{x\right}$ and the power set of Y is $\phi, \left{y\right}$ so "the union of the power set of X and the power set of y" is $\phi, \left{x\right}, \left{y\right}$.

Last edited by a moderator: Dec 24, 2008
8. Dec 24, 2008

### jojo12345

Also, consider two non-empty disjoint sets E and F with N and M elements respectively. The union of their power sets will have 2^N + 2^M elements while the power set of the union will have 2^(M+N)>2^N+2^M for N,M large enough. Will this also work as a counter example?

9. Dec 24, 2008

I guess what's really happening is that $$\mathcal{P}(X \cup Y) = \mathcal{P}X \cup \mathcal{P}Y$$ if and only if $$X \subseteq Y$$ or $$Y \subseteq X$$. (This includes the case where one of the sets is empty.) This should be easy to prove.