1.3 Laws of the algebra of sets
Set operations obey rules much like those of ordinary algebra. For any sets \(A\), \(B\), \(C\) in a universal set \(U\):
| Name | For \(\cup \) | For \(\cap \) |
| Idempotent | \(A\cup A=A\) | \(A\cap A=A\) |
| Commutative | \(A\cup B=B\cup A\) | \(A\cap B=B\cap A\) |
| Associative | \((A\cup B)\cup C=A\cup (B\cup C)\) | \((A\cap B)\cap C=A\cap (B\cap C)\) |
| Distributive | \(A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\) | \(A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\) |
| Identity | \(A\cup \varnothing =A\) | \(A\cap U=A\) |
| \(A\cup U=U\) | \(A\cap \varnothing =\varnothing \) | |
| Complement | \(A\cup A^c=U\) | \(A\cap A^c=\varnothing \) |
| \((A^c)^c=A\) | \(U^c=\varnothing ,\ \varnothing ^c=U\) | |
| De Morgan | \((A\cup B)^c=A^c\cap B^c\) | \((A\cap B)^c=A^c\cup B^c\) |
That mirroring is called duality, and it halves the number of laws worth memorising: learn one column and swap the symbols to get the other.
Note 1.25. De Morgan’s laws in words. “Not (A or B)” means “not A and not B”; “not (A and B)” means “not A or not B”. Notice that the operation changes when the complement is taken through the bracket. Forgetting to change \(\cup \) into \(\cap \) is the usual slip.
Example 1.26. Verify De Morgan’s law \((A\cup B)^c=A^c\cap B^c\) for \[U=\{1,2,3,4,5,6,7,8\},\quad A=\{1,2,3,4\},\quad B=\{3,4,5,6\}.\]
Solution. Work out each side separately and compare.
Left-hand side. \[A\cup B=\{1,2,3,4,5,6\}\quad \implies \quad (A\cup B)^c=\{7,8\}.\]
Right-hand side. \[A^c=\{5,6,7,8\},\qquad B^c=\{1,2,7,8\}\] \[\implies \quad A^c\cap B^c=\{7,8\}.\]
Both sides give \(\{7,8\}\), so the law holds for these sets.
Remark 1.27. Checking one example does not prove a law — it only fails to disprove it. A proof would argue about an arbitrary element \(x\): if \(x\notin A\cup B\) then \(x\) is in neither \(A\) nor \(B\), so \(x\in A^c\) and \(x\in B^c\), hence \(x\in A^c\cap B^c\); and the same reasoning runs backwards. That argument covers every possible set at once, which no amount of examples can do.
Solution. Take the outer complement first, using De Morgan: \[\left (A^c\cup B\right )^c=\left (A^c\right )^c\cap B^c=A\cap B^c.\] So the expression becomes \[\left (A\cap B^c\right )\cup \left (A\cap B\right ).\] Both terms contain \(A\), so factor it out by the distributive law: \[=A\cap \left (B^c\cup B\right )=A\cap U=A.\]
The whole expression collapses to \(A\). Read on the diagram this is obvious: the first part is everything in \(A\) outside \(B\), the second is everything in \(A\) inside \(B\), and together they are all of \(A\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.