Sets, Relations & Functions
A set is an unordered collection of distinct elements. Sets are the foundation of nearly every area of mathematics and computer science.
Set Notation
A = {1, 2, 3, 4, 5} # Roster notation
B = {x | x is even, 1≤x≤10} # Set-builder notation
ℕ = {0, 1, 2, 3, ...} # Natural numbers
ℤ = {..., -2, -1, 0, 1, 2, ...} # Integers
Set Operations
| Operation | Symbol | Meaning |
|---|
| Union | A ∪ B | Elements in A or B (or both) |
| Intersection | A ∩ B | Elements in both A and B |
| Difference | A − B | Elements in A but not B |
| Complement | Aᶜ | Elements NOT in A (relative to universe U) |
| Subset | A ⊆ B | Every element of A is in B |
| Power Set | 𝒫(A) | Set of ALL subsets of A |
Power set size: If |A| = n, then |𝒫(A)| = 2ⁿ. A set with 3 elements has 8 subsets (including ∅ and A itself).
Functions
A function f: A → B assigns exactly one element of B to each element of A.
- Injective (one-to-one): f(a₁) = f(a₂) ⟹ a₁ = a₂
- Surjective (onto): For every b ∈ B, ∃ a ∈ A such that f(a) = b
- Bijective: Both injective and surjective — a perfect pairing
Worked Example — Power Set of {a, b, c}
Start: A = {a, b, c}, |A| = 3, so |𝒫(A)| = 2³ = 8
List subsets by size 0: {∅}
Size 1: {a}, {b}, {c}
Size 2: {a,b}, {a,c}, {b,c}
Size 3: {a,b,c}
Total = 1+3+3+1 = 8 ✓
Knowledge Check
Which set operation gives elements in A OR B (or both)?
If |A| = 4, how many subsets does A have?
A ∩ B contains
A function f: A→B is injective if
A ⊆ B means