🎯 Key Points
- Reflexive: (a, a) ∈ R for every a ∈ A. Symmetric: (a, b) ∈ R ⟹ (b, a) ∈ R. Transitive: (a, b), (b, c) ∈ R ⟹ (a, c) ∈ R
- An equivalence relation is all three at once; it partitions the set into disjoint equivalence classes
- One-one (injective): f(x₁) = f(x₂) ⟹ x₁ = x₂. Onto (surjective): range = codomain. Bijective: both
- For a function between two finite sets of the same size, one-one ⟺ onto — but this equivalence fails for infinite sets
- Composition: (g∘f)(x) = g(f(x)) — apply f first. Composition is associative but not commutative
- f is invertible if and only if f is bijective, and then (f⁻¹)⁻¹ = f
- (g∘f)⁻¹ = f⁻¹∘g⁻¹ — the order reverses
- The empty relation is symmetric and transitive but not reflexive (on a non-empty set); the universal relation is all three
Types of Relations
A relation R on a set A is a subset of A × A. The three properties that matter:
- Reflexive — every element relates to itself
- Symmetric — the relation never has a preferred direction
- Transitive — relations chain together
Two special cases: the empty relation R = ∅ (nothing relates to anything) and the universal relation R = A × A (everything relates to everything).
Equivalence Relations and Classes
A relation that is reflexive, symmetric and transitive is an equivalence relation. Its real power is structural: it splits A into non-overlapping equivalence classes, where [a] = { x ∈ A : (x, a) ∈ R }. Every element belongs to exactly one class, and the classes together make up all of A.
A standard example: on the integers, "a is related to b if a − b is divisible by 3" is an equivalence relation, and it produces exactly three classes — the remainders 0, 1 and 2.
Types of Functions
- One-one (injective) — distinct inputs give distinct outputs. Test: assume f(x₁) = f(x₂) and derive x₁ = x₂. Graphically, no horizontal line meets the graph twice.
- Onto (surjective) — every element of the codomain is hit, so range = codomain.
- Bijective — one-one and onto together.
Counting note: if A has m elements and B has n, the number of one-one functions A → B is nPm (needing n ≥ m), and a bijection exists only when m = n.
Composition of Functions
For f : A → B and g : B → C, the composite g∘f : A → C is defined by (g∘f)(x) = g(f(x)) — the inner function acts first. Key facts:
- Composition is associative: (h∘g)∘f = h∘(g∘f)
- It is generally not commutative: g∘f ≠ f∘g
- If f and g are both one-one, so is g∘f; if both are onto, so is g∘f
Invertible Functions
f : A → B is invertible if there exists g : B → A with g∘f = IA and f∘g = IB. Such a g is unique and is written f⁻¹.
f is invertible ⟺ f is bijective
To find f⁻¹: write y = f(x), solve for x in terms of y, then swap the names.
💡 Advanced Edge
- The three properties are independent — a relation can hold any combination. "Is perpendicular to" on lines is symmetric but neither reflexive nor transitive.
- Restricting the codomain can force ontoness: f(x) = x² is not onto as a map ℝ → ℝ, but it is onto as a map ℝ → [0, ∞).
- Restricting the domain can force injectivity: f(x) = x² is not one-one on ℝ, but is on [0, ∞) — exactly the trick used to define √x.
- On infinite sets, one-one no longer implies onto: f : ℕ → ℕ with f(n) = 2n is injective but misses every odd number.
- If g∘f is one-one then f must be one-one, but g need not be — a common exam distractor.
Example 1 — Checking an equivalence relation
Q: On ℤ, define aRb if a − b is divisible by 5. Show R is an equivalence relation.
Reflexive: a − a = 0, and 0 is divisible by 5 ✓
Symmetric: if 5 | (a − b) then 5 | (b − a), since b − a = −(a − b) ✓
Transitive: if 5 | (a − b) and 5 | (b − c), then their sum a − c is divisible by 5 ✓
Answer: R is an equivalence relation, with 5 classes — the remainders 0, 1, 2, 3 and 4.
Example 2 — One-one and onto
Q: Is f : ℝ → ℝ, f(x) = 3x + 5, bijective?
One-one: 3x₁ + 5 = 3x₂ + 5 ⟹ 3x₁ = 3x₂ ⟹ x₁ = x₂ ✓
Onto: for any y ∈ ℝ take x = (y − 5)/3, which is real and gives f(x) = y ✓
Answer: f is bijective, and f⁻¹(y) = (y − 5)/3.
Example 3 — Composition
Q: If f(x) = x + 1 and g(x) = x², find g∘f and f∘g, and comment.
Step 1 — (g∘f)(x) = g(f(x)) = g(x + 1) = (x + 1)².
Step 2 — (f∘g)(x) = f(g(x)) = f(x²) = x² + 1.
Answer: (x + 1)² and x² + 1. They differ — for instance at x = 1 they give 4 and 2 — confirming composition is not commutative.