# How to show equality $A = (A\setminus B) \cup (A\setminus C) \cup (A \cap B \cap C)$

I need help with proving that: $$\tag{1}A = (A\setminus B) \cup (A\setminus C) \cup (A \cap B \cap C).$$

I started first with $2$ sets I showed that $A = (A\setminus B) \cup(A\cap B)$ like this:

1. $A \cap U$
2. $A \cap(\overline B \cup B)$
3. Distributive Law $\Rightarrow(A\cap\overline B) \cup(A\cap B)$
4. Using $(A\cap \overline B) = A\setminus B$ I got $(A\setminus B) \cup (A\cap B)$

Now I tried to show, with same rules used up there, for sets $A,B,C$ that (1) holds. But the expression got ugly and I got stuck.

I tried to show with inclusions that 2 sets are equal:

1. $(\supseteq)$ is trivial, because for each of the 3 sets in the RHS has $x \in A$.
2. $(\subseteq)$ Let $x\in A$. I "split" set $A$ in two cases. First I assumed that $x\in A \setminus(B\cup C)$. Then since $A \setminus(B\cup C)\subseteq A\setminus B$, we have $$x\in (A\setminus B) \cup (A\setminus C) \cup (A \cap B\cap C) .$$ Second case was $x\notin A \setminus(B\cup C)$. Then $(x\notin A) \lor (x\in (B\cap C))$. $x\notin A$ is contradiction, so $x\in (B\cap C)$ and with that $x\in (A\setminus B) \cup (A\setminus C) \cup (A \cap B\cap C)$.

Can I split $A$ in two cases like I did and if someone could hint me how to start with showing equality using laws because I want to know both ways.

• Just Draw A Venn Diagram (TM) – Patrick Stevens Feb 12 '18 at 21:42
• need proof, Venn Diagram is not acceptable – Korko Feb 12 '18 at 21:43
• Venn diagrams can be converted into proofs. If you've ended up colouring in all of $A$ on your diagram, just write down why you know you've coloured in all of $A$, and that's your proof. – Patrick Stevens Feb 12 '18 at 21:44
• i won't get points on exam with just Venn diagram, need logic proof – Korko Feb 12 '18 at 21:45
• I restate: If you've ended up colouring in all of $A$ on your diagram, just write down why you know you've coloured in all of $A$, and that's your proof. – Patrick Stevens Feb 12 '18 at 21:47

\begin{align} & x \in\Big((A\setminus B) \cup (A\setminus C) \cup (A \cap B \cap C)\Big)\tag{given} \\ \\ &\iff x \in (A\setminus B) \lor x \in (A\setminus C) \lor x\in (A\cap B\cap C)\tag{1}\\ \\ &\iff (x\in A \land x \notin B) \lor (x \in A \land x \notin C) \lor (x \in A \land x \in B \land x\in C)\tag 2\\ \\ &\iff x \in A \land\big( (x\notin B \lor x\notin C) \lor (x \in B\land x\in C)\big)\tag 3\\ \\ &\iff x \in A \land \big({\lnot (x\in B \land x \in C) \lor (x \in B \land x \in C)} \big)\tag 4\\ \\ &\iff x\in A \land \underbrace{((x \notin B\cap C)\lor (x\in B\cap C))}_{\top}\tag 5\\ \\ &\iff x \in A \land (\top) \tag 6\\ \\ &\iff x\in A\tag 7 \end{align}  Note this proof is bidirectional. From $1 \to 2\to 3 \to 4 \to 5\to 6 \to 7$, and $7\to 6\to 5 \to 4 \to 3\to 2 \to 1$
In (5), $\top$ is essentially "necessarily/always true" because it is always true that any element is either in or not in any given set.