# Powerset Proof

1. May 3, 2007

### Hallucigen

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.

2. May 3, 2007

### matt grime

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.

3. May 5, 2007

### ZioX

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.

4. May 5, 2007

### fopc

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

5. May 5, 2007

### MathematicalPhysicist

btw, a good question for you, is what condition on the sets should be met in order to be an equality?

6. May 9, 2007

### fopc

Think idempotence.

7. May 9, 2007

### EnumaElish

Show that for arbitrary A and B

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

8. May 12, 2007

### bomba923

$$\mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \supset \mathcal{P} \left( A \cup B \right)$$

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

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

Why not just apply a simple direct proof?

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

so therefore,
$$\thus \mathcal{P} \left( A \right) \cup \mathcal{P} \left( B \right) \subseteq \mathcal{P} \left( A \cup B \right)$$

Last edited: May 12, 2007
9. May 13, 2007

### matt grime

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.

10. May 14, 2007

### EnumaElish

My post #7 should have read:

Show either ⊆ or ⊃ must be the case,

11. Oct 17, 2009

### jacktsoi

How to use your method the prove/disprove this proof?
Powerset(A ∩ B) = Powerset(A) ∩ Powerset(B)

12. Oct 17, 2009

### honestrosewater

To prove that theorem, you could use these theorems:

$$\forall X, Y, Z \ [Y = Z \leftrightarrow (X \in Y \leftrightarrow X \in Z)]$$
$$\forall X, Y \ [X \in \mathcal{P}(Y) \leftrightarrow X \subseteq Y]$$
$$\forall X, Y, Z \ [X \in (Y \cap Z) \leftrightarrow (X \in Y \wedge X \in Z)]$$

13. Oct 22, 2009

### Attilitus

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.