Prove that $A-(B\cup C) = (A-B) \cap (A-C)$

$A-(B\cup C)=(A-B)\cap(A-C)$ \begin{align*} x\in [(A-(B\cup C) ] &\Rightarrow x \in[(A-B)\cap (A-C)]\\ &\Rightarrow x\in(A-B) \land x \in (A-C) \\ & \Rightarrow (x \in A \land x \notin B) \land ( x \in A \land x \notin C)\\ & \Rightarrow (x \in A) \land (x \notin B \lor x \notin C) \\ & \Rightarrow A- (B \cup C) \end{align*}

This and the thesis proving the hypothesis, now it must do the opposite? Hypothesis prove the thesis?

\begin{align*} x \in [(A-B) \cap (A-C)] &\Rightarrow x \in [A-(B \cup C)] \\ &\Rightarrow x \in A \land x \in (B \cup C) \\ &\Rightarrow ( x \in A) \land (x \in B \lor x \in C) \\ &\Rightarrow (x \in A \land x \notin B) \land ( x \in A \land x \notin C) \\ & \Rightarrow (A-B) \cap (A-C) \end{align*}

Is this correct?

• The organization of this seems a bit off... almost like the first line is meant as a label for what you are trying to prove and you have your labels reversed accidentally. You also have some $\in$'s which should be replaced with $\notin$'s. There is also a $\vee$ which should have been a $\wedge$ that I can see. – JMoravitz May 19 '17 at 22:39
• Could you show me where I went wrong? – user447599 May 19 '17 at 22:59

I will add positions for notes using $[\star 1],[\star 2],\dots$ at the end of lines to denote where the location of the note is in reference to, and then will write out notes at the bottom:

Looking at the second section of what you show in detail, you write:

\begin{align*} x \in [(A-B) \cap (A-C)] &\Rightarrow^{[\star 1]} x \in [A-(B \cup C)]\\ &\Rightarrow x \in A \land x \in (B \cup C) ~~[\star 2]\\ &\Rightarrow ( x \in A) \land (x \in B \lor x \in C)~~[\star 3] \\ &\Rightarrow (x \in A \land x \notin B) \land ( x \in A \land x \notin C)~~[\star 4] \\ & \Rightarrow (A-B) \cap (A-C)~~[\star 5] \end{align*}

$[\star 1]$ This implication is not true, but it appears that perhaps you intend this line entirely as a header explaining what we expect to see in what follows. All of the work that follows appears to be taking $x\in [A-(B\cup C)]$ as the hypothesis, not what is written on the far left which is what is the implied intended hypothesis. Suggest replacing this entire line with: "We wish to show the implication $x\in [A-(B\cup C)]\implies x\in[(A-B)\cap (A-C)]$... to do so, suppose $x\in[A-(B\cup C)]$" and then continue as normal.

$[\star 2]$ Here, you went from $x\in[A-(B\cup C)]$ to $x\in A\wedge x\color{red}{\in} (B\cup C)$. The red $\color{red}{\in}$ should have instead been a $\notin$. Remember set difference: $x\in E-F$ is the set of all $x$ such that $x$ is in $E$ but is not in $F$. This could have just been a typo.

$[\star 3]$ Here, the mistake from the earlier typo causes the proof to divert from the intended path. The implication as written here is correct, but although it is true that $x\in A\wedge x\in(B\cup C)$ does imply $x\in A\wedge (x\in B\vee x\in C)$, this is not how this step would have looked without the earlier mistake. Note that $x\notin (B\cup C)$ implies $x\notin B \wedge x\notin C$.

$[\star 4]$ The implication as written, $(x\in A)\wedge (x\in B\vee x\in C)\implies (x\in A\wedge x\notin B)\wedge (x\in A\wedge x\notin C)$ is false. Somehow you started using $\notin$'s here where they hadn't appeared in what you have written up to this point and for seemingly no reason other than this is the correct final line that you would need to arrive at the final conclusion. Had none of the mistakes occurred up until this point, your previous line should have read $(x\in A)\wedge (x\notin B\wedge x\notin C)$ to which one could with a little bit of mental gymnastics go straight to the conclusion for this line, but I would still include an additional step for clarity that $(x\in A)\wedge (x\notin B\wedge x\notin C)\implies (x\in A\wedge x\in A\wedge x\notin B\wedge x\notin C)$ to which the next step is just recognizing that you can rearrange these and place parentheses as you like.

$[\star 5]$ Here in your final line you have written $(x\in A\wedge x\notin B\wedge)\wedge (x\in A\wedge x\notin C)\implies (A-B)\cap (A-C)$. This is awkward because on the left we have a logical statement whereas on the right we have a set. A set is not a logical statement which has truth value... it is just a set. You should have instead written $\color{red}{x\in[}(A-B)\cap (A-C)\color{red}{]}$ where the inclusion of the "$x\in$" phrase makes this now a logical statement as necessary.

Your first section has similar errors.

Remember the following things:

• $X-Y$ is another writting for $X\cap\overline Y$ where $\overline Y$ is the complement of $Y$
• $\bigcap$ and $\bigcup$ are associative
• taking the complement inverse the role of $\bigcap$ and $\bigcup$

From there you can transform one statement into the other :

$(A-B)\cap(A-C)=(A\cap\overline B)\cap(A\cap\overline C)=A\cap(\overline B\cap\overline C)=A\cap(\overline{B\cup C})=A-(B\cup C)$