What is a relation?
Take a set A. Make every possible pair (a, b) from it. This big list is A × A. A relation R on A is any part (subset) of A × A. We write (a, b) ∈ R, or a R b, and say "a is related to b".
Picture it as arrows: (a, b) is an arrow from a to b.
Two special relations
- Empty relation: no pair at all. R = ∅. Example: on A = {1, 2, 3}, "a − b = 10".
- Universal relation: every pair. R = A × A. Example: on the students of one class, "a and b are in the same class".
Both of these are called trivial relations.
Reflexive, symmetric and transitive relations
Reflexive
R is reflexive if (a, a) ∈ R for every a in A. One missing loop breaks it.
Symmetric
R is symmetric if whenever (a, b) ∈ R, then (b, a) ∈ R too. Every arrow has a return arrow.
Transitive
R is transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. Every two-step path has a direct shortcut.
How to check (method)
- Reflexive: list all (a, a). Are all there?
- Symmetric: for each (a, b), look for (b, a).
- Transitive: for each pair of arrows that join end-to-start, look for the shortcut.
To show a property fails, one counter-example is enough. To show it holds, you must argue for all elements.
Equivalence relations and equivalence classes
A relation that is reflexive, symmetric and transitive is an equivalence relation. It behaves like "is the same kind as".
An equivalence relation splits A into groups called equivalence classes. The class of a is [a] = all elements related to a.
- Every element is in exactly one class.
- Two classes are either the same or have nothing in common.
- Joined together, the classes give back A.
Famous example: on the integers Z, let a R b if a − b is divisible by 2. It is an equivalence relation with two classes: the even numbers and the odd numbers.
Functions: one-one, onto and bijective
A function f: A → B is a relation where every element of A has exactly one image in B. A is the domain, B is the co-domain, and the set of actual outputs is the range.
One-one (injective)
Different inputs give different outputs. Test: assume f(x₁) = f(x₂) and show x₁ = x₂. Example: f(x) = 3x + 2 on R. If 3x₁ + 2 = 3x₂ + 2, then x₁ = x₂. So it is one-one.
Many-one: two inputs share an output. f(x) = x² on R is many-one, since f(2) = f(−2) = 4.
Onto (surjective)
Every element of B is an output. Range = co-domain. Test: take any y in B, solve y = f(x), and check that x is in A. For f(x) = 3x + 2 on R: x = (y − 2)/3 is a real number, so it is onto.
Bijective
Both one-one and onto. Only a bijection has an inverse function.
Counting tip for finite sets
If A and B each have n elements, a function A → B is one-one exactly when it is onto. The number of bijections is n!.
Try it: make your own equivalence relation
Go to the last 3D step. Start with only the three loops (1,1), (2,2), (3,3). Now add (1, 3). The readout will say it is not symmetric. Add (3, 1). What do you see? You now have classes {1, 3} and {2}.
At home: sort your family's shoes by colour. "Same colour as" is an equivalence relation. Each pile is one class. Can any shoe be in two piles?
Key formulas and definitions
- Relation on A: R ⊆ A × A
- Reflexive: (a, a) ∈ R for all a ∈ A
- Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R
- Transitive: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R
- Equivalence relation = reflexive + symmetric + transitive; class [a] = {x ∈ A : (x, a) ∈ R}
- One-one: f(x₁) = f(x₂) ⇒ x₁ = x₂
- Onto: for every y ∈ B there is x ∈ A with f(x) = y (range = co-domain)
- Bijective = one-one + onto; number of bijections between two n-element sets = n!
- Number of relations on a set with n elements = 2^(n²)
Worked examples
1. On A = {1, 2, 3}, R = {(1,1), (2,2), (3,3), (1,2)}. Check reflexive, symmetric and transitive.
Reflexive: (1,1), (2,2), (3,3) are all present, so yes. Symmetric: (1,2) is in R but (2,1) is not, so no. Transitive: the only chains are like (1,1),(1,2) → (1,2), which is present; so yes. R is reflexive and transitive but not symmetric.
2. On A = {1, 2, 3}, R = {(1,2), (2,1)}. Is R transitive?
Chain (1,2) and (2,1) needs the shortcut (1,1). It is missing. So R is not transitive. It is symmetric but not reflexive either.
3. Show that R = {(a, b) : a − b is a multiple of 4} on the integers Z is an equivalence relation. Find [0].
Reflexive: a − a = 0 = 4 × 0. Symmetric: if a − b = 4k, then b − a = 4(−k). Transitive: if a − b = 4k and b − c = 4m, add them: a − c = 4(k + m). So it is an equivalence relation. [0] = all numbers whose difference with 0 is a multiple of 4 = {…, −8, −4, 0, 4, 8, …}. There are 4 classes in total: [0], [1], [2], [3].
4. Let L be the set of all lines in a plane, and l R m if l is parallel to m or l = m. Is R an equivalence relation?
Reflexive: every line equals itself. Symmetric: if l ∥ m then m ∥ l. Transitive: if l ∥ m and m ∥ n, then l ∥ n (or l = n). Yes, it is an equivalence relation. Each class is one 'direction' of lines.
5. Is f: R → R, f(x) = 5 − 2x one-one? Is it onto?
One-one: if 5 − 2x₁ = 5 − 2x₂, then −2x₁ = −2x₂, so x₁ = x₂. Yes. Onto: take any real y. Solve y = 5 − 2x → x = (5 − y)/2, which is a real number, and f(x) = 5 − 2 × (5 − y)/2 = y. Yes. So f is bijective.
6. Is f: N → N, f(x) = x² one-one? Is it onto?
One-one: if x₁² = x₂² with x₁, x₂ natural (positive), then x₁ = x₂. Yes. Onto: 2 is in N, but no natural number squares to 2. So not onto. Note: on R the same rule is not one-one, because f(−3) = f(3). The domain matters!
7. Show that f: R → R, f(x) = x³ is bijective.
One-one: if x₁³ = x₂³, then (x₁ − x₂)(x₁² + x₁x₂ + x₂²) = 0. The second bracket is 0 only when x₁ = x₂ = 0, so in every case x₁ = x₂. Onto: for any real y, x = ∛y is real and x³ = y. So f is bijective.
8. How many relations can be defined on A = {a, b}? How many bijections from A to A?
A × A has 2 × 2 = 4 pairs. Each pair is either in R or not: 2⁴ = 16 relations. Bijections from a 2-element set to itself: 2! = 2 (the identity and the swap).
Common mistakes
- Calling a relation reflexive because some elements have loops. It needs (a, a) for EVERY a in the set.
- Thinking an empty relation cannot be symmetric or transitive. It is both, because there is no pair to break the rule (but it is not reflexive on a non-empty set).
- Forgetting the domain when testing one-one or onto. x² is one-one on N but not on R; it is onto [0, ∞) but not onto R.
- Proving onto by checking a few values. You must take a general y, solve for x, and show x lies in the domain.