As usual, let’s start with the relevant 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.
In this case, we can find a function f, such that (x,y) ∈ R if and only if f(x) = f(y)
We can define the function as follows:
- f(x)=[x]R
Notice that this function has A as its domain. The range is the set of all equivalence classes over A defined by R.
So, the function will map each element x∈A to the equivalence class of such element defined by R: [x]R.
So, ∀x,y∈A, (x,y) ∈ R if and only if f(x) = f(y).
⧠
Notice that a relation R={(a,b)| [a]=[b]} is an equivalence relation.
Related posts:
- Let R be the relation on the set of all sets of real numbers such that SRT if and only if S and T have the same cardinality. Show that R is an equivalence relation. What are the equivalence classes of the sets {0, 1, 2} and Z?
- Define three equivalence relations on the set of students in your discrete mathematics class different from the relations discussed in the text. Determine the equivalence classes for each of these equivalence relations
- Define three equivalence relations on the set of classes offered at your school. Determine the equivalence classes for each of these equivalence relations
- Define three equivalence relations on the set of buildings on a college campus. Determine the equivalence classes for each of these equivalence relations.
- Which of these relations on the set of all functions from Z to Z are equivalence relations? Determine the properties of an equivalence relation that the others lack
