# Algebraic proof for simple set theory problem

Prove that:

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

(cmp = complement)

Now, one way to solve this is to take a small universe $U$, say $U$ = {a, b, c, d, e, f, g}, draw the Venn diagram, figure out the union-ed parts of the equation and prove it.

How can we do this purely algebraically? using the laws of sets like the idempotent law, duality, domination, absorption etc?

-
"The members of C are in A, in B or in neither of these." – Myself Jul 3 '11 at 16:54

The algebraic way to solve this is to remember that union and intersection are distributive over one another, therefore:

\begin{align} & (A^c\cap B^c\cap C) \cup (B\cap C) \cup (A\cap C) &=&(\text{un-distribute } \cap C) \\ & \Big( (A^c\cap B^c) \cup B \cup A\Big)\cap C &=&(\text{distribute }\cup B) \\ & \Big( (A\cup B)^c \cup (B\cup A)\Big)\cap C &=&(\text{de Morgan's law}) \\ & &=&C \end{align}

(As Theo suggested, using de Morgan's law shortens the proof.)

-
Thanks both of you for the insights. I've to brush up with the rules though. Doing this after a long, long time. – IntelligentMoron Jul 3 '11 at 17:30
This is a nice way of inserting reasons in a sequence of aligned equalities. – Jay Apr 26 '14 at 20:04