In the previous lesson we defined what a set is. Now we learn how to combine sets to produce new sets. These combinations — union, intersection, complement, difference, symmetric difference — are the everyday verbs of mathematics, logic, and computer science.
In logic, set operations mirror the connectives: $\cup \leftrightarrow \vee$, $\cap \leftrightarrow \wedge$, $\,'\, \leftrightarrow \neg$.
In databases, SQL UNION, INTERSECT, EXCEPT are the exact same operations.
In Python, the built-in set exposes them as the operators |, &, -, ^.
Imports used throughout this lessonfrom itertools import combinations, product
from sympy import (FiniteSet, EmptySet, Union, Intersection, Complement,
Symbol, symbols, And, Or, Not, simplify, Equivalent, S)
A, B, C, D = symbols('A B C D')
2 / 24
The Universe of Discourse
Definition
A universe (or universal set) $U$ is a fixed set, agreed upon in context, containing every element under consideration. All sets in a discussion are taken to be subsets of $U$.
The universe is what makes the complement operation meaningful: without $U$ there is no "everything else". We always pick $U$ explicitly before computing complements.
Examples
For divisibility problems on small integers: $U = \{1, 2, \dots, 100\}$.
For real-analysis problems: $U = \mathbb{R}$.
For database queries: $U =$ the entire table or schema.
Two different choices of universe give two different complements. If $A = \{2,4\}$, then $A' = \{1,3,5\}$ when $U=\{1,2,3,4,5\}$ but $A' = \{1,3,5,6,7,8,9,10\}$ when $U=\{1,\dots,10\}$.
3 / 24
Union
Definition
The union of two sets $A$ and $B$ is the set of all elements that belong to $A$, to $B$, or to both:
$$A \cup B \;=\; \{\, x \mid x \in A \;\vee\; x \in B \,\}.$$
Example
$\{1,2,3\}\cup\{3,4,5\} = \{1,2,3,4,5\}$. Notice that $3$ appears in both inputs but only once in the result — sets do not record multiplicity.
N-ary union
For a family $\{A_i\}_{i\in I}$ we write $\displaystyle \bigcup_{i\in I} A_i = \{\, x \mid \exists i \in I,\; x \in A_i \,\}$.
SymPyfrom sympy import FiniteSet, Union
A = FiniteSet(1, 2, 3)
B = FiniteSet(3, 4, 5)
print(Union(A, B)) # {1, 2, 3, 4, 5}
4 / 24
Intersection
Definition
The intersection of $A$ and $B$ is the set of elements common to both:
$$A \cap B \;=\; \{\, x \mid x \in A \;\wedge\; x \in B \,\}.$$
$A$ and $B$ are disjoint iff $A \cap B = \varnothing$.
For a family: $\displaystyle \bigcap_{i\in I} A_i = \{\, x \mid \forall i\in I,\; x \in A_i \,\}$.
PythonA, B = {1, 2, 3}, {3, 4, 5}
print(A & B) # {3}
L = [{1, 2, 3}, {2, 3, 4}, {3, 4, 5}]
print(set.intersection(*L)) # {3}
Precedence reminder: $\cap$ binds tighter than $\cup$. So $A\cup B\cap C$ means $A\cup(B\cap C)$, just as $a + b\cdot c$ means $a + (b\cdot c)$.
5 / 24
Difference and Complement
Definitions
Difference: $A \setminus B = \{\, x \mid x \in A \;\wedge\; x \notin B \,\}$.
Complement (in universe $U$): $A' = A^c = \overline{A} = U \setminus A$.
Difference is asymmetric: in general $A\setminus B \neq B\setminus A$. Complement is just a "shortcut" for the difference $U\setminus A$.
Theorem
$A \setminus B = A \cap B'$.
Proof.
For any $x \in U$:
$$x \in A\setminus B \;\Leftrightarrow\; x\in A \wedge x\notin B \;\Leftrightarrow\; x\in A \wedge x\in B' \;\Leftrightarrow\; x \in A\cap B'.$$
By extensionality, $A\setminus B = A\cap B'$.
Python — three equivalent waysU = set(range(1, 11))
A = {1, 3, 5, 7, 9}
B = {2, 3, 5, 7}
print(A - B) # {1, 9} difference
print(A & (U - B)) # {1, 9} A ∩ B'
print(U - A) # {2, 4, 6, 8, 10} complement of A
6 / 24
Symmetric Difference
Definition
The symmetric difference of $A$ and $B$ is the set of elements in exactly one of them:
$$A \,\triangle\, B \;=\; (A \setminus B) \cup (B \setminus A).$$
Theorem (equivalent forms)
$A \triangle B \;=\; (A \cup B) \setminus (A \cap B) \;=\; (A \cap B') \cup (A' \cap B).$
Proof.
Using $A\setminus B = A\cap B'$ (previous slide):
$(A\setminus B)\cup(B\setminus A) = (A\cap B')\cup(B\cap A')$, which is the third form.
For the second form, note that $x \in (A\cup B)\setminus(A\cap B)$ means $x$ is in $A$ or $B$ but not in both — exactly the definition of $x \in A\triangle B$.
Theorem (properties of $\triangle$)
For all sets $A, B, C$:
$A \triangle A = \varnothing$ (self-cancelling)
$A \triangle \varnothing = A$ (identity element)
$A \triangle B = B \triangle A$ (commutative)
$(A \triangle B) \triangle C = A \triangle (B \triangle C)$ (associative)
Python — symmetric difference operator ^A, B, C = {1, 2, 3, 4}, {3, 4, 5, 6}, {5, 6, 7, 8}
print(A ^ B) # {1, 2, 5, 6}
print((A | B) - (A & B)) # same
print(A ^ A, A ^ set()) # set() ; {1,2,3,4}
print((A ^ B) ^ C == A ^ (B ^ C)) # True (associative)
7 / 24
N-ary Operations (Indexed Families)
Definition
Let $\{A_i\}_{i\in I}$ be an indexed family of sets.
$$\bigcup_{i\in I} A_i = \{\, x \mid \exists i\in I,\; x\in A_i\,\}, \qquad
\bigcap_{i\in I} A_i = \{\, x \mid \forall i\in I,\; x\in A_i\,\}.$$
When $I = \{1, 2, \dots, n\}$ we may write $A_1\cup A_2\cup\cdots\cup A_n$ or $\bigcup_{i=1}^{n} A_i$.
Theorem (generalised associativity)
Union and intersection are associative, so the expressions $A_1\cup A_2\cup\cdots\cup A_n$ and $A_1\cap\cdots\cap A_n$ are unambiguous (no parentheses needed).
Proof sketch.
For union, $x \in A_1\cup\cdots\cup A_n$ in any parenthesisation iff $\exists i,\; x\in A_i$. Since the right-hand side does not depend on the way we associate, all parenthesisations yield the same set. Same argument for intersection with $\forall$ in place of $\exists$.
Python — n-ary union and intersectionL = [{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {3, 5, 7}]
print(set().union(*L)) # {1, 2, 3, 4, 5, 7}
print(set.intersection(*L)) # {3}
# Equivalent using functools.reduce
from functools import reduce
import operator
print(reduce(operator.or_, L)) # union
print(reduce(operator.and_, L)) # intersection
8 / 24
Operator Precedence
Convention
From highest to lowest priority:
Complement $\;'$
Intersection $\;\cap$
Union $\;\cup$
Operations of equal priority associate to the left. Parentheses always override.
This mirrors the logic precedence $\neg > \wedge > \vee$, which in turn mirrors arithmetic $-\;>\;\cdot\;>\;+$.
Example
With $U=\{1..10\}$, $A=\{1,2,3\}$, $B=\{2,3,4\}$, $C=\{3,4,5\}$:
$A \cup B \cap C \;=\; A \cup (B\cap C) = \{1,2,3\}\cup\{3,4\} = \{1,2,3,4\}$.
$(A\cup B)\cap C = \{1,2,3,4\}\cap\{3,4,5\} = \{3,4\}$.
$A' \cap B \cup C \;=\; (A'\cap B)\cup C = \{4\}\cup\{3,4,5\} = \{3,4,5\}$.
Python — checking each readingU = set(range(1, 11))
A, B, C = {1,2,3}, {2,3,4}, {3,4,5}
print(A | (B & C)) # {1, 2, 3, 4}
print((A | B) & C) # {3, 4}
print(((U - A) & B) | C) # {3, 4, 5}
9 / 24
How We Prove Set Identities
Every identity in this lesson is proved by the same general technique:
Method (element-chasing)
To prove $X = Y$, show both:
$X \subseteq Y$ — pick an arbitrary $x \in X$ and deduce $x \in Y$.
$Y \subseteq X$ — pick an arbitrary $x \in Y$ and deduce $x \in X$.
Then by extensionality, $X = Y$. Often a chain of biconditionals $x\in X\Leftrightarrow\cdots\Leftrightarrow x\in Y$ does both directions at once.
Worked example — $A\cap(A\cup B) = A$ (absorption)
Proof.
"⊆": If $x \in A\cap(A\cup B)$, then in particular $x \in A$.
"⊇": If $x \in A$, then $x \in A\cup B$ (by definition of union), and $x \in A$, so $x \in A\cap(A\cup B)$.
Both inclusions hold, so $A\cap(A\cup B) = A$.
Alternatively, the chain of equivalences is:
$x \in A\cap(A\cup B) \Leftrightarrow x\in A \wedge (x\in A\vee x\in B) \Leftrightarrow x\in A$ (since $p\wedge(p\vee q)\equiv p$).
10 / 24
Set Identities — The Complete Catalogue
Identity
$A \cap U = A,\quad A \cup \varnothing = A$
Domination
$A \cup U = U,\quad A \cap \varnothing = \varnothing$
Idempotency
$A \cup A = A,\quad A \cap A = A$
Double complement
$(A')' = A$
Commutativity
$A \cup B = B \cup A,\quad A \cap B = B \cap A$
Associativity
$A\cup(B\cup C) = (A\cup B)\cup C$, $A\cap(B\cap C) = (A\cap B)\cap C$
Distributivity
$A\cup(B\cap C) = (A\cup B)\cap(A\cup C)$, $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$
Each row has two "dual" statements: swap $\cup\leftrightarrow\cap$ and $U\leftrightarrow\varnothing$ and you get the other one. This is the duality principle of Boolean algebra.
11 / 24
Proof — Distributivity of $\cap$ over $\cup$
Theorem
$A \cap (B \cup C) \;=\; (A \cap B) \cup (A \cap C).$
Proof.
For any $x$:
\begin{align*}
x \in A\cap(B\cup C)
&\Leftrightarrow x\in A \wedge (x\in B \vee x\in C) &\text{(defs of $\cap, \cup$)}\\
&\Leftrightarrow (x\in A \wedge x\in B) \vee (x\in A \wedge x\in C) &\text{(distrib. of $\wedge$ over $\vee$)}\\
&\Leftrightarrow x \in (A\cap B) \vee x\in(A\cap C)\\
&\Leftrightarrow x \in (A\cap B)\cup(A\cap C).
\end{align*}
Hence both sets contain the same elements; by extensionality they are equal.
The dual identity $A \cup (B \cap C) = (A\cup B)\cap(A\cup C)$ is proved the same way, swapping $\cap\leftrightarrow\cup$ and $\wedge\leftrightarrow\vee$.
Python — exhaustive check on $U=\{1,2,3\}$from itertools import combinations
U = {1, 2, 3}
subsets = [set(c) for r in range(len(U)+1) for c in combinations(U, r)]
count = 0
for A in subsets:
for B in subsets:
for C in subsets:
assert A & (B | C) == (A & B) | (A & C)
count += 1
print(f"Distributivity verified on {count} triples.") # 8**3 = 512
12 / 24
Proof — De Morgan's Laws
Theorem (De Morgan)
For all $A, B \subseteq U$:
$$(A \cup B)' = A' \cap B', \qquad (A \cap B)' = A' \cup B'.$$
Proof of $(A\cup B)' = A'\cap B'$.
For any $x \in U$:
\begin{align*}
x \in (A\cup B)'
&\Leftrightarrow x \notin A\cup B\\
&\Leftrightarrow \neg(x\in A \vee x\in B)\\
&\Leftrightarrow \neg(x\in A) \wedge \neg(x\in B) &\text{(De Morgan in logic)}\\
&\Leftrightarrow x \in A' \wedge x \in B'\\
&\Leftrightarrow x \in A'\cap B'.
\end{align*}
The second law follows from the first by substituting $A,B$ with $A',B'$ and using $(A')' = A$:
$(A'\cup B')' = A''\cap B'' = A\cap B$, hence $A'\cup B' = (A\cap B)'$.
Python — empirical proof on $|U|=4$ (256 pairs)from itertools import combinations
U = {1, 2, 3, 4}
S = [set(c) for r in range(5) for c in combinations(U, r)]
for A in S:
for B in S:
assert U - (A | B) == (U - A) & (U - B)
assert U - (A & B) == (U - A) | (U - B)
print("De Morgan: both laws hold for all 256 (A,B).")
13 / 24
Membership Tables — Sets ↔ Logic
A membership table is a truth table where the rows enumerate the possible cases "is element $x$ in $A$? in $B$? …". Each column shows whether $x$ belongs to a given set expression.
$A$
$B$
$A\cup B$
$A\cap B$
$A'$
$(A\cap B)'$
$A'\cup B'$
1
1
1
1
0
0
0
1
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
The last two columns are identical — this is De Morgan again, this time proved at the truth-table level.
Method
To prove $X = Y$, build the membership table for the expressions $X$ and $Y$. If the two columns are identical, the identity holds.
Python — print a membership tablefrom itertools import product
print(f"{'A':>3}{'B':>3}{'(A∩B)\\'':>10}{'A\\'∪B\\'':>10}")
for a, b in product([1, 0], repeat=2):
lhs = int(not (a and b))
rhs = int((not a) or (not b))
print(f"{a:>3}{b:>3}{lhs:>10}{rhs:>10}")
14 / 24
The Sets ↔ Logic Dictionary
Every set identity is the "shadow" of a propositional tautology. Replace the connectives according to this dictionary and you can prove either side from the other:
Set world
Logic world
$A \cup B$
$P \vee Q$
$A \cap B$
$P \wedge Q$
$A'$
$\neg P$
$A \setminus B$
$P \wedge \neg Q$
$A \triangle B$
$P \oplus Q$ (xor)
$A \subseteq B$
$P \Rightarrow Q$
$A = B$
$P \Leftrightarrow Q$
$U$ (universe)
$\top$ (true)
$\varnothing$
$\bot$ (false)
Concretely: De Morgan in logic is $\neg(P\vee Q) \equiv \neg P\wedge\neg Q$. Translate via the table and you get $(A\cup B)' = A'\cap B'$.
Worked example — streaming services
A survey of 200 people about services $N, P, D$:
$|N|=120, |P|=90, |D|=70$; $|N\cap P|=50, |N\cap D|=30, |P\cap D|=25$; $|N\cap P\cap D|=15$.
Number using at least one:
$120+90+70-50-30-25+15 = 190.$
Using none: $200-190 = 10.$
Using exactly one: $|N|+|P|+|D| - 2(|N\cap P|+|N\cap D|+|P\cap D|) + 3|N\cap P\cap D| = 280-210+45=115.$
Using exactly two: $(|N\cap P|+|N\cap D|+|P\cap D|) - 3|N\cap P\cap D| = 105-45 = 60.$
(Check: $115+60+15+10=200.$ ✓)
16 / 24
The 8 Regions of a 3-Set Venn Diagram
For three sets $A, B, C$ in a universe $U$, the Venn diagram has $2^3 = 8$ regions, one per combination "in or not in" each set. Each region is described by exactly one of:
$A$
$B$
$C$
Region (set expression)
0
0
0
$A'\cap B'\cap C'$ (outside everything)
0
0
1
$A'\cap B'\cap C$
0
1
0
$A'\cap B\cap C'$
0
1
1
$A'\cap B\cap C$
1
0
0
$A\cap B'\cap C'$
1
0
1
$A\cap B'\cap C$
1
1
0
$A\cap B\cap C'$
1
1
1
$A\cap B\cap C$ (all three)
These 8 regions partition the universe $U$: their pairwise intersection is $\varnothing$ and their union is $U$.
Python — enumerate the 8 regionsfrom itertools import product
def venn_regions(A, B, C, U=None):
U = U or (A | B | C)
regions = {}
for bits in product([0, 1], repeat=3):
sel = [(A, B, C)[i] if b else (U - (A, B, C)[i]) for i, b in enumerate(bits)]
regions[bits] = sel[0] & sel[1] & sel[2]
return regions
G, H, I = set(range(1,8)), set(range(3,10)), set(range(5,12))
for k, r in venn_regions(G, H, I).items():
print(k, "→", sorted(r))
17 / 24
Worked Example — Combining Operations
Let $G=\{1,\dots,7\}$, $H=\{3,\dots,9\}$, $I=\{5,\dots,11\}$ with universe $U = G\cup H\cup I$.
Goal
Find $(G\cup H) \cap I'$ (elements in $G$ or $H$ but not in $I$).
By hand. $G\cup H = \{1,\dots,9\}$. The complement $I' = U\setminus I = \{1,2,3,4\}$. The intersection is therefore $\{1,2,3,4\}$.
Python — confirms the calculationG = set(range(1, 8))
H = set(range(3, 10))
I = set(range(5, 12))
U = G | H | I
answer = (G | H) & (U - I)
print(sorted(answer)) # [1, 2, 3, 4]
Connection
The result equals the region where the membership pattern is "$G$ or $H$, but not $I$", which corresponds to the Venn rows $(1,0,0), (1,1,0), (0,1,0)$ from the previous slide. The union of those three regions is exactly $\{1,2\}\cup\{3,4\}\cup\varnothing = \{1,2,3,4\}$.
18 / 24
Proving Identities Computationally
For finite identities involving only $\cup,\cap,',\setminus,\triangle$, three independent techniques can be used:
Element-chasing — the rigorous mathematical proof.
Membership table — the same proof in tabular form.
Symbolic simplification (SymPy) — let the computer reduce both sides to a canonical form.
SymPy — boolean simplificationfrom sympy import symbols, And, Or, Not, simplify, Equivalent
A, B = symbols('A B')
# Absorption: A ∪ (A ∩ B) ≡ A
print(simplify(Equivalent(Or(A, And(A, B)), A))) # True
# Splitting: (A ∩ B) ∪ (A ∩ B') ≡ A
print(simplify(Equivalent(Or(And(A, B), And(A, Not(B))), A))) # True
# De Morgan: ¬(A ∩ B) ≡ ¬A ∨ ¬B
print(simplify(Equivalent(Not(And(A, B)), Or(Not(A), Not(B))))) # True
A returned value of True from SymPy means the boolean expression is a tautology — equivalently, the corresponding set identity is valid for every choice of $A, B, \dots$.
19 / 24
Property Testing with Random Inputs
For large universes a full enumeration is impractical, but a randomised check is still convincing. Inclusion–exclusion is a great target:
Python — verify |A ∪ B| = |A| + |B| − |A ∩ B| on 1000 random pairsimport random
random.seed(42)
U = list(range(1, 21)) # universe {1..20}
def random_subset():
return {x for x in U if random.random() < 0.5}
for _ in range(1000):
A, B = random_subset(), random_subset()
assert len(A | B) == len(A) + len(B) - len(A & B)
print("Inclusion–Exclusion holds on 1000 random (A, B).")
Cautionary remark
Random testing builds confidence but is not a proof — only the element-chasing argument from the previous slides is. Use random tests to find counter-examples, and proofs to confirm.
20 / 24
The Algebra of Sets — A Boolean Algebra
Let $U$ be a fixed universe. The collection $\mathcal{P}(U)$ of all subsets of $U$, together with the operations $\cup, \cap, '$ and the constants $\varnothing, U$, forms a structure called a Boolean algebra.
Definition
A Boolean algebra $(B, \vee, \wedge, ', 0, 1)$ is a set $B$ with two binary operations, one unary operation and two distinguished elements satisfying: commutativity, associativity, distributivity (both ways), identity ($x\vee 0 = x,\; x\wedge 1 = x$), and complement ($x\vee x' = 1,\; x\wedge x' = 0$).
Theorem
$(\mathcal{P}(U), \cup, \cap, ', \varnothing, U)$ is a Boolean algebra.
Proof sketch.
All ten axioms are exactly the identities of Slide 11, which we have either proved (or can prove) by element-chasing.
Propositional logic forms another Boolean algebra $(\{\top,\bot\}, \vee, \wedge, \neg, \bot, \top)$. The Sets ↔ Logic dictionary of Slide 15 is an isomorphism of Boolean algebras — that is the deep reason set identities and logical equivalences look identical.
21 / 24
Worked Example — Simplifying an Expression
Problem
Show that
$$\bigl[(A\cap B)\cup C\cup D\bigr] \cap (B'\cup C) \;\equiv\; (B'\cap D) \cup C.$$
By absorption, $C \cap (B'\cup C) = C$. The first bracket simplifies because $A\cap B\cap B' = \varnothing$, leaving $A\cap B\cap C$, which is absorbed into $C$. The third bracket is $(D\cap B')\cup(D\cap C)$; the second part $D\cap C$ is again absorbed into $C$. The remainder is $C \cup (B'\cap D)$. $\;\Box$
Approach 2 — exhaustive truth-table check
Python — 16 truth assignmentsfrom itertools import product
def lhs(a, b, c, d): return (((a and b) or c or d) and ((not b) or c))
def rhs(a, b, c, d): return ((not b) and d) or c
ok = all(lhs(*v) == rhs(*v) for v in product([True, False], repeat=4))
print("Equivalent?", ok) # True
SymPy — same identity, fully symbolicfrom sympy import symbols, And, Or, Not, simplify, Equivalent
A, B, C, D = symbols('A B C D')
L = And(Or(And(A, B), C, D), Or(Not(B), C))
R = Or(And(Not(B), D), C)
print(simplify(Equivalent(L, R))) # True
22 / 24
Summary — What You Now Know
Union $A\cup B$, intersection $A\cap B$, complement $A'$, difference $A\setminus B$, symmetric difference $A\triangle B$ — six core operations defined via $\in$ and the logical connectives.
Precedence: $\,' \;>\; \cap \;>\; \cup$.
Element-chasing is the universal proof technique. Membership tables and SymPy give two complementary checks.
The 10 fundamental identities (identity, domination, idempotency, commutativity, associativity, distributivity, De Morgan, absorption, complement, double complement) make $\mathcal{P}(U)$ into a Boolean algebra, isomorphic to propositional logic.
Inclusion–Exclusion: $|A\cup B| = |A|+|B|-|A\cap B|$ and its 3-set generalisation — the basis of counting arguments.
The 8-region Venn partition of a 3-set universe gives a complete picture and turns abstract set algebra into a visual exercise.
Prove the second distributive law $A\cup(B\cap C) = (A\cup B)\cap(A\cup C)$ by element-chasing.
Generalise venn_regions to $n$ sets — there are $2^n$ regions.
Prove $A\triangle B = (A\cap B')\cup(A'\cap B)$ symbolically with SymPy.
Bridges to other lessons
The next lesson "Relations and Functions" defines a relation as a subset of $A\times B$ — every operation we just learned will be re-used on these subsets. The "Sequences and Series" lesson will then use Inclusion–Exclusion to count finite sequences satisfying multiple constraints.
The cleanest way to remember any set identity: write it in logic via the dictionary, prove the logical tautology by a 2- or 4-row truth table, then translate back. The two worlds are the same Boolean algebra in different costumes.