Proving $A \cup B \cup C = (A-B)\cup(B-C)\cup(C-A)\cup(A \cap B \cap C)$ - not sure why this reasoning is failing.

Question

This seems like a fairly elementary problem but I am not sure where my reasoning is incorrect, whether it's down to a simple error in Boolean algebra or if I'm misunderstanding something else.

We want to show that

$A \cup B \cup C = (A-B)\cup(B-C)\cup(C-A)\cup(A \cap B \cap C)$.

Let $x \in A \cup B \cup C$. Then:

$(x \in A) \lor (x \in B) \lor (x \in C) \\ \leftrightarrow (x \in A \land \mathbf T) \lor (x \in B \land \mathbf T) \lor (x \in C \land \mathbf T) \\ \leftrightarrow (x \in A \land (x \in B \lor x\notin B)) \lor (x \in B \land (x \in C \lor x\notin C)) \lor (x \in C \land (x \in A \lor x\notin A)) \\ \leftrightarrow ((x \in A \land x \in B) \lor (x\in A \land x\notin B)) \lor ((x \in B \land x \in C) \lor (x\in B \land x\notin C)) \lor ((x \in C \land x \in A) \lor (x\in C \land x\notin A)) \\ \leftrightarrow (x \in A \land x \in B) \lor (x\in(A-B)) \lor (x \in B \land x \in C) \lor (x\in (B-C)) \lor (x \in C \land x \in A) \lor (x\in (C- A)) \\ \leftrightarrow x\in(A-B) \lor x\in (B-C) \lor x\in (C- A) \lor (x \in A \land x \in B) \lor(x \in B \land x \in C) \lor (x \in C \land x \in A)$

...which almost works, but obviously $(x \in A \land x \in B) \lor(x \in B \land x \in C) \lor (x \in C \land x \in A) \neq x\in A \land x\in B \land x\in C$.

I suspect I am erroneously equivocating some Boolean algebra operation onto set operations.

Answer 1

From your third line, continue:

$((x \in A \land x \in B) \lor (x\in A \land x\notin B)) \lor ((x \in B \land x \in C) \lor (x\in B \land x\notin C)) \lor ((x \in C \land x \in A) \lor (x\in C \land x\notin A)) \Leftrightarrow \text{ (removing redundant parentheses)}$

$(x \in A \land x \in B) \lor (x\in A \land x\notin B) \lor (x \in B \land x \in C) \lor (x\in B \land x\notin C) \lor (x \in C \land x \in A) \lor (x\in C \land x\notin A) \Leftrightarrow \text{ same trick you did at start!}$

$(x \in A \land x \in B \land \mathbf T) \lor (x\in A \land x\notin B) \land \mathbf T) \lor (x \in B \land x \in C \land \mathbf T) \lor (x\in B \land x\notin C \land \mathbf T) \lor (x \in C \land x \in A \land \mathbf T) \lor (x\in C \land x\notin A \land \mathbf T) \Leftrightarrow$

$(x \in A \land x \in B \land (x \in C \lor x \notin C)) \lor (x\in A \land x\notin B) \land (x \in C \lor x \notin C)) \lor (x \in B \land x \in C \land (x \in A \lor x \notin A)) \lor (x\in B \land x\notin C \land (x \in A \lor x \notin A)) \lor (x \in C \land x \in A \land (x \in B \lor x \notin B)) \lor (x\in C \land x\notin A \land (x \in B \lor x \notin B)) \Leftrightarrow$

$(x \in A \land x \in B \land x \in C) \lor (x \in A \land x \in B \land x \notin C) \lor (x\in A \land x\notin B \land x \in C) \lor (x\in A \land x\notin B \land x \notin C) \lor (x \in B \land x \in C \land x \in A) \lor (x \in B \land x \in C \land x \notin A) \lor (x\in B \land x\notin C \land x \in A) \lor (x\in B \land x\notin C \land x \notin A) \lor (x \in C \land x \in A \land x \in B) \lor (x \in C \land x \in A \land x \notin B) \lor (x\in C \land x\notin A \land x \in B) \lor (x\in C \land x\notin A \land x \notin B) \Leftrightarrow \text{ Commutation }$

$(x\in A \land x\notin B \land x \in C) \lor (x \in C \land x \in A \land x \notin B) \lor (x\in A \land x\notin B \land x \notin C) \lor (x \in A \land x \in B \land x \notin C) \lor (x\in B \land x\notin C \land x \in A) \lor (x\in B \land x\notin C \land x \notin A) \lor (x\in C \land x\notin A \land x \in B) \lor (x \in B \land x \in C \land x \notin A) \lor (x\in C \land x\notin A \land x \notin B) \lor (x \in A \land x \in B \land x \in C) \lor (x \in B \land x \in C \land x \in A) \lor (x \in C \land x \in A \land x \in B) \Leftrightarrow \text{ Removing duplicates by Idempotence }$

