Showing that $A\cap B = A\setminus (A\setminus B)$

Question

How does one show that $A\cap B = A\setminus (A\setminus B)$?

My thinking is that if $x\in A\setminus (A\setminus B)$ then this means that $x\in A$ and $x\notin A\setminus B$, which means that $x\in A$ and ($x\notin A$ and $x\in B$), but I don't see why the expression in parentheses should simplify to just $x\in B$. Any insight would be helpful.

Maybe $(x\in A^c$ and $x\in B)$, i.e, $x\in A^c\cap B$ is a possible simplification of the expression in parentheses, but still don't see why this simplifies to just $x\in B$.

Answer 1

Your reasoning is good, you just made a small mistake.

When you write $x\in A\setminus (A\setminus B)$, it's perfectly ok to conclude $x\in A$ and $x\notin A\setminus B$. Notice the use of the logical connective AND.

Thus, when you write $x\notin A\setminus B$, what you're saying, from the point of view of logic, is it is not the case that $x\in A\setminus B$. Therefore, it is not the case that ($x\in A$ AND $x\notin B$). That's where your mistake lies: you need to distribute the negation over the conjunction (also known as De Morgan's Law).

You can easily convince yourself that NOT( A AND B)=(NOT A) OR (NOT B).

Therefore you get that $x\notin A\setminus B$ is equivalent to $x\notin A$ OR $x\in B$ (double negation cancels out). But you already know that $x\in A$. Therefore, it must be the case that $x\in B$.

Since $x\in A$ and $x\in B$, we have $x\in A\cap B$.

---

You could also start with the LHS: $x\in A\cap B\Longleftrightarrow x\in A\text{ and }x\notin B^c$.

Then you just have to argue that: $x\notin B^c\Longleftrightarrow x\notin A\setminus B$ and you're done.

Answer 2

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

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

This uses De Morgan's Law $\overline{A\stackrel{\cup}\cap B}=\overline{A}\stackrel{\cap}\cup \overline {B}$ and the distributive law $$A\stackrel{\cup}\cap (B\stackrel{\cap}\cup C)=(A\stackrel{\cup}\cap B)\stackrel{\cap}\cup (A\stackrel{\cup}\cap C)$$

Also, $A\setminus B=A\cap\overline{B}$.

This uses the notation $\overline{A}$ for $A^c$.

---

Another proof:

If $x\in A\setminus(A\setminus B)$, then $$(x\in A)\wedge (x\not\in A\setminus B)\iff (x\in A)\wedge ((x\not\in A)\lor (x\in B))\iff$$

$$\iff (x\in A)\wedge (x\not\in A))\lor ((x\in A)\wedge (x\in B))\iff$$

$$\iff (x\in A)\wedge (x\in B)\iff (x\in A\cap B)$$

---

You said: "$x\in A$ and $x\not\in A\setminus B$, which means that $x\in A$ and $(x\not\in A \wedge x\in B)$", but it's actually "$(x\not\in A \lor x\in B)$", since $¬(A\cap \overline {B})=\overline{A}\cup B$ by De Morgan's law.

Since you have that $(x\in A)\wedge ((x\not\in A)\lor (x\in B))$, we know that $(x\in A)\wedge (x\in B)$, since $x$ can't be in $A$ and $\overline {A}$ at the same time so that you can ignore the $(x\not\in A)\lor$ in the expression (or you can show like I did in the second proof above).

Answer 3

Hint: Generalizing your own observation slightly, we have (in any universe $X$ in which $A, B$ are sets) that $A \setminus B = A \cap B^c$.

Additional hint: Now, apply de Morgan.

Answer 4

Observe that $ x\in A\cap B \Leftrightarrow x\in A \text{ and }x\notin B^{c}\Leftrightarrow x\in A \text{ and }x\notin A\setminus B \Leftrightarrow x\in A\setminus (A\setminus B) $