1
$\begingroup$

How to prove the following equality

Let A, B and C be sets. Prove that
$\hspace{1cm}A \cup B \cup C\:= (A -B) \cup (B-C) \cup (C-A) \cup (A \cap B \cap C).$
using a chain of if and only if statements.

I tried to express set equality formula using propositional variables and connectives, solve it and then use in the solution of above equality, but I failed.

$\endgroup$
0
2
$\begingroup$

By the De Morgan's laws we obtain: $$\sum_{cyc}(A-B)+ABC=\sum_{cyc}(A(-B)+ABC)=\sum_{cyc}A(-B+BC)=$$ $$=\sum_{cyc}A(-B+B)(-B+C)=\sum_{cyc}A(-B+C)=$$ $$=\sum_{cyc}(A(-B)+AC)=\sum_{cyc}(A(-B)+AB)=\sum_{cyc}A(-B+B)=\sum_{cyc}A.$$ I used the cyclic summation.

For example, $$\sum_{cyc}(A\setminus B)=(A\setminus B)+(B\setminus C)+(C\setminus A)=(A\setminus B)\cup(B\setminus C)\cup(C\setminus A),$$ $$\sum_{cyc}(A(-B)+ABC)=$$ $$=((A\cap\overline{B})\cup (A\cap B\cap C))\cup((B\cap\overline{C})\cup (B\cap C\cap A))\cup((C\cap\overline{A})\cup (C\cap A\cap B)).$$

$\endgroup$
4
  • $\begingroup$ I have a question that is about summation symbol. What is cyc below summation symbol. What do you mean by using summation like that? Can you just provide sample extended version of one of the summations in your answer? $\endgroup$
    – Alparslan
    Oct 23 '20 at 15:09
  • $\begingroup$ @Imral I added something. See now. Sometimes thinking by cyclic summation gives very easy solutions, like you see. $\endgroup$ Oct 23 '20 at 16:20
  • $\begingroup$ thank you very much. I appreciate your work. What a beautiful solution this is. $\endgroup$
    – Alparslan
    Oct 23 '20 at 17:00
  • $\begingroup$ @Imral You are welcome! $\endgroup$ Oct 23 '20 at 17:18
1
$\begingroup$

EDIT: Oh I see you wanted if and only if statements. I guess need to say $x\in A\cup B\cup C \iff x\in A\vee x\in B\vee x\in C \iff \ldots$. But the idea can be the same.

Here is a similar proof for only two sets: $$ \begin{split} (A\setminus B) \cup (B\setminus A) \cup (A\cap B) &= (A\cap B^c) \cup (B\cap A^c) \cup (A\cap B) \\ &= (A \cap (B \cup B^c)) \cup (B\cap A^c) \\ &= A \cup (B\cap A^c) \\ &= (A\cup B)\cap (A\cup A^c) \\ &= A\cup B \end{split} $$ Line 2 is distributivity in reverse; line 4 is distributivity.

$\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.