1.2 The Algebra of Sets

The operations \(\cup \), \(\cap \) and \('\) obey laws closely parallel to those of ordinary arithmetic, and simplification of set expressions rests on them.

Theorem 1.23 (Laws of set algebra). For any sets \(A\), \(B\), \(C\) contained in a universal set \(E\):

(i).: Commutative. \(A\cup B=B\cup A\) and \(A\cap B=B\cap A\).
(ii).: Associative. \(A\cup (B\cup C)=(A\cup B)\cup C\) and \(A\cap (B\cap C)=(A\cap B)\cap C\).
(iii).: Distributive. \[A\cap (B\cup C)=(A\cap B)\cup (A\cap C),\quad A\cup (B\cap C)=(A\cup B)\cap (A\cup C).\]
(iv).: De Morgan. \[(A\cup B)'=A'\cap B',\quad (A\cap B)'=A'\cup B'.\]
(v).: Complement. \(A\cup A'=E\), \(A\cap A'=\emptyset \), \(\emptyset \cup E=E\), \(\emptyset \cap E=\emptyset \), and \((A')'=A\).
(vi).: Absorption. If \(A\subset B\) then \(A\cap B=A\) and \(A\cup B=B\).

Note 1.24. Two of these have no arithmetic counterpart and are worth noticing. Ordinary multiplication distributes over addition, \(a(b+c)=ab+ac\), but addition does not distribute over multiplication — \(a+bc\neq (a+b)(a+c)\) in general. For sets both distributive laws hold. And De Morgan has no analogue at all in arithmetic; it is a statement about negation, and it is the law learners misremember most often.

The way to remember De Morgan is: a complement turns \(\cup \) into \(\cap \) and \(\cap \) into \(\cup \). Not being in \(A\) or \(B\) means being outside both; not being in both means being outside at least one.

Theorem 1.25 (De Morgan’s second law). For any sets \(A\) and \(B\), \((A\cap B)'=A'\cup B'\).

Proof. We show each side is a subset of the other.

Case I: \((A\cap B)'\subset A'\cup B'\). Let \(x\in (A\cap B)'\). Then \(x\notin A\cap B\), so it is not the case that \(x\) lies in both \(A\) and \(B\). Hence \(x\) fails to lie in at least one of them: \[x\notin A \quad \text {or}\quad x\notin B,\] that is, \(x\in A'\) or \(x\in B'\), and therefore \(x\in A'\cup B'\). This gives \[(A\cap B)'\subset A'\cup B' \quad \cdots \quad (1)\]

Case II: \(A'\cup B'\subset (A\cap B)'\). Conversely let \(x\in A'\cup B'\). Then \(x\in A'\) or \(x\in B'\), so \(x\notin A\) or \(x\notin B\). In either case \(x\) fails to be in both, so \(x\notin A\cap B\), that is \(x\in (A\cap B)'\). This gives \[A'\cup B'\subset (A\cap B)' \quad \cdots \quad (2)\]

From \((1)\) and \((2)\) the two sets contain each other, so \((A\cap B)'=A'\cup B'\). □

Note 1.26. The step to watch is the first one in Case I. From \(x\notin A\cap B\) it follows that \[x\notin A \quad \textbf {or}\quad x\notin B,\] not that \(x\notin A\) and \(x\notin B\). Writing “and” there is the standard slip, and it is easy to miss because the conclusion of the proof comes out looking right anyway.

Test it on a case. Take \(A=\{1,2\}\), \(B=\{2,3\}\) and \(x=1\). Then \(A\cap B=\{2\}\), so \(x\notin A\cap B\) and \(x\) belongs on the left-hand side. But \(x\in A\), so “\(x\notin A\) and \(x\notin B\)” is false. Only the “or” version survives. One example is enough to settle it, and checking a claimed implication on a single concrete case costs almost nothing.

Example 1.27. Simplify

(a).: \((X\cup Y)\cap (X\cup Y')\);
(b).: \(\left [(X\cap Y)'\cap X\right ]'\).

Solution. (a). By the second distributive law, then the complement law: \begin {align*} (X\cup Y)\cap (X\cup Y') &= X\cup (Y\cap Y')\\ &= X\cup \emptyset \\ &= X . \end {align*}

(b). By De Morgan, then \((A')'=A\), then distributing: \begin {align*} \left [(X\cap Y)'\cap X\right ]' &= (X\cap Y)''\cup X'\\ &= (X\cap Y)\cup X'\\ &= (X\cup X')\cap (Y\cup X')\\ &= E\cap (Y\cup X')\\ &= Y\cup X' . \end {align*}

Example 1.28. Let \(E=\{1,2,3,\dots ,10\}\), \(A=\{1,2,3,4,5\}\), \(B=\{2,3,5,7\}\) and \(C=\{3,4,5,6,7,8\}\). Verify that \((A\cup B)'=A'\cap B'\).

Solution. Working out each side separately, \[A\cup B=\{1,2,3,4,5,7\},\quad (A\cup B)'=\{6,8,9,10\},\] \[A'=\{6,7,8,9,10\},\quad B'=\{1,4,6,8,9,10\},\] \[A'\cap B'=\{6,8,9,10\}.\] The two sides agree, so \((A\cup B)'=\{6,8,9,10\}=A'\cap B'\) for these sets.

Note 1.29. Verifying a law on one example is not proving it. The example above confirms De Morgan for three particular sets and would not have detected a law that fails only when \(A\) and \(B\) are disjoint, say. A single example can disprove a claim, as in the note after the proof; only an argument about arbitrary \(x\) can establish one.

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.