Xjyuk

Trying to prove the following identity:

(AB) ∪ (BC) = (A∪B) (B∩C)

I worked algebraically on the expression on the left and reached:

(AB) ∪ (BC)

= (A∩B') ∪ (B ∩ C')

= ((A∩B') ∪ B) ∩ ((A∩B') ∪ C')

.

.

.

= (A∪B) (B∩C) (CA)

I couldn't find a way to show that " (CA)" 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!

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 $(Asetminus B) ∪ (Bsetminus C) = (A∪B)setminus (B∩C)$.

I'll show the first necessary condition, $(Asetminus B) ∪ (Bsetminus C) subseteq (A∪B)setminus (B∩C)$, and leave the other direction up to you.

So we begin by assuming $x in (Asetminus B) ∪ (Bsetminus 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 $xin 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:

• If $x in A setminus B$ then $x in A, xnot in B$
  


• If $x in B setminus C$ then $x in B, x not in C$
  

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, xnot 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,

$$(Asetminus B) ∪ (Bsetminus C) subseteq (A∪B)setminus (B∩C)$$

From here, you need to prove the reverse, i.e. $(A∪B)setminus (B∩C) subseteq (Asetminus B) ∪ (Bsetminus C)$ by a similar process.

This will allow you to claim equality and end the proof.

Here is a different approach, using indicator (or characteristic) functions. If the universe is $X$ and $Asubseteq X$, then the indicator function of $A$, written $1_A$ (or sometimes $chi_A$) is defined by $$1_A(x)=cases1,&$xin A$\0,&$xnotin A$$$for $xin X.$

Notice that $$beginalign
1_A^c&=1-1_A\
1_Acap B&=1_Acdot1_B\
1_Acup B&=1_A+1_B-1_Acdot1_B\
1_Acdot 1_A&=1_A
endalign
$$
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 $$beginaligna&=a1_A,\b&=1_B,\c&=1_Bendalign$$

Then the indicator function of $(Asetminus B)cup(Bsetminus 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.

Recall that,

$$ (Acup B)backslash B = (Acup B)cap B^c = (Acap B^c)cup(Bcap B^c)
= (Abackslash B)cup X = Abackslash B, $$

where $X$ is a referencial (or universe) set.

For instance, with Morgan laws you can do:

$$ (Acup B)backslash (Bcap C)
= (Acup B) cap (Bcap C)^c
= (Acup B) cap (B^ccup C^c) $$
$$ = left((Acup B)cap B^cright)bigcup left((Acup B)cap C^cright)
= (Abackslash B)bigcup ((Acup B)backslash C)$$
$$=(Abackslash B)bigcup left((Abackslash C)cup(Bbackslash C)right)
=(Abackslash B)cup (Abackslash C)cup(Bbackslash C).$$
finally, use that:

Given $A$ and $C$, we have:
$$Abackslash C subseteq (Abackslash B)cup(Bbackslash C), forall B.$$
for this reason $Abackslash C$ does not influence the whole union. Then, you have:

$$ (Abackslash B)cup (Abackslash C)cup(Bbackslash C) = (Abackslash B)cup(Bbackslash C) $$

Alternatively, here is a graphical proof: