Why does \mathcal{P}(X \cup Y) not always equal \mathcal{P}X \cup \mathcal{P}Y?

[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).

 

[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).

 

[adriank]

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.

 

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

 

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

 

[adriank]

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

 

[HallsofIvy]

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

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}$.

 

[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?

 

[adriank]

Halls, good point; each of X and Y must not be a subset of the other.

jojo, that does work as well.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.