# Set theory: proving of set identities

Suppose we have four sets A, B, C and X.

How can one prove the following identity:

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

I tried to apply here any of basic set identities like Distributive Law or Associative Law but it led me to nothing.

Any help would be appreciated, then.

-
Can't you just prove it by showing that if $x \in C$, then $x \in$LHS, and vice-versa? It looks like you could use DeMorgan's laws, but this might just be shorter! – Prahlad Vaidyanathan Oct 28 '13 at 11:56

Prahlad Vaidyanathan’s suggestion in the comments is probably the easiest way to go, but an algebraic proof is certainly possible. First note that $$(\neg A\cap C)\cup(\neg B\cap C)=(\neg A\cup\neg B)\cap C$$ by one of the distributive laws. Then $C\cap X=X\cap C$, and

$$\big((\neg A\cup\neg B)\cap C\big)\cup(X\cap C)=\big(\neg A\cup\neg B\cup X\big)\cap C$$

by one of the distributive laws. Thus, the original lefthand side is equal to

$$(A\cap B\cap C\cap\neg X)\cup\big((\neg A\cup\neg B\cup X)\cap C\big)\;.\tag{1}$$

Now use one of the De Morgan laws and the fact that $\neg(\neg Y)=Y$ to see that

$$\neg A\cup\neg B\cup X=\neg(A\cap B\cap\neg X)\;,$$

so that $(1)$ is equal to

$$\Big((A\cap B\cap\neg X)\cap C\Big)\cup\Big(\neg(A\cap b\cap\neg N)\cap C\Big)\;,$$

and use a distributive law to pull out the $C$ and get

$$\Big((A\cap B\cap\neg X)\cup\neg(A\cap B\cap\neg X)\Big)\cap C\;.\tag{2}$$

Finally, use the fact that $Y\cup\neg Y$ is the universal set, which I’ll call $U$, so that $(2)$ is $$U\cap C=C\;.$$

-
Just one question. How many examples must I solve to start easily decompose such identities to simple parts according to set identities laws? I didn't see all those parts, until you showed them :( – Dragon Oct 28 '13 at 12:27
@Dragon: That seems to vary enormously from one person to another. I can tell you some of what went through my mind, if that helps: every term on the lefthand side included an intersection with $C$, so in principle I could have factored $C$ out and got $$\text{ugly expression}\cap C\;.$$ This equals $C$ if and only if $\text{ugly expression}\supseteq C$. Instead of trying to deal with this all at once, I did it in smaller, simpler chunks: I just kept pulling out $C$ and combining what was left, starting with the simplest bits. – Brian M. Scott Oct 28 '13 at 12:34
Thanks a lot for detailed explanation. I need more practice for sure. – Dragon Oct 28 '13 at 12:37
@Dragon: You’re welcome. – Brian M. Scott Oct 28 '13 at 12:45
My version, explaining why each step is done: $\newcommand{\s}[2]{\\#1\quad&\quad\text{"#2"}\\\quad&}$ \begin{align}\quad& (A\cap B\cap C\cap\neg X)\cup(\neg A\cap C)\cup(\neg B\cap C)\cup(C\cap X) \s={$\cap$ is symmetric, twice; $\cap$ distributes over $\cup$ -- to factor out the ${}\cap C$ part} ((A\cap B\cap\neg X)\cup\neg A\cup\neg B\cup X)\cap C \s={DeMorgan -- to make the left hand part more symmetrical} ((A\cap B\cap\neg X)\cup\neg(A\cap B\cap\neg X))\cap C \s={simplify: a set and its complement cover the universe $U$} U\cap C \s={simplify: $U$ is the identity of $\cap$} C \end{align} – Marnix Klooster Jan 31 '15 at 19:16