- \(A\cup B\) is equivalent to \(x\in A\) or \(x\in B\).
- \(A\cap B\) is equivalent to \(x\in A\) and \(x\in B\).
- \(A\backslash B\) is equivalent to \(x\in A\) and \({x}\notin B\).
- \(x\in A^{C}\) is equivalent to \(x\not\in A\).
Useful facts (the first two are called De Morgan’s Laws):
\(\begin{aligned}&\left(A\cup B\right)^C=A^C\cap B^C\\&\left(A\cap B\right)^C=A^C\cup B^C\\&\left(A^C\right)^C=A\end{aligned}\)
Equality of Sets
To prove that two sets are equal, we must show that each is the subset of the other. That is, for sets \(A \operatorname{and}B\) to show that \(A=B\) you must show that \(A\subseteq B\) and \(B\subseteq A.\)
The common strategy is to expand set operations ‘from the outside in’, then rearranging them as needed to make them fit the other side. It often helps to expand both sets to gain a better understanding of how to bridge the gap.
Example.
Prove that \((A\setminus B)\setminus(B\cup C)=A\cap B^C\cap C^C.\)
Solutions
To prove this, we must show \((A\setminus B)\setminus(B\cup C)\subseteq A\cap B^C\cap C^C\) and \(A\cap B^c\cap C^c\subseteq(A\setminus B)\setminus(B\cup C).\)
We will show \((A\setminus B)\setminus(B\cup C)\subseteq A\cap B^c\cap C^c\) first. We start with \(x\in(A\setminus B)\setminus(B\cup C)\) and want to end up with \(x\in A\cap B^C\cap C^C.\) We want to break down our statement starting with the outermost layer, the set minus. Breaking it down we get: \(x\in(A\setminus B)\) and \(x\not\in(B\cup C).\) On the left part we apply the same rule, on the right side when we distribute the \(\mathrm\notin\) charge we change the union (or) into an intersection (and):
\(x\in A\ and\ x\notin B\ and\ x\notin B\ and\ x\notin C.\) Showing the \(\in\) as complements we have \(x\in A\ and\ x\in B^{C} and\ x\in C^{C}\), then showing the ‘and’s as intersections we get \(x\in A\cap B^{c}\cap C^{c}\) as we wanted.
Now we must show \(A\cap B^C\cap C^C\subseteq(A\setminus B)\setminus(B\cup C).\) Similar to the previous part we start with \(x\in A\cap B^{c}\cap C^{c}\) and want to end up with \(x\in(A\setminus B)\setminus(B\cup C).\)
From \(x\in A\cap B^{C}\cap C^{C}\) we turn the intersections into and’s: \(x\in A\ and\ x\in B^{C} and\ x\in C^{C}\) and thus \(x\in A\ and\ x\notin B\ and\ x\not\in C_{.}\)
This looks like what we had above, so we expand:
\(x\in A\ and\ x\not\in B\ and\ x\not\in B\ and\ x\not\in C\\\left(x\in A\ and\ x\not\in B\right) and \left(x\not\in B\ and\ x\not\in C\right)\\\left(x\lfloor A\setminus B\right) and \left(x\lfloor B^{C} and\ x\lfloor C^{C}\right)\\\left(x\lfloor A\setminus B\right) and \left(x\lfloor B^{C} \complement C^{C}\right)\)
Use formula (1) from the Useful facts above:
\(\begin{gathered}
\begin{pmatrix}x\lfloor A\setminus B\end{pmatrix} and \begin{pmatrix}x\lfloor (B\lceil C)^C\end{pmatrix} \\
\left(x\in A\setminus B\right) and \left(x\not\in(B\cup C)\right) \\
x\in(A\setminus B)\setminus(B\cup C)
\end{gathered}\)
Example
Prove that \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C).\)
Solution
Again, in order to prove two sets are equal we must prove they are subsets of one another.
We will do \(A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C)\) first. Start by letting \(x\in A\cap(B\cup C).\) We break up the statement at the intersection and then at the union:
\(\begin{array}{l}x\in A\ and\ x\in B\cup C\\x\in A\ and\ (x\in B\ or\ x\in C)\end{array}\)
Here we come across an ‘or’, which we can handle in cases.
Case 1: \(x\in B\)
Then our statement becomes \(x\in A \) and \(x\in B\), which is \(x\in A\cap B.\)
Case 1: \(x\in C\)
Similarly, then our statement becomes \(x\in A \) and \(x\in C\), which is \(x\in A\cap C.\)
By our cases we can see that we have \(x\in A\cap B\ or\ x\in A\cap C\), which we can turn into a union: \(x\in(A\cap B)\cup(A\cap C).\) Thus, we’ve shown \(A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C).\)
Now we show the other direction, \((A\cap B)\cup(A\cap C)\subseteq A\cap(B\cup C) .\) Begin by letting \(x\in(A\cap B)\cup(A\cap C)\), then break up the union: \(x\in A\cap B\ or\ x\in A\cap C .\) Since we have an ‘or’, we continue using cases.
Case 1: \(x\in A\cap B\)
We can break this up at the intersection, giving \(x\in A \) and \(x\in B\)
Case 2: \(x\in A\cap C\)
Similarly, we break up the intersection into \(x\in A\) and \(x\in C\).
In both cases we have \(x\in A \), this must be true. In Case 1 we have \(x\in B\) and in Case 2 we have \(x\in C\), thus, we have \(x\in B\) or \(x\in C\). Placing these two together, we have \(x\in A\) and \(\left(x\in B\ or\ x\in C\right).\) Turn the ‘and’ into intersection and ‘or’ into union and we have \(x\in A\cap(B\cup C).\)
Therefore, we’ve shown \((A\cap B)\cup(A\cap C)\subseteq A\cap(B\cup C).\) Since we showed both inclusions, we have \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C).\)