$(x\in A \land x\notin B \land x \in C) \lor (x\in A \land x\notin B \land x \notin C) \lor (x\in B \land x\notin C \land x \in A) \lor (x\in B \land x\notin C \land x \notin A) \lor (x\in C \land x\notin A \land x \in B) \lor (x\in C \land x\notin A \land x \notin B) \lor (x \in A \land x \in B \land x \in C) \Leftrightarrow $

$(x\in A \land x\notin B \land (x \in C \lor x \notin C)) \lor (x\in B \land x\notin C \land (x \in A \lor x \notin A)) \lor (x\in C \land x\notin A \land (x \in B \lor x \notin B)) \lor (x \in A \land x \in B \land x \in C) \Leftrightarrow $

$(x\in A \land x\notin B \land \mathbf T) \lor (x\in B \land x\notin C \land \mathbf T) \lor (x\in C \land x\notin A \land \mathbf T) \lor (x \in A \land x \in B \land x \in C) \Leftrightarrow $

$(x\in A \land x\notin B ) \lor (x\in B \land x\notin C ) \lor (x\in C \land x\notin A ) \lor (x \in A \land x \in B \land x \in C) \Leftrightarrow $

$ (x\in B - C) \lor (x\in A - B) \lor (x\in A - C) \lor (x \in A \land x \in B \land x \in C)$

Now, that's pretty lengthy ... can we shorten this?

Yes, first of all, instead of doing something like:

$x \in A \Leftrightarrow x \in A \land T \Leftrightarrow x \in A \land (x \in B \lor x \notin B) \Leftrightarrow (x \in A \land x \in B) \lor (x \in A \land x \notin B)$

there is a handy-dandy equivalence called:

Adjacency

$P \Leftrightarrow (P \land Q) \lor (P \land \neg Q)$

and with that, you can just do this in 1 step:

$x \in A \overset{Adjacency}\Leftrightarrow (x \in A \land x \in B) \lor (x \in A \land x \notin B)$

Moreover, all boolean logical rules have a perfect equivalent in set-theory, so that, for example, you also have:

$A \overset{Adjacency}= (A \cap B) \cup (A \cap B^C)$

So, while still following the same basic thought, we can do your problem as follows:

$A \cup B \cup C=$

$(A \cap B) \cup (A \cap B^C) \cup (B \cap C) \cup (B \cap C^C) \cup (C \cap A) \cup (C \cap A^C)=$

$(A \cap B \cap C) \cup (A \cap B \cap C^C) \cup (A \cap B^C \cap C) \cup (A \cap B^C \cap C^C) \cup (B \cap C \cap A) \cup (B \cap C \cap A^C) \cup (B \cap C^C \cap A) \cup (B \cap C^C \cap A^C) \cup (C \cap A \cap B) \cup (C \cap A \cap B^C) \cup (C \cap A^C \cap B) \cup (C \cap A^C \cap B^C)=$

$(A \cap B^C \cap C) \cup (C \cap A \cap B^C) \cup (A \cap B^C \cap C^C) \cup (A \cap B \cap C^C) \cup (B \cap C^C \cap A) \cup (B \cap C^C \cap A^C) \cup (C \cap A^C \cap B) \cup (B \cap C \cap A^C) \cup (C \cap A^C \cap B^C) \cup (A \cap B \cap C) \cup (B \cap C \cap A) \cup (C \cap A \cap B) =$

$(A \cap B^C \cap C) \cup (A \cap B^C \cap C^C) \cup (B \cap C^C \cap A) \cup (B \cap C^C \cap A^C) \cup (C \cap A^C \cap B) \cup (C \cap A^C \cap B^C) \cup (A \cap B \cap C) =$

$(A\cap B^C)\cup(B\cap C^C)\cup(C\cap A^C)\cup(A \cap B \cap C)=$

$(A-B)\cup(B-C)\cup(C-A)\cup(A \cap B \cap C)$

But, we can do better yet. Consider:

Reduction

$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$

which is a special case of:

Generalized Reduction

$(P \land Q) \lor (P \land \neg Q \land R) \Leftrightarrow (P \land Q) \lor (P \land R)$

With these, your identity is more quickly shown, and probably better best understood when starting with the right side:

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

$(A\cap B^C)\cup(B\cap C^C)\cup(C\cap A^C)\cup(A \cap B \cap C)\overset{Generalized Reduction}=$

$(A\cap B^C)\cup(B\cap C^C)\cup(C\cap A^C)\cup(A \cap C)\overset{Adjacency}=$

$(A\cap B^C)\cup(B\cap C^C)\cup C\overset{Reduction}=$

$(A\cap B^C)\cup B\cup C\overset{Reduction}=$

$A \cup B\cup C$

Answer 2

