# algebra of Sets

Prove: $[ (A \cap B) \cup C ]\cap (A^c\cup C) = C$

My attempt:

$(A\cup C)\cap(B\cup C)\cap(A^c\cup C) = C$ I used the distributive property,

but this is where I'm lost at. I think that I need to get A and $A^c$ together. So I should use the commutative property.

$(A\cup C)\cap(A^c\cup C)\cap(B\cup C) = C$ Should I distribute $(A\cup C)\cap(A^c\cup C)$?

My original post of this question was incorrect. Sorry about that.

• I think something is wrong on the LHS of the statement. Perhaps it is $(A\cup B)\cap C$ and not as it is written? – Asaf Karagila Feb 2 '11 at 6:19
• What happens if you do? Have you tried? – Mariano Suárez-Álvarez Feb 2 '11 at 6:20
• I think your first $\cup$ is supposed to be a $\cap$. Writing LHS = RHS in your work when really you're trying to manipulate LHS to show that it is equal to RHS is a bit confusing. – Jonas Meyer Feb 2 '11 at 6:21
• I did copy it down wrong.I'm going to correct it now. – lampShade Feb 2 '11 at 15:10
• To your last question-yes. If you "anti-distribute" on $(A\cup C)\cap(A^c\cup C)$ the $A$'s will disappear. Then you just have $B$ to get rid of. – Ross Millikan Feb 2 '11 at 15:17

1. What is $(A\cup C)\cap(A^c\cup C)$ ? Try finding the anwser this way: if $a \in (A\cup C)$ and $a \in (A^c\cup C)$, where must $a$ be?

2. What must $C \cap (B \cup C)$ be?

Note that the operation of intersection is associative, i.e. $(A \cap B) \cap C = A \cap (B \cap C)$.

• if a $\in (A \cup C)$ then a must be $\in (A^c \cup C)$ as well. So do I have True $\cap (B\cup C)$ now? – lampShade Feb 2 '11 at 15:31
• I think I see now. Once we establish that $a\in (A \cup C)$ then it must also be $a\in (A^c \cup C)$ this gives us $(U \cap C)$ which is C and $C\cap(B\cup C) is C$ – lampShade Feb 2 '11 at 15:41

Another pattern to look for in this problem is to -un-distribute $C$, that is pull out the $C$ from the two main parts being intersected. That is,

$$[(A\cap B)\cup C]∩(A^c\cup C) \rightarrow [((A\cap B) \cap A^c) \cup C]$$

Then you can notice something in that intersection about $A$ and $A^C$ that will eliminate that entire part not involving $C$.

Two general strategies for solving equivalence problems by just playing with the syntax is to

• rewrite to simpler things, like using an identity like distribution to reduce the length of the 'phrases' (the shortest set of things operated on). This can be very automatic (apply any identity that fits but always in one direction), but sometimes you get stuck, where you don't think you can simplify any further.
• look for patterns to undo. Here you can ignore complexity in the syntax and consider one complex part as replaced by some new variable. Then with this new variable the syntax you have might match one side of an identity you already know. This is where a little experience helps, knowing identities that might be useful.

Another strategy is to try to think of what the (convoluted) syntax -means- (for example by some visualization like a Venn diagram, or thinking of an intersection as somehow below' both the sets being intersected)

• $(A\cap B)\cap A^c)\cup C)$ everything not involving C should be the null set? Am I right? – lampShade Feb 2 '11 at 16:14
• Yes, because ...something about the A's and intersection. And then the nullset union another set is what? – Mitch Feb 4 '11 at 2:28
• Oh, reading the other answer I realize that, though my strategies are very general, there are specific strategies one can follow, and for proving set identities, one specific strategy is to show that every member of one side is a member of the other side (and vice versa). – Mitch Feb 4 '11 at 2:30

Since this is an old question, I feel comfortable giving a complete solution, instead of hints. For me, the simplest way to solve this kind of problem is to reason at the level of logic, after translating set theory definitions to the level of elements.

In this case we can calculate which elements $\;x\;$ are in the set on the left hand side by simplifying: \begin{align} & x \in [ (A \cap B) \cup C ] \cap (A^c\cup C) \\ \equiv & \;\;\;\;\;\text{"expand the definitions of $\;\cap\;$, $\;\cup\;$ (twice), $\;\cap\;$ again, and $\;^c\;$"} \\ & ((x \in A \land x \in B) \lor x \in C) \land (x \not\in A \lor x \in C) \\ \equiv & \;\;\;\;\;\text{"logic: extract common disjunct $\;x \in C\;$ out of both conjuncts"} \\ & (x \in A \land x \in B \land x \not\in A) \lor x \in C \\ \equiv & \;\;\;\;\;\text{"logic: contradiction"} \\ & (\text{false} \land x \in B) \lor x \in C \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & x \in C \\ \end{align} This completes the proof of the original statement.

$[ (A \cap B) \cup C ]\cap (A^c\cup C) = C$

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

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

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

$C \cup \emptyset = C$

$C = C$