2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Just Draw A Venn Diagram (TM) $\endgroup$ – Patrick Stevens Feb 12 '18 at 21:42
  • 1
    $\begingroup$ need proof, Venn Diagram is not acceptable $\endgroup$ – Korko Feb 12 '18 at 21:43
  • $\begingroup$ 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. $\endgroup$ – Patrick Stevens Feb 12 '18 at 21:44
  • $\begingroup$ i won't get points on exam with just Venn diagram, need logic proof $\endgroup$ – Korko Feb 12 '18 at 21:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Patrick Stevens Feb 12 '18 at 21:47
2
$\begingroup$

$$\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 (2), we unpack the definitions of setminus (twice), and of set intersections.

In (3), we use the distributive property.

In (4), we use the DeMorgan's

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.

$\endgroup$

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.