I found out that some students want to solve this type of exercise, where they need to answer if a relation is an equivalence relation, but they don’t know what an equivalence relation is. By doing this, you have a high probability of answering wrong.
So, let’s start with the definitions.
Definition: “A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.”
Definition: “A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A.”
Definition: “A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A.”
Definition: “A relation R on a set A is called transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A.”
The definitions above are from the textbook “Discrete Mathematics and its applications” By Rosen.
Now, we can solve the exercises.
Table of Contents
- a) {(0,0),(1,1),(2,2),(3,3)}
- b) {(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}
- c) {(0,0),(1,1),(1,2),(2,1),(2,2),(3,3)}
- d) {(0,0),(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3, 3)}
- e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}
a) {(0,0),(1,1),(2,2),(3,3)}
As per the definition above, to prove that a relation is an equivalence relation, we need to prove three things: (1) the relation is reflexive, (2) symmetric, and (3) transitive.
Reflexive: A={0,1,2,3}, for all a∈A (a,a)∈R. Therefore, the relation is reflexive.
Symmetric: if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. Therefore, the relation is symmetric.
Transitive: if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A. Therefore, the relation is transitive.
Because this relation is reflexive, symmetric, and transitive, we can state that the relation is an equivalence relation.
b) {(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}
Reflexive: 1∈A and (1,1)∉R. Therefore, the relation is not reflexive.
It is symmetric. You can check that if (a,b)∈R, then (b,a)∈R.
Transitive: (0,2)∈R, (2,3)∈R but (0,3)∉R. Therefore, the relation is not transitive.
The relation is not an equivalence relation because is not reflexive and not transitive.
c) {(0,0),(1,1),(1,2),(2,1),(2,2),(3,3)}
Again, let’s follow the definitions.
Reflexive: A={0,1,2,3}, for all a∈A (a,a)∈R. Therefore, the relation is reflexive.
Symmetric: if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. Therefore, the relation is symmetric.
Transitive: if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A. Therefore, the relation is transitive.
It is an equivalence relation because it is reflexive, symmetric, and transitive.
d) {(0,0),(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3, 3)}
Reflexive: A={0,1,2,3}, for all a∈A (a,a)∈R. Therefore, the relation is reflexive.
Symmetric: if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. Therefore, the relation is symmetric.
Transitive: (1,3) ∈R and (3,2)∈ R, but (1,2)∉ R. Therefore, the relation is not transitive.
It is not an equivalence relation because is not transitive.
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}
Reflexive: A={0,1,2,3}, for all a∈A (a,a)∈R. Therefore, the relation is reflexive.
Symmetric: (1,2) ∈ R and (2,1)∉R. Therefore, the relation is not symmetric.
The relation is not symmetric. Therefore, is not an equivalence relation.
Related exercises:
- Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if a + d = b + c. Show that R is an equivalence relation
- Suppose that A is a nonempty set, and f is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs (x, y) such that f (x) = f (y)
- Show that the relation of logical equivalence on the set of all compound propositions is an equivalence relation. What are the equivalence classes of F and of T?
- Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack