The exercise asks the reader to prove or disprove the following statement.

If $A$ and $B$ are sets, then $\mathscr{P}(A) \cap \mathscr{P}(B) = \mathscr{P}(A \cap B)$.

I know one way to prove such a statement is to simply produce a series of equalities that transform the LHS of the equation into the RHS. However, I am not sure if my translation of the powersets into set builder notation is valid. More specifically, the book never gives an example of a quantifier used in a set builder so I tried to translate from the book's definition of a subset written in English (as opposed to symbolic notation). Bellow is my proof.

Proof. Observe the following sequence of equalities. \begin{align} \mathscr{P}(A) \cap \mathscr{P}(B) &= \{ X: X \subseteq A \land X \subseteq B\} &(\text{def. of powerset}) \\ &= \{ X: \forall x \in X, x \in A \land x \in B \} &(\text{def. of subset}) \\ &= \{ X:\forall x \in X, x \in A \cap B \} &(\text{def. of intersection}) \\ &= \{ X: X \subseteq A \cap B \} &(\text{def. of subset}) \\ &= \mathscr{P}(A \cap B) &(\text{def. of powerset}) \end{align}

The proof is complete. $$\tag*{$\blacksquare$}$$

Any feedback on the validity of this proof or on ways it could be better written is greatly appreciated.

  • $\begingroup$ The proof looks good to me, and the equalities are alright. I would just add the following caveat: $\{X|x\in A \textit { and } x\in B, \textit { then } x\in X\}$. Basically, make it a conditional with the "and" statement as the antecedent. It's just cosmetic, but it makes it more fluid. $\endgroup$ – Bertrand Wittgenstein's Ghost Feb 5 at 22:27
  • 1
    $\begingroup$ @BertrandWittgenstein'sGhost: The OP’s version is correct; what you’re suggesting would not be, as it describes the collection of $X$ such that $A\cap B\subseteq X$. $\endgroup$ – Brian M. Scott Feb 5 at 22:30
  • $\begingroup$ @BrianM.Scott that's weird, I don't read it like that. $\endgroup$ – Bertrand Wittgenstein's Ghost Feb 5 at 22:35
  • 2
    $\begingroup$ @BertrandWittgenstein'sGhost: $x\in A\land x\in B\to x\in X$ clearly says that if $x$ belongs to both $A$ and $B$, then $x$ belongs to $X$. This certainly implies that $A\cap B\subseteq X$. And it says absolutely nothing about any $x$ that does not belong to both $A$ and $B$, so it is entirely possible that some of them also belong to $X$. Thus, we cannot conclude that $X=A\cap B$, and it is certainly the case that $X$ cannot be a proper subset of $A\cap B$. In short, it says that $X\supseteq A\cap B$. If you’re reading it differently, I’m afraid that you’re misreading it. $\endgroup$ – Brian M. Scott Feb 5 at 22:40
  • 1
    $\begingroup$ @BertrandWittgenstein'sGhost: You’re very welcome! $\endgroup$ – Brian M. Scott Feb 5 at 22:50

The proof is correct, and if you’re required to use that rather artificial format, it’s just fine. You probably are required to give that much detail, but if you’re not restricted to that format, it could be given in a form closer to normal mathematical writing:

$X\in\wp(A)\cap\wp(B)$ iff $X\in\wp(A)$ and $X\in\wp(B)$, which is the case iff $X\subseteq A$ and $X\subseteq B$. But that is true iff $X\subseteq A\cap B$, i.e., iff $X\in\wp(A\cap B)$, so $\wp(A)\cap\wp(B)=\wp(A\cap B)$.

  • $\begingroup$ Thank you. I am going through the book for my own pleasure so no one is imposing a format on me. The book is my first exposition to formal proof writing so I try to be as thorough and rigorous as possible, similarly to how the author presents the content, although sometimes the statement are trivial to prove. I appreciate the feedback and the example of how it would be written in a normal mathematical writing context. $\endgroup$ – madibam Feb 5 at 22:37
  • $\begingroup$ @madibam: You’re welcome. $\endgroup$ – Brian M. Scott Feb 5 at 22:40
  • $\begingroup$ Your answer kind of leads to a latent question I have about proof writing. The reason I wanted to expand the statement into set builder notation is that I did not want to assume $X \subseteq A$ and $X \subseteq B \iff X \subseteq A \cap B$ although it makes intuitive sense. So, to what extend can we assume statements as these? Does it depend entirely on the context and the level of your readers? $\endgroup$ – madibam Feb 5 at 22:42
  • 1
    $\begingroup$ @madibam: Yes, it really does depend very heavily on context and the expected readership. If I write something up for advanced undergraduates, I’ll give more detail than I would in a research paper and less than I would if I were writing for sophomores, say. $\endgroup$ – Brian M. Scott Feb 5 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.