Below are the relevant definitions that we need to know to solve 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.”
The definitions above are from the textbook “Discrete Mathematics and its applications” By Rosen.
Table of Contents
- a) {(f,g)|f(1)=g(1)}
- b) {(f,g) | f(0) = g(0) or f(1) = g(1)}
- c) {(f,g)|f(x)−g(x)=1 for all x∈Z}
- d) {(f,g)| for some C∈Z, for all x∈Z,f(x)−g(x) = C}
- e) {(f,g) | f(0) = g(1) and f(1) = g(0)}
a) {(f,g)|f(1)=g(1)}
Reflexive: the pair (f,f) ∈R as f(1)=f(1). Therefore, the relation is reflexive.
Symmetric: The relation is symmetric because (f,g)∈R if f(1)=g(1), and if f(1)=g(1) then g(1)=f(1).
Transitive: if f(1)=g(1), and g(1)=h(1), then f(1)=h(1). Therefore, the relation is transitive.
This is an Equivalence relation because it is reflexive, symmetric, and transitive.
b) {(f,g) | f(0) = g(0) or f(1) = g(1)}
Reflexive: the pair (f,f) ∈R as f(0)=f(0). Therefore, the relation is reflexive.
Symmetric: The relation is symmetric because (f,g)∈R if f(0) = g(0) or f(1)=g(1), and if f(0)=g(0) then g(0)=f(0). Also, if f(1)=g(1) then g(1)=f(1).
Transitive: if f(0)=g(0), (f,g)∈R. If g(1)=h(1), then (g,h)∈R. However, it might be the case that f(0)≠h(0) and f(1)≠h(1). In this case, (f,h)∉R. Therefore, the relation is not transitive.
This is not an equivalence relation because it is not transitive.
c) {(f,g)|f(x)−g(x)=1 for all x∈Z}
Reflexive: for all x∈Z, f(x)-f(x)=0, by definition of a function. Therefore, the relation is not reflexive.
Symmetric: f(x)-g(x)≠g(x)-f(x). Therefore, the relation is not symmetric.
Transitive: if f(x)−g(x)=1, and g(x)-h(x)=1, then f(x)-h(x)=2. In other words, (f,g)∈R, (g,h)∈R, and (f,h)∉R. Therefore, the relation is not transitive.
This is not an equivalence relation because it is not reflexive, not symmetric, and not transitive.
d) {(f,g)| for some C∈Z, for all x∈Z,f(x)−g(x) = C}
Reflexive: for all x, f(x)-f(x)=0, in this case, C=0. Therefore, it is reflexive.
Symmetric: if f(x)−g(x) = C for all x∈Z and some C∈Z, then g(x)-f(x)=-C for all x∈Z. Therefore, the relation is symmetric.
Transitive: if (1) f(x)−g(x) = C for all x∈Z and some C∈Z, and (2) g(x)−h(x) = C1 for all x∈Z and some C∈Z, then g(x)=f(x)-C by (1); substituting g(x) in (2) we get f(x)-C−h(x) = C1, it follows that get f(x)−h(x) = C1+C = C2 for all x∈Z and some C2∈Z. Therefore, the relation is transitive.
This is an Equivalence relation because it is reflexive, symmetric, and transitive.
e) {(f,g) | f(0) = g(1) and f(1) = g(0)}
Reflexive: There are cases where f(0)≠f(1). Therefore, the relation is not reflexive.
Symmetric: if f(0) = g(1) and f(1) = g(0), then g(0)=f(1) and g(1)=f(0). Therefore, the relation is symmetric.
Transitive: if f(0) = g(1) and f(1) = g(0), and g(0)=h(1) g(1)=h(0) means (f,g)∈R and (g,h)∈R. f(0)=h(0) and f(1)=h(1). So, it might be the case that f(0)∉h(1). Therefore, the relation is not transitive.
This is not an equivalence relation because it is not reflexive and not transitive.
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 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.
