Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The power set of a union

  1. Dec 23, 2008 #1
    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. jcsd
  3. Dec 23, 2008 #2
    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).
  4. Dec 23, 2008 #3
    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.
  5. Dec 23, 2008 #4


    User Avatar
    Science Advisor
    Gold Member

    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.
  6. Dec 23, 2008 #5
    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.
  7. Dec 23, 2008 #6
    As a concrete example, if [tex]x \in X[/tex] and [tex]y \in Y[/tex], then [tex]\{x, y\} \in \mathcal{P}(X \cup Y)[/tex] but [tex]\{x, y\} \notin \mathcal{P}X \cup \mathcal{P}Y[/tex].
  8. Dec 24, 2008 #7


    User Avatar
    Science Advisor

    If [itex]x \in X[/itex] but [itex]x \notin Y[/itex] and [itex]y\in Y[/itex] but [itex]y\notin X[/itex].

    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 [itex]X\cup Y= {x, y}[/itex] so its power set is [itex]\phi, \left{x}\right}, \left{y\right}, \left{x,y\right}[/itex] while the power set of X is [itex]\phi, \left{x\right}[/itex] and the power set of Y is [itex]\phi, \left{y\right}[/itex] so "the union of the power set of X and the power set of y" is [itex]\phi, \left{x\right}, \left{y\right}[/itex].
    Last edited by a moderator: Dec 24, 2008
  9. Dec 24, 2008 #8
    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?
  10. Dec 24, 2008 #9
    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 [tex]\mathcal{P}(X \cup Y) = \mathcal{P}X \cup \mathcal{P}Y[/tex] if and only if [tex]X \subseteq Y[/tex] or [tex]Y \subseteq X[/tex]. (This includes the case where one of the sets is empty.) This should be easy to prove.
    Last edited: Dec 24, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook