Relation on a set
Think of the pairs "student, friend of that student" in your class. Each pair joins two people from the same group, and the whole list of such pairs is a relation.
A relation R on a set A is a subset of A × A. If (a, b) is in R we write a R b. The relation with no pair is the empty relation; the relation with every pair is the universal relation.
Formula: Number of relations on a set with n elements = 2^(n²)
Rule 1: List the pairs — Check every pair (a, b) of A × A against the rule.
- Easy: A = {1, 2, 3}, R = {(a, b) : b = a + 1} gives R = {(1, 2), (2, 3)}.
- Medium: A = {1, 2, 3, 4}, R = {(a, b) : a divides b} gives (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4): 8 pairs.
- Exam-type: A = {1, 2, 3, 4, 5, 6}, R = {(a, b) : a + b = 7} gives (1,6), (2,5), (3,4), (4,3), (5,2), (6,1): 6 pairs.
Rule 2: Empty or universal? — Test the smallest and the largest possible values.
- Easy: On A = {1, 2, 3}, R = {(a, b) : a + b < 2} is empty because the smallest sum is 2.
- Medium: On A = {1, 2, 3}, R = {(a, b) : |a − b| < 3} is universal because the largest difference is 2.
- Exam-type: A set with 3 elements has 3 × 3 = 9 pairs, and each pair is either in R or not, so there are 2^9 = 512 relations.
A relation is just a set of ordered pairs, so the order inside a pair matters: (1, 2) is not (2, 1).
Forgetting the pairs of the form (a, a) when the rule allows a = b.
n elements give n × n pairs, and every pair has two choices (in or out): 2 to the power n².
Practice questions
- 1A = {1, 2, 3}. List R = {(a, b) : a < b}.
- 2How many ordered pairs are there in A × A if A has 4 elements?
- 3A = {2, 4, 6}. List R = {(a, b) : a = b}.
- 4A = {1, 2, 3, 4}. List R = {(a, b) : b = 2a}.
- 5A = {1, 2, 3, 4, 5}. List R = {(a, b) : a − b is a multiple of 3}.
- 6On A = {1, 2, 3}, is R = {(a, b) : a + b > 6} empty, universal or neither?
- 7How many relations can be defined on a set with 2 elements?
- 8On A = {1, 2, 3}, is R = {(a, b) : a × b < 9} empty, universal or neither? Give a reason.
Show answers (try them yourself first)
- 1R = {(1, 2), (1, 3), (2, 3)}
- 216
- 3R = {(2, 2), (4, 4), (6, 6)}
- 4R = {(1, 2), (2, 4)}
- 5R = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,4), (4,1), (2,5), (5,2)}: 9 pairs
- 6Empty, because the largest sum is 3 + 3 = 6, which is not greater than 6
- 72^4 = 16
- 8Neither: (1, 1) is in R, but (3, 3) is not because 9 is not less than 9
Reflexive, symmetric and transitive relations
"Is in the same class as" works both ways and also links a student to herself. "Is taller than" does neither. Checking such habits of a relation is what we do here.
R on A is reflexive if (a, a) is in R for every a; symmetric if (a, b) in R gives (b, a) in R; transitive if (a, b) and (b, c) in R give (a, c) in R.
Formula: Reflexive: a R a. Symmetric: a R b ⇒ b R a. Transitive: a R b and b R c ⇒ a R c.
Rule 1: Test a listed relation — Check each property separately; one failing pair is enough to say no.
- Easy: A = {1, 2, 3}, R = {(1,1), (2,2), (3,3), (1,2)} is reflexive and transitive but not symmetric, because (2, 1) is missing.
- Medium: On the real numbers, a R b if a ≤ b is reflexive and transitive but not symmetric (1 ≤ 2 but 2 is not ≤ 1).
- Exam-type: On N, a R b if a divides b is reflexive and transitive but not symmetric (2 divides 4 but 4 does not divide 2).
Rule 2: Disprove with one counterexample — To say no, produce one pair or triple that breaks the property.
- Easy: On {1, 2}, R = {(1, 2)} is not reflexive and not symmetric, but it is transitive because no chain of two pairs exists.
- Medium: On the set of lines in a plane, "is perpendicular to" is symmetric only: if l ⊥ m and m ⊥ n then l is parallel to n, not perpendicular.
- Exam-type: On Z, a R b if |a − b| ≤ 1 is reflexive and symmetric but not transitive: 1 R 2 and 2 R 3 but |1 − 3| = 2.
Transitive needs a chain of two pairs; if no chain exists, the condition holds automatically.
Calling a relation symmetric because one pair has its reverse; every pair needs its reverse.
R-S-T: Self, Swap, Through (a to b to c).
Spot the difference
| Property | Meaning |
|---|---|
| Reflexive | every element is related to itself |
| Symmetric | related one way means related back |
| Transitive | a to b and b to c means a to c |
Practice questions
- 1R = {(1,1), (2,2), (3,3)} on A = {1, 2, 3}. Is R reflexive?
- 2R = {(1, 2), (2, 1)} on A = {1, 2, 3}. Is R symmetric? Is it reflexive?
- 3On N, a R b if a < b. Is R reflexive?
- 4On N, a R b if a + b is even. Check reflexive, symmetric and transitive.
- 5On the set of all people, "is taller than" is a relation. Check the three properties.
- 6R = {(1,1), (1,2), (2,1)} on A = {1, 2, 3}. Check all three properties.
- 7Give an example of a relation on {1, 2, 3} that is symmetric and transitive but not reflexive.
- 8On Z, a R b if a × b ≥ 0. Check the three properties.
Show answers (try them yourself first)
- 1Yes, all three pairs (a, a) are present
- 2Symmetric: yes. Reflexive: no, (1,1), (2,2), (3,3) are missing
- 3No, because a < a is never true
- 4All three hold: a + a is even; a + b even gives b + a even; a + b and b + c even means a, b, c have the same parity, so a + c is even
- 5Not reflexive, not symmetric, but transitive
- 6Symmetric only: (2,2) and (3,3) are missing; (2,1) and (1,2) give (2,2) which is not in R
- 7R = {(1, 1)} (other answers are possible)
- 8Reflexive and symmetric, but not transitive: 1 × 0 ≥ 0 and 0 × (−1) ≥ 0, yet 1 × (−1) < 0
Equivalence relations and equivalence classes
Grouping students by the month of their birth puts everyone in exactly one group. Equivalence relations do the same job for any set.
A relation that is reflexive, symmetric and transitive is an equivalence relation. The equivalence class of a is the set of all elements related to a. Different classes never overlap and together they cover the whole set.
Formula: [a] = {x in A : x R a}
Rule 1: Prove a relation is an equivalence — Prove the three properties one by one.
- Easy: On {1, 2, 3, 4}, R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1)} is an equivalence relation with classes {1, 2}, {3} and {4}.
- Medium: On Z, a R b if a − b is even: a − a = 0 is even; a − b even gives b − a even; (a − b) + (b − c) = a − c is even. Classes: all evens and all odds.
- Exam-type: On Z, a R b if a − b is divisible by 4: the same three steps work and there are 4 classes, [0], [1], [2] and [3].
Rule 2: Find the classes — Pick an element and collect everything related to it.
- Easy: On {1, ..., 6}, a R b if a and b leave the same remainder on division by 3: classes {1, 4}, {2, 5}, {3, 6}.
- Medium: On Z, a R b if a − b is a multiple of 3: [1] = {..., −5, −2, 1, 4, 7, ...}.
- Exam-type: On R, a R b if |a| = |b|: [3] = {3, −3} and [0] = {0}.
The classes of an equivalence relation split the set into groups with no overlap.
Checking only reflexive and symmetric and forgetting transitive.
Equivalence = "same as": same remainder, same month, same size.
Practice questions
- 1Is "has the same birth month as" an equivalence relation on the students of a class?
- 2On Z, a R b if a − b is divisible by 6. How many equivalence classes are there?
- 3On {1, 2, ..., 8}, a R b if a − b is divisible by 4. List the classes.
- 4Prove that a R b if a − b is an integer is an equivalence relation on the real numbers.
- 5R = {(1,1), (2,2), (3,3), (1,2), (2,3)} on {1, 2, 3}. Is R an equivalence relation?
- 6On Z, a R b if a² = b². Find the classes [3] and [0].
- 7Write an equivalence relation on {1, 2, 3} that has exactly 2 classes.
- 8On N × N, (a, b) R (c, d) if a × d = b × c. Is (2, 3) related to (4, 6)? Is R an equivalence relation?
Show answers (try them yourself first)
- 1Yes: same month is reflexive, symmetric and transitive
- 26 classes, [0] to [5]
- 3{1, 5}, {2, 6}, {3, 7}, {4, 8}
- 4a − a = 0 is an integer; a − b integer gives b − a integer; (a − b) + (b − c) = a − c is an integer
- 5No, it is not symmetric: (1, 2) is in R but (2, 1) is not
- 6[3] = {3, −3}, [0] = {0}
- 7R = {(1,1), (2,2), (3,3), (1,2), (2,1)}: classes {1, 2} and {3}
- 8Yes, 2 × 6 = 12 = 3 × 4. R is reflexive and symmetric; if ad = bc and cf = de then af = be (multiply and cancel c d), so R is transitive: it is an equivalence relation (equal fractions)