1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    0rthodontist

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Discrete Math Proving some power sets
Loading...