# Homework Help: Discrete Math Proving some power sets

1. Jan 24, 2006

### Servo888

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. Jan 24, 2006

### Servo888

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

3. Jan 24, 2006

### matt grime

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

4. Jan 24, 2006

### Servo888

a subset of B.

5. Jan 24, 2006

### 0rthodontist

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

6. Jan 24, 2006

### Servo888

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.