Need Help Proving Powerset Inequality

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

 

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

 

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

 

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

 

[MathematicalPhysicist]

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

 

[fopc]

Think idempotence.

 

[EnumaElish]

Show that for arbitrary A and B

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

leads to a contradiction.

 

[bomba923]

Show that for arbitrary A and B
Powerset(A) U Powerset(B) ⊃ Powerset(A ∪ B)
leads to a contradiction.

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

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

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

 

[matt grime]

To prove the OP statement, Hallucigen must also then contradict...

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.

 

[EnumaElish]

My post #7 should have read:

Show either ⊆ or ⊃ must be the case,
Show ⊃ leads to a contradiction.

 

[jacktsoi]

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

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

 

[honestrosewater]

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

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

 

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