[Math] For all sets $A$ and $B$, $P(A \times B) = P(A) \times P(B)$

discrete mathematicselementary-set-theory

Prove each statement that is true and find a counterexample for each statement that is false.

For all sets $A$ and $B$, $P(A × B) = P(A) × P(B)$.

For all sets $A$ and $B$, $P(A ∩ B) = P(A) ∩ P(B)$.

Here $P$ is the power set.

Can some show or explain to me how to do this? I'm very confused. Thanks.

Best Answer

The first statement, $\mathcal{P}(A \times B) = \mathcal{P}(A) \times \mathcal{P}(B)$, is false. To disprove this, all you have to do is consider a special case like $A = \{1\}, B = \{1\}$. What are the two sets in this case? Or, count the sizes of the two sets.

The second statement is true. To prove the equality of sets $X = Y$, a very common strategy is to first show $X \subseteq Y$, and then show $Y \subseteq X$. To show $X \subseteq Y$, you start with an arbitrary $x \in X$ and you prove that $x \in Y$.

So we want to show the equality $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$. Suppose $x \in \mathcal{P}(A \cap B)$. Then $x \subseteq A \cap B$. It follows since $A \cap B \subseteq A$ and $A \cap B \subseteq B$ that $x \subseteq A$ and $x \subseteq B$. So $x \in \mathcal{P}(A)$ and $x \in \mathcal{P}(B)$. So $x \in \mathcal{P}(A) \cap \mathcal{P}(B)$.

That proves $\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)$. Can you do the other direction?

Related Question