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

Powerset Proof

  1. May 3, 2007 #1
    Hey everyone,
    Can I get some tips on this proof?

    Powerset(A) U Powerset(B) ⊆ Powerset(A ∪ B)

    not too sure how to prove that this is true... maybe some pointers? thanks. :biggrin:
     
  2. jcsd
  3. May 3, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Take something in the left hand side, and show it is in the right hand side. Although, this is one of those questions that is obviously true, and therefore it is difficult to jude precisely what one is required to write down for the teacher.
     
  4. May 5, 2007 #3
    What does it mean to be in the powerset of A? And what does it mean to be in the union?

    That's all you need to know.
     
  5. May 5, 2007 #4
    Couple of pointers.

    1. Set union is defined in terms of logical or. This should suggest proof by cases, where you will need only show details in case 1. Then state that case 2 follows mutatis mutandis. (See how your prof reacts to that.)

    2. The Addition Rule of Inference will make life very easy in the case 1 "details".
     
  6. May 5, 2007 #5
    btw, a good question for you, is what condition on the sets should be met in order to be an equality?
     
  7. May 9, 2007 #6
    Think idempotence.
     
  8. May 9, 2007 #7

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Show that for arbitrary A and B

    Powerset(A) U Powerset(B) ⊃ Powerset(A ∪ B)

    leads to a contradiction.
     
  9. May 12, 2007 #8
    Contradicting
    [tex] \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \supset \mathcal{P} \left( A \cup B \right) [/tex]

    is not enough, as it only proves
    [tex] \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \subseteq \mathcal{P} \left( A \cup B \right) [/tex]
    (logical) OR
    [tex] \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \ne \mathcal{P} \left( A \cup B \right) [/tex]

    To prove the OP statement, Hallucigen must also then contradict
    [tex] \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \ne \mathcal{P} \left( A \cup B \right) [/tex]

    Why not just apply a simple direct proof? :redface:

    [tex] x \in \mathcal{P} \left( A \right) \, \cup \, \mathcal{P} \left( B \right) \Rightarrow x \in \mathcal{P} \left( A \right) \, \vee \, x \in \mathcal{P} \left( B \right) \Rightarrow x \subseteq A \, \vee \, x \subseteq B \Rightarrow x \subseteq A \, \cup \, B \Rightarrow x \in \mathcal{P} \left( A \cup B \right) [/tex]

    so therefore,
    [tex]\thus \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \subseteq \mathcal{P} \left( A \cup B \right) [/tex]
     
    Last edited: May 12, 2007
  10. May 13, 2007 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Since the proof will demonstrate that there is an element of P(AuB) not in P(A) or P(B) (since the reverse inclusion is clearly true), this is not particularly relevant information. Plus, not every one uses the strict set inequality symbol to mean strict set inequality.
     
  11. May 14, 2007 #10

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    My post #7 should have read:

    Show either ⊆ or ⊃ must be the case,
    Show ⊃ leads to a contradiction.
     
  12. Oct 17, 2009 #11
    How to use your method the prove/disprove this proof?
    Powerset(A ∩ B) = Powerset(A) ∩ Powerset(B)
     
  13. Oct 17, 2009 #12

    honestrosewater

    User Avatar
    Gold Member

    To prove that theorem, you could use these theorems:

    [tex]\forall X, Y, Z \ [Y = Z \leftrightarrow (X \in Y \leftrightarrow X \in Z)][/tex]
    [tex]\forall X, Y \ [X \in \mathcal{P}(Y) \leftrightarrow X \subseteq Y][/tex]
    [tex]\forall X, Y, Z \ [X \in (Y \cap Z) \leftrightarrow (X \in Y \wedge X \in Z)][/tex]
     
  14. Oct 22, 2009 #13
    You take an element X of Powerset(A) union Powerset(B)

    X is either a subset of A or a subset of B.

    Since Powerset(A union B) contains all subsets of A union B it contains all subsets of A that do not contain elements of B and all subsets of B that do not contain elements of A. Therefore, X is in Powerset(A union B)

    Since every X in Powerset(A) union Powerset(B) is in Powerset(A union B), it follows that Powerset(A) union Powerset(B) is a subset of Powerset(A union B)

    Thats a proof... you should not need to do anything fancier than give an explanation like that.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Powerset Proof
  1. Powerset proof (Replies: 6)

  2. Proofs . . . (Replies: 5)

  3. Proof that a=a (Replies: 3)

  4. Proof of epimormphism? (Replies: 3)

Loading...