In showing that $[A \cup B \cup C] \subseteq [(A-B)\cup(B-C)\cup(C-A)\cup(A \cap B \cap C)],$ I would use a case system:

Case 1: $x\in(A-(B\cup C))$. Then show that $x\in A-B$.

Case 2: $x\in ((A\cap B)-C)$. Then show that $x\in B-C$.

Case 3: $x\in A\cap B\cap C$. This one's straight-forward.

Once you've done these three cases, then WLOG, you've shown the one direction to be true.

In showing that $[A \cup B \cup C] \supseteq [(A-B)\cup(B-C)\cup(C-A)\cup(A \cap B \cap C)],$ again, I would take cases. Just take each disjunct separately:

Case 1: $x\in A-B$. Then show it's in $A\cup B\cup C$. $B-C$ and $C-A$ will be similar.

Case 2: $x\in A\cap B\cap C$. Then it'll be straight-forward to show that $x\in A\cup B\cup C$.

Answer 3

You proved

$A \cup B \cup C$ =

$(A - B) \cup (B - C) \cup (C- A)$ $\cup$

$(A \cap B) \cup (B \cap C) \cup (C \cap A)$

you can make a Venn-diagram to follow this:

Let $X = A \cap B \cap C$

Then

$(A\cap B) \cup (B \cap C) \cup (C \cap A)$ =

$[((A\cap B) - X) \cup ((B \cap C) - X) \cup ((C \cap A) - X)] \cup X$ ........ (1)

We have:

$((A\cap B) - X) \subset (B - C)$ ........ (2a)

$((B\cap C) - X) \subset (C - A)$ ........ (2b)

$((C\cap A) - X) \subset (A - B)$ ........ (2c)

Therefore:

$(A - B) \cup (B - C) \cup (C - A)$ $\cup$

$(A\cap B) \cup (B \cap C) \cup (C \cap A)$ = (by (1)) =

$(A - B) \cup (B - C) \cup (C - A)$ $\cup$

$[((A\cap B) - X) \cup ((B \cap C) - X) \cup ((C \cap A) - X)] \cup X$ =

$(A - B) \cup (B - C) \cup (C - A)$ $\cup$

$[((B\cap C) - X) \cup ((C \cap A) - X) \cup ((A \cap B) - X)] \cup X$ = (by 2a,b,c) =

$(A - B) \cup (B - C) \cup (C - A) \cup X$ =

$(A - B) \cup (B - C) \cup (C - A) \cup (A \cap B \cap C)$

Conclusion:

$A \cup B \cup C$ =

$(A - B) \cup (B - C) \cup (C- A)$ $\cup$ $(A \cap B \cap C)$

Answer 4

Shesh.   Using inclusion arguments inline unneccessarily bloats the text; a source for error and confusion.

Your proof essentially boils down to:

$\def\stm{{\smallsetminus}}\begin{align}\quad & A\cup B\cup C \\ \tag 1 =~&(A \stm B)\cup(A\cap B)\,\cup\,(B\stm C)\cup(B\cap C)\,\cup\,(C\stm A)\cap (A\cap C) \\ \tag 2 =~&(A\stm B)\cup(B\stm C)\cup(C\stm A)\,\cup\,(A\cap B)\,\cup\,(B\cap C)\,\cup\,(A\cap C) \\~~~ &\text{...and from there move on to:} \\ \tag 3 =~&(A\stm B)\cup(B\stm C)\cup(C\stm A)\,\cup\,((A\cap B)\stm C)\cup((B\cap C)\stm A)\cup((A\cap C)\stm B)\,\cup\, (A\cap B\cap C) \\ \tag 4 =~&(A\stm B)\cup((A\cap C)\stm B)\,\cup\,(B\stm C)\cup((A\cap B)\stm C)\,\cup\,(C\stm A)\cup((B\cap C)\stm A)\,\cup\, (A\cap B\cap C) \\ \tag 5 =~&(A\stm B)\cup(B\stm C)\cup(C\stm A)\,\cup\, (A\cap B\cap C) \end{align}$

If you feel the need, you may use inclusion arguments to seperately prove the justifications for steps in (1), (3), and (5).

$${{(1): X=(X\stm Y)\cup(X\cap Y)\\ (2): \text{Commutation}\\ (3): (X\cap Y)=((X\cap Y)\stm Z)\cup(X\cap Y\cap Z)\text{ plus distributing the common disjunct}\\ (4) :\text{commutation and association}\\(5): (X\stm Z)\cup((X\cap Y)\stm Z)=(X\stm Z)}}$$

---

PS: Note that indeed clearly $(A\cap B)\cup(B\cap C)\cup(A\cap C)\neq A\cap B\cap C$ in general, but ... when $X\cup Y\neq Y$ you can still have $(Z\cup X)\cup (X\cup Y) =(Z\cup X)\cup Y$ .