Most efficient way to prove basic set equality?

Question

Suppose you are asked to prove that $A \cap (B - C) = (A \cap B) - (A \cap C)$. What is the “best” way to go about doing so? Remark: the equality we are asked to prove is not really relevant; I just picked a random example from Chapter 1 of Munkres which can't be completed in a line or two.

I will provide two ways I would prove it. I would like feedback on which is best, with feedback (if any) on how to improve the best one. We can define the best to be the proof which, in your own opinion, has the optimal combination of satisfactory, brevity, logical leaps, and readability as well as elegance.

Proof 1: Let $x \in A \cap (B - C)$. Then $x \in a$ and $x \in B - C$, and by definition of set difference, $x \in B$ and $x \notin C$. Observe that $A \cap C \subset C$, and since $x \not\in C$, it follows that $x \not\in A \cap C$. Therefore, $x \in A$ and $x \in B$ but $x \not\in A \cap C$. The set of $x$ which satisfy this is $(A \cap B) - (A \cap C)$.

Now Let $x \in (A \cap B) - (A \cap C)$. Then $x \in A \cap B \Rightarrow x \in A$ and $x \in B$ and $x \not\in A \cap C$. This means that $x \not\in A$ or $x \not\in C$, but we know $x \in A$, so $x \in A$ and $x \in B$ bug $x \not\in C$. Therefore, $A \cap (B - C)$. Alternatively, we could also write this as $(A \cap B) - C$. Either way, the proof is done.

Proof 2:

\begin{align*} A \cap (B - C) &= \{ x \mid x \in A ~\text{and}~ x \in (B - C) \}, \\ &= \{ x \mid x \in A ~\text{and}~ (x \in B ~\text{and}~ x \not\in C) \}, \\ &= \{ x \mid (x \in A ~\text{and}~ x \in B) ~\text{and}~ (x \in A ~\text{and}~ x \not\in C)\}, \\ &= \{ x \mid (x \in A ~\text{and}~ x \in B) ~\text{and}~ x \not\in C\}, \\ &= (A \cap B) - C. \end{align*} Now notice that

\begin{align*} (A \cap B) - (A \cap C) &= \{ x \mid (x \in A ~\text{and}~ x \in B) ~\text{and}~ x \not\in A \cap C \}, \\ &= \{ x \mid (x \in A ~\text{and}~ x \in B) ~\text{and}~ (x \not\in A ~\text{or}~ x \not\in C ) \}, \\ &= \{ x \mid (x \in A ~\text{and}~ x \in B) ~\text{and}~ x \not\in C \}, \\ &= (A \cap B)-C, \end{align*}which is is equal to $A \cap (B - C)$ by the previous part.

Bonus question: which way would Munkres want?

Answer 1

I think proof 1 is the better proof for the reasons described by user2661923. However, personally I like the logic based approach for these types of problems, as the proofs tend to be clear and short. I know some people don't like these (Why? Because they don't consider themselves to be computers!). To do them, you need to have a handle on the logic identities and how to generate them (e.g. through natural deduction). Here is the proof:

$x\in(A\cap B) \backslash (A \cap C)$
$\iff ((x \in A \wedge x \in B) \wedge \neg(x \in A \wedge x \in C))$
$\iff ((x \in A \wedge x \in B) \wedge (x \notin A \lor x \notin C)) \hspace {35pt} $ By Demorgan
$\iff ((x \in A \wedge x \in B) \wedge x \notin C) \hspace {79pt}$ Distributivity and eliminate contradiction
$\iff (x \in A \wedge (x \in B \wedge x \notin C)) \hspace {79pt}$ By associativity
$\iff x \in A \cap ( B \backslash C)$

Answer 2

The simplest way is to use the formula $X/Y=X\bigcap\,Y^{c}$ where $Y^{c}$ the complement of $Y$. Then.

$A\bigcap(B/C)=A\bigcap\,B\,\bigcap\,C^{c}$. $(1)$

Also $(A\bigcap\,B)/(A\bigcap\,C)$=$(A\bigcap\,B)\bigcap[A\bigcap C)^{c}$. Now the complement of intersection is the union of complements, so the latter

=$(A\bigcap\,B)\bigcap(A^{c}\bigcup\,C^{c})$=$\varnothing\,\bigcup\,A\bigcap\,B\,\bigcap\,C^{c}$

=$A\bigcap\,B\,\bigcap\,C^{c}\,\,\,\,$ $(2)$.

By $(1),(2)$ we get the result!!