Types of relations
A relation R on a set A is a subset of A × A. Some relations have special properties.
Type | Condition | Example on the set of real numbers |
|---|---|---|
Empty | no element is related to any element | R = ∅ |
Universal | every element is related to every element | R = A × A |
Reflexive | (a, a) ∈ R for every a ∈ A | "a = b"; "a ≤ b" |
Symmetric | (a, b) ∈ R ⇒ (b, a) ∈ R | "a = b"; "a − b is an integer" |
Transitive | (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R | "a < b"; "a ≤ b" |
"a < b" is transitive but not reflexive (a < a is false) and not symmetric.
Equivalence relations
A relation that is reflexive, symmetric and transitive is an equivalence relation.
Example. On the set of integers ℤ, define a R b if a − b is divisible by 3.
Reflexive: a − a = 0 is divisible by 3. ✓
Symmetric: if 3 divides a − b, then 3 divides b − a = −(a − b). ✓
Transitive: if 3 divides a − b and b − c, it divides their sum a − c. ✓
So R is an equivalence relation.
Equivalence classes. An equivalence relation splits the set into disjoint subsets, each containing all elements related to each other. For "a − b divisible by 3", ℤ splits into three classes:
[0] = {…, −3, 0, 3, 6, …}
[1] = {…, −2, 1, 4, 7, …}
[2] = {…, −1, 2, 5, 8, …}
These classes don't overlap, and together they cover all of ℤ. Such a split is called a partition.
Example of a relation that fails. On the set of lines in a plane, "L₁ is perpendicular to L₂" is symmetric but not reflexive (no line is perpendicular to itself) and not transitive (if L₁ ⊥ L₂ and L₂ ⊥ L₃, then L₁ ∥ L₃). So it is not an equivalence relation. "L₁ is parallel to L₂" (counting each line as parallel to itself) is an equivalence relation.
Types of functions
One-one (injective). f : A → B is one-one if different elements have different images: f(x₁) = f(x₂) ⇒ x₁ = x₂.
Onto (surjective). f is onto if every element of B is the image of some element of A: the range equals the codomain.
Bijective. f is a bijection if it is both one-one and onto.
Function | One-one? | Onto? |
|---|---|---|
f : ℝ → ℝ, f(x) = 2x + 3 | yes | yes (bijective) |
f : ℝ → ℝ, f(x) = x² | no: f(−2) = f(2) | no: negative numbers aren't images |
f : ℕ → ℕ, f(x) = 2x | yes | no: odd numbers aren't images |
f : ℝ → [0, ∞), f(x) = x² | no | yes |
Checking one-one: assume f(x₁) = f(x₂) and show x₁ = x₂. For f(x) = 2x + 3: 2x₁ + 3 = 2x₂ + 3 gives x₁ = x₂. ✓
Checking onto: for any y in the codomain, solve y = f(x) and check that x lies in the domain. For f(x) = 2x + 3 on ℝ, x = (y − 3)/2 is real for every real y. ✓
For finite sets of the same size, a function is one-one if and only if it is onto.
Counting functions from A (m elements) to B (n elements): there are nᵐ functions, and if m = n, there are n! bijections.
Composition of functions
If f : A → B and g : B → C, the composition g∘f : A → C is defined by
(g∘f)(x) = g(f(x))
Apply f first, then g.
Example. f(x) = x² and g(x) = x + 1. Then (g∘f)(x) = x² + 1, but (f∘g)(x) = (x + 1)². So g∘f ≠ f∘g in general: composition is not commutative.
If f and g are both one-one, so is g∘f; if both are onto, so is g∘f.
Invertible functions
A function f : A → B is invertible if there is a function g : B → A such that g∘f = I_A and f∘g = I_B (the identity functions). Then g is the inverse of f, written f⁻¹.
A function is invertible if and only if it is a bijection.
Finding the inverse: write y = f(x), solve for x in terms of y, and swap the letters.
Example. f : ℝ → ℝ, f(x) = 4x + 3. Then y = 4x + 3 gives x = (y − 3)/4, so f⁻¹(y) = (y − 3)/4. Check: f(f⁻¹(y)) = 4 × (y − 3)/4 + 3 = y. ✓
Binary operations
A binary operation * on a set A is a function A × A → A, combining two elements to give an element of A. Addition and multiplication on ℝ are binary operations; subtraction is a binary operation on ℤ but not on ℕ (3 − 5 is not natural).
Summary
Equivalence relation = reflexive + symmetric + transitive; it partitions the set into equivalence classes.
One-one: distinct inputs give distinct outputs. Onto: range = codomain.
(g∘f)(x) = g(f(x)); composition is not commutative.
f is invertible exactly when it is a bijection.