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.
So, we need to specify three relations and prove that they are reflexive, symmetric, and transitive.
The classes that are offered in the same year.
Reflexive: any class is offered in the same year as itself. Therefore, it is reflexive.
Symmetric: if class a is offered in the same year as class b, then class b is also offered in the same year as class a. Therefore, it is symmetric.
Transitive: if classes a and b are offered in the same year, and classes b and c are offered in the same year, it follows that classes a and c are offered in the same year. Therefore, it is transitive.
This relation is an equivalence relation because it is reflexive, symmetric, and transitive.
An equivalence class will consist of all the classes offered in the same year. For instance, all classes offered in year 1 will be the elements of an equivalence class.
The classes offered in a Computer Science degree.
Reflexive: any class is offered in the same degree as itself. Therefore, it is reflexive.
Symmetric: it is symmetric because both classes are offered in the CS degree.
Transitive: if class a and class b are offered in a CS degree, and classes b and c are offered in the CS degree, it follows that classes a and c are offered in the CS degree. Therefore, it is transitive.
This relation is an equivalence relation because it is reflexive, symmetric, and transitive.
An equivalence class will consist of all the classes offered in the CS Degree.
The classes offered that have the same number of students enrolled.
Reflexive: any class has the same number of students enrolled as itself. Therefore, it is reflexive.
Symmetric: it is symmetric. If class a have the same number of students than class b, then class b has the same number of students as class a.
Transitive: if class a and class b have the same number of students and class b and c have the same number of students, it follows that class a and c have the same number of students. Therefore, it is transitive.
This relation is an equivalence relation because it is reflexive, symmetric, and transitive.
An equivalence class will consist of all the classes offered that have the same number of students.
Related posts:
- Suppose that A is a nonempty set and R is an equivalence relation on A. Show that there is a function f with A as its domain such that (x,y) ∈ R if and only if f(x) = f(y)
- 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 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