Sets & Set Operations
Discrete Mathematics Fundamentals
Chapter 4 · Sets & Set Operations
Chapter 1 named sets as directly underlying "Python's set, JavaScript's Set, SQL's DISTINCT and UNION." This chapter covers set theory properly — what a set actually is, the notation mathematicians use for it, the core operations, and how directly each one maps onto code you've almost certainly already written.
What a Set Actually Is
A set is an unordered collection of distinct elements — no duplicates, and no built-in notion of order. {1, 2, 3} and {3, 1, 2} are the exact same set. Membership is written x ∈ A ("x is an element of A") or x ∉ A ("x is not an element of A"). The empty set, written ∅ or {}, contains no elements at all.
Set-Builder Notation — A Predicate in Disguise
{x | P(x)} reads as "the set of all x such that P(x) holds" — and P(x) is exactly Chapter 3's own predicate. A set-builder expression is literally a predicate, repurposed to define which elements belong to a set rather than to just answer true/false.
Core Set Operations
| Operation | Symbol | Meaning | Python equivalent |
|---|---|---|---|
| Union | A ∪ B | Everything in A, B, or both | A | B |
| Intersection | A ∩ B | Only what's in both A and B | A & B |
| Difference | A − B | In A, but not in B | A - B |
| Symmetric difference | A Δ B | In exactly one of A or B, not both | A ^ B |
Worked Example: Two Sets of Numbers
Let A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7}:
| Expression | Result |
|---|---|
| A ∪ B | {1, 2, 3, 4, 5, 6, 7} |
| A ∩ B | {4, 5} |
| A − B | {1, 2, 3} |
| B − A | {6, 7} |
| A Δ B | {1, 2, 3, 6, 7} |
Note that A − B and B − A are different sets — difference isn't symmetric, unlike union and intersection.
Subsets — Defined Directly by Chapter 3's Own Quantifier
A ⊆ B ("A is a subset of B") means every element of A is also in B. This has a precise quantified definition, using exactly the pattern from Chapter 3:
A ⊂ B (proper subset) adds one more condition: A ⊆ B and A ≠ B — every element of A is in B, but B has at least one element A doesn't.
Cardinality & the Power Set
Cardinality, written |A|, is simply the number of elements in a finite set — exactly what len() computes in Python. The power set, written P(A), is the set of every possible subset of A, including the empty set and A itself.
This 2^|A| result isn't a coincidence — it's a direct combinatorics fact (Chapter 9's own territory): each element independently either is or isn't in a given subset, a binary choice repeated once per element.
Sets Are Unordered and Deduplicated — Both at Once
list(set([3, 1, 2, 2, 1])) both removes duplicates (a set can't contain the same element twice by definition) and discards the original order (a set has no notion of order at all — it isn't merely "unsorted," order genuinely isn't part of what a set is). Python's own documentation is explicit that sets are unordered; the specific order you happen to see when iterating one is an implementation detail, not a guarantee, and can even change between separate runs of the same program due to hash randomization. Never rely on set iteration order for anything that needs to be reproducible.
Hands-On Exercises
Given A = {2, 4, 6, 8, 10} and B = {4, 8, 12, 16}, compute A ∪ B, A ∩ B, A − B, and B − A.
For the set A = {a, b, c}, list every element of the power set P(A) explicitly, and confirm the total matches 2^|A|. Then write out the quantified definition of A ⊆ B from memory and explain, in your own words, why it uses → rather than ∧.
A marketing team has set E (users who opted into email) and set P (users who made a purchase in the last 30 days). For each request below, name the correct set operation: (a) "everyone who purchased but hasn't opted into email," (b) "everyone who either purchased, opted in, or both," (c) "everyone who both purchased and opted in."
📄 View solutionChapter 4 Quick Reference
- A set is an unordered collection of distinct elements — no duplicates, no built-in order
- Set-builder notation
{x | P(x)}is a predicate defining membership — directly what a Python set comprehension is - ∪ union (
|), ∩ intersection (&), − difference (-), Δ symmetric difference (^) - A ⊆ B ≡ ∀x (x ∈ A → x ∈ B) — every element of A is also in B, using Chapter 3's own "every P is Q" pattern
- |A| = cardinality =
len(); P(A) = power set = every subset, with|P(A)| = 2^|A| - Converting a list to a set discards both duplicates and order — never rely on set iteration order for anything reproducible
- Next chapter: Relations — properties, equivalence relations, and partial orders