Trying to prove the following identity:
(A\B) ∪ (B\C) = (A∪B) \ (B∩C)
I worked algebraically on the expression on the left and reached:
(A\B) ∪ (B\C)
= (A∩B') ∪ (B ∩ C')
= ((A∩B') ∪ B) ∩ ((A∩B') ∪ C')
.
.
.
= (A∪B) \ (B∩C) \ (C\A)
I couldn't find a way to show that "\ (C\A)" has no influence on the whole expression, even though it is true.
I also tried manipulating the other side of the equation, but with no luck.
Thanks for your help!
On
Recall that,
$$ (A\cup B)\backslash B = (A\cup B)\cap B^{c} = (A\cap B^{c})\cup(B\cap B^{c}) = (A\backslash B)\cup X = A\backslash B, $$
where $X$ is a referencial (or universe) set.
For instance, with Morgan laws you can do:
$$ (A\cup B)\backslash (B\cap C) = (A\cup B) \cap (B\cap C)^{c} = (A\cup B) \cap (B^{c}\cup C^{c}) $$ $$ = \left((A\cup B)\cap B^{c}\right)\bigcup \left((A\cup B)\cap C^{c}\right) = (A\backslash B)\bigcup ((A\cup B)\backslash C)$$ $$=(A\backslash B)\bigcup \left((A\backslash C)\cup(B\backslash C)\right) =(A\backslash B)\cup (A\backslash C)\cup(B\backslash C).$$ finally, use that:
Given $A$ and $C$, we have:
$$A\backslash C \subseteq (A\backslash B)\cup(B\backslash C),\ \forall B.$$
for this reason $A\backslash C$ does not influence the whole union. Then, you have:
$$ (A\backslash B)\cup (A\backslash C)\cup(B\backslash C) = (A\backslash B)\cup(B\backslash C) $$
On
Here is a different approach, using indicator (or characteristic) functions. If the universe is $X$ and $A\subseteq X$, then the indicator function of $A$, written $1_A$ (or sometimes $\chi_A$) is defined by $$1_A(x)=\cases{1,&$x\in A$\\0,&$x\notin A$}$$for $x\in X.$
Notice that $$\begin{align} 1_{A^c}&=1-1_A\\ 1_{A\cap B}&=1_A\cdot1_B\\ 1_{A\cup B}&=1_A+1_B-1_A\cdot1_B\\ 1_A\cdot 1_A&=1_A \end{align} $$ The last equation is true because $1_A$ only takes the values $0$ and $1$.
Obviously, two sets are the same if and only if they have the same indicator function. Once you have become familiar with this idea, proofs like this become easy. I'll write $$\begin{align}a&=1_A,\\b&=1_B,\\c&=1_C\end{align}$$
Then the indicator function of $(A\setminus B)\cup(B\setminus C)$ is $$ a(1-b)+b(1-c)-a(1-b)b(1-c)=a-ab+b-bc$$ because $$(1-b)b=b-b^2=b-b=0$$ The indicator function of the right-hand side is $$(a+b-ab)(1-bc)=a-abc+b-b^2c-ab+abc=a+b-bc-ab$$ and we see that the two functions are identical.
On
Using the algebraic approach you get for the LHS:
$$(A\setminus B) \cup (B\setminus C) =$$
$$(A \cap B') \cup (B \cap C')=$$
$$((A \cap B')\cup B) \cap ((A \cap B')\cup C')=$$
$$(A \cup B) \cap (A \cup C') \cap (B' \cup C')$$
while for the RHS you get:
$$(A\cup B) \setminus (B\cap C)=$$
$$(A\cup B) \cap (B\cap C)'=$$
$$(A\cup B) \cap (B' \cup C')$$
So, here is your question: we get a $A \cup C'$ term in the LHS that we don't have in the RHS. So, are they really equal? And if so, how would we show that? How can we get rid of that extra term?
Well, note that $A \cup C'=(A \cup C' \cup B) \cap (A \cup C' \cup B')$, and so applying this to the LHS:
$$(A \cup B) \cap (A \cup C') \cap (B' \cup C')=$$
$$(A \cup B) \cap (A \cup C'\cup B) \cap (A \cup C'\cup B') \cap (B' \cup C')=$$
$$(A\cup B) \cap (B' \cup C')$$
because $(A \cup B) \cap (A \cup C'\cup B)=(A \cup B)$ and $(A \cup C'\cup B') \cap (B' \cup C')=(B' \cup C')$
The fact that we can get rid of this third term is actually a well-known equivalence principle, known as the Consensus Theorem
In my opinion, the easiest way to show, for sets $A,B$, that $A=B$ is that you show $A \subseteq B$ and $B \subseteq A$. That is, to show the equality, you would show $x \in A \implies x \in B$ and $x \in B \implies x \in A$.
So, we want to show that $(A\setminus B) ∪ (B\setminus C) = (A∪B)\setminus (B∩C)$.
I'll show the first necessary condition, $(A\setminus B) ∪ (B\setminus C) \subseteq (A∪B)\setminus (B∩C)$, and leave the other direction up to you.
So we begin by assuming $x \in (A\setminus B) ∪ (B\setminus C)$. We want to, in effect, "unravel" what this means, in the sense that we want to figure out which of $A,B,C$ the element $x$ is a member of.
From the definition of the union of sets, $x \in P \cup Q$ would mean either $x \in P$ or $x \in Q$ or possibly both. Thus, we conclude $x\in A \setminus B$ or $x \in B \setminus C$. Since at least one of the two must hold, everything that follows has to be taken by cases.
Similarly, from the definition of set difference, if $x \in P \setminus Q$ then $x \in P$ and $x \not \in Q$. From this, we conclude:
This is all we can say at this point. In the first case, we don't know if $x$ is in $C$, and similarly for $x$ and $A$ in the second case.
We handle each case separately at this point as we try to construct the right-hand side of the equality we want to prove.
Case 1: Suppose $x \in A, x\not \in B$, and $C$ is a set which $x$ may or may not be in. Since $x \in A$, then $x \in A \cup B$. Since $x \not \in B$, then $x \not \in B \cap C$ (since $x$ must be in both to be in the intersection). Then from the definition of set difference, $x$ is in the set difference of this union and intersection noted; that is, $x \in (A \cup B) \setminus (B \cap C)$, the result desired.
Case 2: This follows much the same logic as the previous. Suppose $x \in B, x \not \in C$, and $A$ is a set which $x$ may or may not be in. Since $x \in B$, then $x \in A \cup B$. Since $x \not \in C$, $x \not \in B \cap C$. As a consequence, we have $x \in (A \cup B) \setminus (B \cap C)$, the result desired.
Both cases lead to the result we want, and thus we conclude our initial assumption implies $x \in (A∪B)\setminus (B∩C)$. In turn, thus,
$$(A\setminus B) ∪ (B\setminus C) \subseteq (A∪B)\setminus (B∩C)$$
From here, you need to prove the reverse, i.e. $(A∪B)\setminus (B∩C) \subseteq (A\setminus B) ∪ (B\setminus C)$ by a similar process.
This will allow you to claim equality and end the proof.