Subsection 2.2.2 Set identities
Proof with generic elements.
One approach is to show \(A-B \subseteq A \cap \overline{B}\) and \(A \cap\overline{B} \subseteq A - B\text{.}\) We can do this with generic elements.
Let \(x \in A - B\text{.}\) Then by definition, \(x\in A\) and \(x \not \in B\text{.}\) Then \(x \in \overline{B}\text{.}\) Since \(x \in A\) and \(x \in \overline{B}\text{,}\) we have \(x \in A \cap \overline{B}\text{.}\) Therefore \(A - B \subseteq A \cap \overline{B}\text{.}\)
Let \(x \in A \cap \overline{B}\text{.}\) Then by definition \(x\in A\) and \(x\in \overline{B}\text{.}\) Then \(x \not \in B\text{.}\) Since \(x \in A\) and \(x \not \in B\text{,}\) we have \(x \in A - B\text{.}\) Thus \(A \cap \overline{B} \subseteq A - B\text{.}\)
Therefore \(A - B = A \cap \overline{B}\text{.}\)
Proof with set builder notation and logical equivalences.
Another approach is to use set builder notation and logical equivalences.
\begin{align*}
A - B \amp = \set{x \given x \in A\land x \not \in B} \\
\amp =\set{x \given x \in A\land x \in \overline{B}} \\
\amp =\set{x \given x \in A \cap \overline{B}} \\
\amp = A \cap \overline{B}.
\end{align*}
Proof with a membership table.
Another approach is to compute a membership table , a table displaying the membership of elements in sets. The concept is similar to using truth tables to display the truth value of propositions. Use \(1\) to indicate membership in the set and \(0\) to denote the element is not in the set.
Below, we use a membership table to prove Theorem 2.2.2.1.
\begin{equation*}
\renewcommand{\arraystretch}{1.2}
\begin{array}{|*{2}{c|}|*{3}{c|}}
\hline
x\in A \amp x\in B \amp x\in\overline{B} \amp x\in A \cap \overline B \amp x\in A-B\\
\hline
1\amp 1\amp 0\amp 0\amp 0\\
1\amp 0\amp 1\amp 1\amp 1\\
0\amp 1\amp 0\amp 0\amp 0\\
0\amp 0\amp 1\amp 0\amp 0\\
\hline
\end{array}
\end{equation*}
Since the last two columns are the same, we have \(A \cap \overline{B} = A - B\text{.}\)
Remark 2.2.2.2.
When using a membership table to prove a set identity, remember to specify which columns give the desired result in the conclusion.
Theorem 2.2.2.3. Set identities I.
Let \(A\) be a set with universal set \(U\text{.}\)
- Identity laws
- Domination laws
- Idempotent laws
- Complementation law
- \(\displaystyle \overline{\overline{A}}= A\)
- Complement laws
Proof.
Exercise. Either compute membership tables and compare columns or use generic elements to show each set is a subset of the other.
Theorem 2.2.2.4. Set identities II.
Let \(A\) and \(B\) be sets.
- Commutative laws
- Absorption laws
Proof.
Exercise. Either compute membership tables and compare columns or use generic elements to show each set is a subset of the other.
Theorem 2.2.2.5. Set identities III.
Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets.
- Associative laws
- distributive laws
- \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) and \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\text{.}\)
We prove the associative law for intersection in several ways and leave the rest as an exercise. Let \(A\) and \(B\) be sets. We want to show
\begin{equation*}
(A\cap B)\cap C = A \cap (B\cap C).
\end{equation*}
Proof with generic elements.
We need to show
-
\(A \cap (B\cap C) \subseteq (A\cap B)\cap C\text{,}\) and
-
\((A\cap B)\cap C \subseteq A \cap (B\cap C)\text{.}\)
Let \(x \in A \cap (B\cap C)\text{.}\) Then \(x\) must be in \(A\) and also in \(B\cap C\text{.}\) Hence \(x\) must be in \(A\) and also in \(B\) and in \(C\text{.}\) Since \(x\) is in both \(A\) and \(B\text{,}\) we conclude that \(x \in A \cap B\text{.}\) This, together with the fact that \(x \in C\) tells us that \(x \in (A\cap B)\cap C\text{,}\) as desired.
Now we prove the other direction. (The argument is nearly identical.) Let \(x \in (A\cap B)\cap C\text{.}\) Then \(x \in A \cap B\) and also in \(C\text{.}\) Hence \(x\) is in \(A\) and \(B\) and \(C\text{.}\) Since \(x\) is in \(B\) and in \(C\text{,}\) we have that \(x \in B \cap C\text{.}\) This, together with the fact that \(x \in A\) gives \(x \in A \cap (B \cap C)\text{,}\) as desired. Therefore \(A \cap(B\cap C) = (A\cap B)\cap C\text{.}\)
Proof with a membership table.
An alternate approach is to use a membership table. Use \(1\) to indicate membership in the set and \(0\) to denote the element is not in the set. Remember to specify which columns give the desired result in the conclusion.
We compute the membership table.
\begin{equation*}
\begin{array}{|c|c|c||c|c||c|c|}
\hline
\amp \amp \amp x\in \amp x\in \amp x\in \amp x\in \\
x\in A \amp x\in B \amp x\in C \amp A \cap B \amp (A \cap B) \cap C \amp B \cap C \amp A \cap (B \cap C)\\
\hline
1\amp 1\amp 1\amp 1\amp 1\amp 1\amp 1 \\
1\amp 1\amp 0\amp 1\amp 0\amp 0\amp 0 \\
1\amp 0\amp 1\amp 0\amp 0\amp 0\amp 0 \\
1\amp 0\amp 0\amp 0\amp 0\amp 0\amp 0 \\
0\amp 1\amp 1\amp 0\amp 0\amp 1\amp 0 \\
0\amp 1\amp 0\amp 0\amp 0\amp 0\amp 0 \\
0\amp 0\amp 1\amp 0\amp 0\amp 0\amp 0 \\
0\amp 0\amp 0\amp 0\amp 0\amp 0\amp 0 \\
\hline
\end{array}
\end{equation*}
Since the 5th and 7th columns are identical, we have
\begin{equation*}
(A \cap B) \cap C = A \cap (B \cap C).
\end{equation*}
Theorem 2.2.2.6. De Morgan’s laws for sets.
Let \(A\) and \(B\) be sets.
-
\(\displaystyle \overline{A \cup B} = \overline{A} \cap \overline{B}\)
-
\(\displaystyle \overline{A \cap B} = \overline{A} \cup \overline{B}\)
Proof.
Exercise. Either compute membership tables and compare columns or use generic elements to show each set is a subset of the other.
https://xkcd.com/668/). What? Oh, no, the ’Enchanted’ soundtrack was just playing because Pandora’s algorithms are terrible. [silence] … (quietly) That’s how you knooooooow …
