Let’s refresh the relevant definitions for this exercise.
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.”
Definition: “Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted by [a]R. When only one relation is under consideration, we can delete the subscript R and write [a] for this equivalence class.”
[a]R ={s|(a,s)∈R}
The definitions above are from the textbook “Discrete Mathematics and its applications” By Rosen.
a) Show that R is an equivalence relation on A
Reflexive: f (x) = f (x), so (x, x) ∈ R. Therefore, the relation is reflexive.
Symmetric: (x,y) ∈ R if and only if f(x) = f(y). If f(x) = f(y) then f(y) = f(x) and (y,x) ∈R. Therefore, the relation is symmetric.
Transitive: If (x,y) ∈ R and (y,z) ∈ R, then f(x) = f(y) and f(y) = f(z). This implies that f(x) = f(z) and (x,z) ∈ R. Therefore, the relation is transitive.
The relation R is an equivalence relation because it is reflexive, symmetric, and transitive.
b) What are the equivalence classes of R?
In this case, we don’t have the definition of the function f. So, we need to express the solution using f.
The equivalence class of an element a with respect to a relation R, are all the elements that are related to a by R.
In this case, R is the relation on A consisting of all ordered pairs (x, y) such that f (x) = f (y). This means that x and y are related if both have the same image.
Then, the equivalence classes of R are:
[a]R ={a∈A|f(a)=b, for 𝑏 in the range of 𝑓}
In other words, you take one image b, and all elements from a whose image is b, are in the same equivalence relation.
When you do that for all elements of the range (all images), you will get all the equivalence classes.
Related exercises:
- Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack
- 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
- 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 {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.