2.6 Set complement
We finish this section by looking at the complement of sets.
Suppose that \(A\) and \(B\) are subsets of some set \(X\).
\(A\setminus B\) denotes the relative complement of \(A\) with respect to \(B\), that is \[A\setminus B=\{x\in X: \ x\in A \text{ and }x\not\in B\ \}.\]
\(A^c\) denotes the complement of \(A\), that is \[A^c=\{x\in X:\ x\not\in A\ \}.\]
Suppose \(A,B\) are subsets of a set \(X\). Then
- \(A\setminus B=A\cap B^c.\)
- \((A\setminus B)^c=A^c\cup B\).
We will prove part a. and leave part b. as an exercise.
Let \(x\in X\). Then \[\begin{align*} x\in A\setminus B &\iff (x\in A)\wedge (x\not\in B)\\ &\iff (x\in A)\wedge (x\in B^c)\\ &\iff x\in A\cap B^c. \end{align*}\] Hence, we have that \(x\in A\setminus B\) is equivalent to \(x\in A\cap B^c\). It follows that \(A\setminus B=A\cap B^c.\)□
Suppose that \(A,B,C\) are subsets of a set \(X\). Then
\(A\setminus (B\cup C)=(A\setminus B)\cap(A\setminus C).\)
\(A\setminus (B\cap C)=(A\setminus B)\cup(A\setminus C).\)
\((A\cap B)^c=A^c\cup B^c\).
\((A\cup B)^c=A^c\cap B^c\).
We will prove parts a. and d. and leave parts b. and c. as exercises.
Proving a.) Let \(x\in X\). Recall that for statements \(P,Q,R\), we have that \(P\wedge(Q\wedge R)\iff(P\wedge Q)\wedge(P\wedge R).\) Then \[\begin{align*} x\in A\setminus(B\cup C) &\iff (x\in A)\wedge(x\not\in B\cup C)\\ &\iff (x\in A)\wedge (\neg(x\in B\cup C))\\ &\iff (x\in A)\wedge (\neg((x\in B) \vee (x\in C)))\\ &\iff (x\in A)\wedge ((x\not\in B)\wedge (x\not\in C))\\ &\iff ((x\in A)\wedge (x\not\in B))\wedge((x\in A)\wedge (x\not\in C))\\ &\iff (x\in A\setminus B)\wedge(x\in A\setminus C)\\ &\iff x\in (A\setminus B)\cap(A\setminus C). \end{align*}\]
Hence, we have that \(x\in A\setminus(B\cup C)\) if and only if \(x\in(A\setminus B)\cap(A\setminus C)\). It follows that \(A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C).\)
Proving d.) Let \(x\in X\). Then \[\begin{align*} x\in (A\cup B)^c &\iff \neg(x\in A\cup B)\\ &\iff \neg((x\in A)\vee (x\in B))\\ &\iff \neg((x\in A)\wedge(\neg(x\in B)))\\ &\iff (x\in A^c)\wedge (x\in B^c)\\ &\iff x\in A^c \cap B^c. \end{align*}\]
Hence, we have that \(x\in (A\cup B)^c\) if and only if \(x\in A^c\cap B^c\). It follows that \((A\cup B)^c=A^c\cap B^c\).□
The above theorem is often known as De Morgan’s Laws, or De Morgan’s Theorem. Augustus De Morgan (English Mathematician, 1806 - 1871) was the first to write this theorem using formal logic (the one we are currently seeing). However this result was known and used by mathematicians and logicians since Aristotle (Greek philosopher, 384BC - 322BC), and can be found in the medieval texts by William of Ockham (English philosopher, 1287 - 1347) or Jean Buridan (French philosopher, 1301 - 1362).
It is often convenient to denote the elements of a set using indices. For example, suppose \(A\) is a set with \(5\) elements. Then we can denote these elements as \(a_1,a_2,a_3,a_4,a_5\). So we can write \[A=\{a_i:\ i\in I\ \}, \text{ where } I=\{1,2,3,4,5\}.\] The set \(I\) is called the indexing set.
Let \(\{A_i\}_{i\in I}\) be a collection of subsets of a set \(X\) where \(I\) is an indexing set. Then we write \(\bigcup\limits_{i\in I}A_i\) to denote the union of all the sets \(A_i\), for \(i\in I\). That is, \[\bigcup_{i\in I}A_i=\{x\in X: \exists\ i\in I \text{ such that } x\in A_i \}.\] Furthermore, we write \(\bigcap\limits_{i\in I}A_i\) to denote the intersection of all the sets \(A_i\), for \(i\in I\). That is, \[\bigcap_{i\in I}A_i=\{x\in X: \forall\ i\in I,\ x\in A_i \}.\]
Let \(X\) be a set, let \(A\) be a subset of \(X\), and let \(\{B_i\}_{i\in I}\) be an indexed collection of subsets, where \(I\) is an indexing set. Then we have
\(A\setminus \bigcap\limits_{i\in I}B_i = \bigcup\limits_{i\in I}(A\setminus B_i).\)
\(A\setminus \bigcup\limits_{i\in I}B_i = \bigcap\limits_{i\in I}(A\setminus B_i).\)
We will prove part a. and leave part b. as an exercise.
We know that \(x\in \bigcap\limits_{i\in I}B_i\) if and only if we have that \(x\in B_i\), for all \(i\in I\). Then \(x\not\in \bigcap\limits_{i\in I}B_i\) if and only if there exists an \(i\in I\) such that \(x\not\in B_i\). Now, suppose that \(x\in A\setminus \bigcap\limits_{i\in I}B_i\). Then \(x\in A\), and for some \(i\in I\), we have that \(x\not\in B_i\). Hence, for some \(i\in I\), we have that \(x\in A\setminus B_i\). Then \(x\in\bigcup\limits_{i\in I}(A\setminus B_i)\) which shows that \(A\setminus \bigcap\limits_{i\in I}B_i\,\subseteq\,\bigcup\limits_{i\in I}(A\setminus B_i).\)
Now, suppose that \(x\in \bigcup\limits_{i\in I}(A\setminus B_i).\) Hence, for some \(i\in I\), we have that \(x\in A\setminus B_i\). Then for some \(i\in I\), we have that \(x\in A\) and \(x\not\in B_i\). Since there exists some \(i\in I\) such that \(x\not\in B_i\), we have \(x\not\in \bigcap\limits_{i\in I}B_i\). Then \(x\in A\setminus \bigcap\limits_{i\in I}B_i\) which shows that \(\bigcup\limits_{i\in I}(A\setminus B_i)\,\subseteq\, A\setminus \bigcap\limits_{i\in I}B_i\). Summarising the above, we have that \(A\setminus \bigcap\limits_{i\in I}B_i\,=\,\bigcup\limits_{i\in I}(A\setminus B_i).\)□
We finish this section with a brief side-note. How does one differentiate whether a statement is a definition, a theorem, a proposition, a lemma etc? The team at Chalkdust Magazine made the following flowchart which while is not meant to be serious, does reflect quite well how one can classify different statements. That is: a definition is a statement taken to be true; roughly speaking a proposition is an interesting but non-important result; while a theorem is an interesting, important main result; and a lemma is there to build up to a theorem. The original figure can be found at https://chalkdustmagazine.com/regulars/flowchart/which-type-of-statement-are-you/
Figure 2.1: What statement are you? Copyright Chalkdust Magazine, Issue 17.