Relations and Functions · Lesson 1 of 4
Relations, Equivalence and Classes
“Learn to test relations and see how equivalence relations divide a set into meaningful groups.”
• Represent a relation using ordered pairs, a rule and relation notation. • Test reflexivity, symmetry and transitivity using proofs or counterexamples. • Recognise empty, universal and equivalence relations. • Find equivalence classes and explain why they form a partition. • Connect numerical and geometric relations to the same three property tests.
From connections to ordered pairs
A connection between two objects can often be described as a rule: two people may live in the same neighbourhood, or two triangles may have the same shape. Mathematics records such a connection using an ordered pair. Once the underlying sets and the rule are clear, we can reason about the connection without relying on an informal description.
An ordered pair (a, b) places a first and b second. The Cartesian product A × B contains every possible pair with its first entry in A and its second entry in B. A relation from A to B selects some of these pairs. For example, if A = {1, 2, 3} and B = {2, 3, 4}, the rule b = a + 1 selects (1, 2), (2, 3) and (3, 4).
A relation R from A to B is a subset of A × B. A relation on A is a subset of A × A. The statement a R b means that the ordered pair (a, b) belongs to R.
We can list the pairs in roster form or describe them in set-builder form. The rule does not have to describe a social or physical connection: any chosen subset is a relation. A function is a special relation in which every element of the declared domain has exactly one output. We will use that distinction in the next lesson.
Problem
Let A = {1, 2, 3, 4} and R = {(a, b) ∈ A × A : b = a + 1}. Write R in roster form.
- 1.For a = 1, the rule gives b = 2, and both entries belong to A. Include (1, 2).
- 2.For a = 2 and a = 3, include (2, 3) and (3, 4).
- 3.For a = 4, the rule gives b = 5. Since 5 is not in A, (4, 5) is not an allowed pair.
- 4.Therefore R = {(1, 2), (2, 3), (3, 4)}. A rule must always be used together with its declared set.
Empty and universal relations
Two extreme choices help us understand what a relation is. We may select none of the available pairs, or we may select every pair. These possibilities are called the empty and universal relations, and both are legitimate relations.
The empty relation on A contains no pairs: R = ∅.
The universal relation on A contains all allowed pairs: R = A × A.
These are sometimes called trivial relations because their membership rules have no intermediate case. On A = {1, 2, 3, 4}, the condition a − b = 10 cannot hold, so it gives an empty relation. The condition |a − b| ≥ 0 always holds, so it gives a universal relation. Absolute value is never negative.
Problem
On a set consisting only of boys in a school, consider “a is the sister of b”. Also consider the relation on school students given by “their heights differ by less than 3 metres”, under the ordinary height assumption in the example.
- 1.For the first rule, no member of the declared set can be a sister. No ordered pair satisfies the rule, so the relation is empty.
- 2.For the second rule, the stated height assumption makes every ordered pair satisfy the condition. The relation is universal.
- 3.The conclusion about a universal relation depends on the declared set and assumptions. A similar wording on a different set need not be universal.
Three tests for a relation
The next properties ask different questions about the selected pairs. Reflexivity checks each element against itself, symmetry checks the reversed pair, and transitivity checks whether two successive connections force a third. A relation may pass some tests and fail others, so each test needs its own reason.
R on A is reflexive when (a, a) belongs to R for every a in A. Every element must be related to itself.
R on A is symmetric when (a, b) in R always implies (b, a) in R. Every connection must also work in the reverse direction.
R on A is transitive when (a, b) and (b, c) in R always imply (a, c) in R. Whenever two compatible links exist, their shortcut must also exist.
To prove a property for an infinite set, reason with arbitrary elements rather than checking a few numbers. To disprove a property, one counterexample is enough. Missing one diagonal pair disproves reflexivity; finding a pair without its reverse disproves symmetry; finding two links without their shortcut disproves transitivity.
Problem
On A = {1, 2, 3}, let R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}. Classify R.
- 1.The three required diagonal pairs are present, so R is reflexive.
- 2.(1, 2) is present but (2, 1) is absent. Therefore R is not symmetric.
- 3.(1, 2) and (2, 3) are present but (1, 3) is absent. Therefore R is not transitive.
- 4.Checking the three properties separately gives a precise classification: reflexive, neither symmetric nor transitive.
Transitivity does not require all possible pairs to be present. It requires a shortcut only when both premise pairs already belong to R. Likewise, a symmetric relation does not have to relate every two elements; it must reverse the pairs that it does contain.
Problem
On the set of lines in a plane, define L₁ R L₂ when L₁ is perpendicular to L₂. Test the three properties.
- 1.A line is not perpendicular to itself, so the relation is not reflexive.
- 2.If L₁ is perpendicular to L₂, then L₂ is perpendicular to L₁. Therefore the relation is symmetric.
- 3.Take distinct parallel horizontal lines L₁ and L₃ and a vertical line L₂. We have L₁ R L₂ and L₂ R L₃, but not L₁ R L₃.
- 4.This gives a counterexample to transitivity. The relation is symmetric, neither reflexive nor transitive.
Problem
On ℝ, let a R b mean a ≤ b. Test R.
- 1.For every real a, a ≤ a, so R is reflexive.
- 2.If a ≤ b and b ≤ c, then a ≤ c. Thus R is transitive.
- 3.Although 1 ≤ 2, we do not have 2 ≤ 1. R is not symmetric.
- 4.A relation can therefore be reflexive and transitive without being symmetric.
The empty relation on a nonempty set is not reflexive, because its diagonal pairs are absent. It is symmetric and transitive: there is no selected pair or two-link chain that violates either implication. This is called vacuous truth. On the empty underlying set, even reflexivity is vacuously true because there is no element whose diagonal pair is missing. The universal relation passes all three tests on any set.
Small relations are also useful for constructing particular combinations of properties. In the following table, the underlying set is {1, 2, 3} and D = {(1, 1), (2, 2), (3, 3)}. Inspecting every possible chain is manageable on this small set; the explanation tells you which pairs matter.
| Relation on {1, 2, 3} | Properties | Reason |
|---|---|---|
| {(1, 2), (2, 1)} | Symmetric; neither reflexive nor transitive | Reverses are present, but diagonal pairs are missing. The chain 1 → 2 → 1 lacks (1, 1). |
| {(1, 2)} | Transitive; neither reflexive nor symmetric | There is no compatible two-link chain to violate transitivity. Diagonal and reverse pairs are absent. |
| D ∪ {(1, 2), (2, 1), (2, 3), (3, 2)} | Reflexive and symmetric; not transitive | All diagonal and reverse pairs are present, but the shortcut (1, 3) is missing. |
| D ∪ {(1, 2)} | Reflexive and transitive; not symmetric | Diagonal pairs and all required shortcuts exist, but (2, 1) is absent. |
| {(1, 1)} | Symmetric and transitive; not reflexive | The sole pair reverses and completes its own chain, but (2, 2) and (3, 3) are missing. |
Problem
On A = {1, 2, 3, 4, 5, 6}, let a R b mean that a divides b. Test R.
- 1.Each positive integer a divides itself because a = a × 1. Thus R is reflexive.
- 2.If a divides b and b divides c, write b = ak and c = bm for positive integers k and m. Then c = a(km), so a divides c. R is transitive.
- 3.The pair (2, 4) belongs to R, but (4, 2) does not. Therefore R is not symmetric and is not an equivalence relation.
- 4.This rule compares one integer as a divisor of the other. It differs from a fixed integer dividing their difference, which can define shared remainder classes.
Equivalence means belonging to the same group
Many useful relations describe a shared feature: triangles have the same size and shape, integers have the same parity, or books have the same number of pages. The three tests together ensure that “belonging to the same group” behaves consistently. This motivates the definition of equivalence.
An equivalence relation is a relation that is reflexive, symmetric and transitive.
Problem
Let T be the set of triangles in a plane, with T₁ R T₂ when T₁ is congruent to T₂. Show that R is an equivalence relation.
- 1.Every triangle is congruent to itself, so R is reflexive.
- 2.If T₁ is congruent to T₂, the equality of corresponding lengths and angles works in reverse. Thus T₂ is congruent to T₁, giving symmetry.
- 3.If T₁ is congruent to T₂ and T₂ to T₃, their corresponding lengths and angles agree throughout. Therefore T₁ is congruent to T₃, giving transitivity.
- 4.All three tests hold, so congruence is an equivalence relation.
Problem
On ℤ, define a R b when 2 divides a − b. Prove that R is an equivalence relation.
- 1.Reflexivity: a − a = 0 = 2 × 0, so 2 divides a − a for every integer a.
- 2.Symmetry: if a − b = 2k for an integer k, then b − a = 2(−k). Thus reversing the pair preserves divisibility.
- 3.Transitivity: if a − b = 2k and b − c = 2m, add the equalities. Then a − c = (a − b) + (b − c) = 2(k + m).
- 4.Since k + m is an integer, 2 divides a − c. R is reflexive, symmetric and transitive.
The proof shows more than a classification. Integers whose difference is even have the same parity: both are even or both are odd. An even integer and an odd integer have an odd difference, so they cannot be related by this rule. The relation therefore separates ℤ into two groups.
Equivalence classes and partitions
Once an equivalence relation is known, choose one element and collect everything related to it. The resulting group is its equivalence class. Different choices may name the same group, so the label of a class is a representative rather than a separate mathematical object.
For an equivalence relation R on X, the class [a] is the set of all b in X related to a. By symmetry we may write a R b or b R a when describing this class.
For the even-difference relation, [0] is the set of all even integers and [1] the set of all odd integers. Every even representative names [0], and every odd representative names [1]: [2r] = [0] and [2r + 1] = [1] for each integer r. The two classes are disjoint and their union is ℤ.
A partition of a set is a collection of nonempty, mutually disjoint subsets whose union is the whole set. Each element belongs to exactly one part.
Why do equivalence classes form a partition? Reflexivity puts every element in its own class, so no element is left out. If [a] and [b] share an element t, then a R t and b R t. Symmetry gives t R b, and transitivity gives a R b. Now anything related to a is also related to b, and the reverse argument gives the same inclusion the other way. Thus two classes are either identical or disjoint.
Problem
Let A = {1, 2, 3, 4, 5, 6, 7}. Define a R b when a and b are both odd or both even. Prove equivalence and find its classes.
- 1.Every a has the same parity as itself, so the relation is reflexive.
- 2.If a and b have the same parity, b and a do too, so the relation is symmetric.
- 3.If a has the same parity as b and b as c, all three have the same parity. Thus a and c are related, proving transitivity.
- 4.The distinct classes are {1, 3, 5, 7} and {2, 4, 6}. Every pair from within either class belongs to R, and no pair joining the classes belongs to R.
We can also start with a partition and create the relation “a and b lie in the same part”. Each element is in the same part as itself; the statement reverses; and two shared-part links place all three elements together. This produces an equivalence relation. The connection therefore works in both directions: equivalence relations give partitions, and partitions give equivalence relations.
Problem
Partition ℤ according to the remainder after division by 3, and identify the corresponding relation.
- 1.The three sets are A₀ = {3r : r ∈ ℤ}, A₁ = {3r + 1 : r ∈ ℤ}, and A₂ = {3r + 2 : r ∈ ℤ}. These forms also include negative integers.
- 2.Every integer has exactly one of these remainders, so the three sets are nonempty, disjoint and cover ℤ.
- 3.Two integers lie in the same set exactly when their difference is a multiple of 3. Define a R b by 3 dividing a − b.
- 4.The same divisibility proof used for 2 proves equivalence. Its classes are [0], [1], [2], with [3r + j] = [j] for j = 0, 1, 2.
Recognising the same structure in different settings
The property tests do not depend on whether the elements are numbers, books or geometric objects. What matters is the precise rule. When a rule says “has the same value of a feature”, the feature often gives a direct way to describe its equivalence classes.
Books with the same page count form classes by page count. Polygons with the same number of sides form classes of triangles, quadrilaterals and so on. Similar triangles form classes by shape, even when their sizes differ; a triangle with sides 3, 4, 5 is related to one with sides 6, 8, 10, but not to one with sides 5, 12, 13.
Points at the same distance from the origin form circles centred at the origin when the distance is positive, and the singleton containing the origin when it is zero. Lines with the same direction form a class of parallel lines, including the line itself. For a line y = 2x + 4, the class is all lines y = 2x + c, where c is real.
For the parallel-line equivalence relation, “parallel” is interpreted as having the same direction and includes a line with itself. If a rule explicitly restricts parallelism to distinct lines, reflexivity fails. Always state the intended convention before applying a property test.
Check your understanding
Use the definitions rather than the appearance of a rule. For each question, decide whether you need all diagonal pairs, reversed pairs, a two-link shortcut, or a description of an entire class.
Quiz
Which statement correctly describes a relation on A?
On A = {1, 2, 3}, which missing pair disproves reflexivity?
R = {(1, 1), (2, 2), (1, 2)} on {1, 2} is:
Which pair must be present for transitivity if (a, b) and (b, c) belong to R?
For the relation 3 divides a − b on ℤ, which integer belongs to [1]?
If two equivalence classes share one element, what follows?
What is true of the empty relation on a nonempty set?
Practice Problems
- On A = {1, 2, 3, 4}, list all pairs satisfying b = 2a, then test reflexivity, symmetry and transitivity.
- For R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)} on {1, 2, 3}, show which property fails and give the missing shortcut.
- On ℝ, test a R b defined by a ≤ b². Give a separate counterexample for each failed property.
- On {0, 1, 2, …, 12}, use the relation 4 divides a − b. Find every distinct class and the class containing 1.
- Explain why “has the same number of pages” is an equivalence relation on a set of books.
- Describe the class of a point (3, 4) under the same-distance-from-origin relation. Describe the class of the origin too.
- Construct a relation that is symmetric but neither reflexive nor transitive on {1, 2, 3}, and justify all three conclusions.
- Start with the partition {{1, 4}, {2, 3, 5}}. Write the equivalence relation it defines and explain why no cross-part pairs occur.
Key Takeaways
• A relation selects ordered pairs from a declared Cartesian product. • Reflexivity checks every diagonal pair; symmetry reverses existing pairs; transitivity completes existing two-link chains. • A proof covers arbitrary allowed elements; a counterexample disproves a universal requirement. • An equivalence relation passes all three tests and divides its set into disjoint equivalence classes. • Different representatives can name the same class, and a partition can reconstruct an equivalence relation. • The exact rule and underlying set determine the classification.
Previous
Start of chapter
Next · Lesson 2
One-One, Onto and Bijective Functions