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

Homework Help: Discrete Math Proving some power sets

  1. Jan 24, 2006 #1
    Ok so I need to prove (by contradiction) that... if the power set(A) is a subset of power set(B), then A is a subset of B.

    I was given a hint to use proof by contradiction, but in general I'm lost as to what to do... I know the power set of (A) is {B|B subset A} and the powerset of (B) is {A|A subset B} but that's about it. As far as where to start; I'm drawing a blank. I need a point in the right direction of where to start, because as it stands now I've spent 2 hours looking at this problem.
  2. jcsd
  3. Jan 24, 2006 #2
    Ok I think I got it...

    My proof is this; Assume that if P(A) is a subset of P(B), then A is not a subset of B (contradiction method). I then show that by definition of a power set; power set B must contain all sets that are in power set A. That would mean that powerset B must contain the set A, there for A is a subset of B (since P(B) contains the set A). Which contradicts the assumption.

    Not sure if it's complete, but I think the logic is right (makes sense).
  4. Jan 24, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Unnecessary contradiction. A is an element of P(A), which is contained in P(B), ie A is an element of P(B), hence A is....
  5. Jan 24, 2006 #4
    a subset of B.
  6. Jan 24, 2006 #5


    User Avatar
    Science Advisor

    Also if you're doing it by contradiction, this is not the assumption you want to make. The negation of the statement "if P(A) is a subset of P(B), then A is not a subset of B" is "P(A) is a subset of P(B) and A is a subset of B," which you can't prove anyway. What you mean is "Assume P(A) is a subset of P(B) _and_ A is not a subset of B."
  7. Jan 24, 2006 #6
    Ah I understand what you are saying, so it's just assuming without implication (sort of). We are assuming P(A) is a subset of P(B) and we assume A is not a subset of B. That makes sense.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook