Which of the following is an equivalence relation on the set of all functions…
2018
Which of the following is an equivalence relation on the set of all functions from Z to Z ?
- A.
\(\{ f, \:g) \mid f(x) - g(x) =1 \: \forall \: x \in \: Z \}\) - B.
\(\{ f, \:g) \mid f(0) = g(0) \text{ or } f(1) = g(1) \}\) - C.
\(\{ f, \:g) \mid f(0) = g(1) \text{ and } f(1) = g(0) \}\) - D.
\(\{ f, \:g) \mid f(x) - g(x) =k \text{ for some } k \in Z \}\)
Attempted by 273 students.
Show answer & explanation
Correct answer: D
Answer: The relation of functions that differ by a constant integer is an equivalence relation.
Check for the relation defined by: there exists an integer k such that for all x in Z, f(x)-g(x)=k.
Reflexive: For any function f, take k = 0. Then f(x)-f(x)=0 for all x, so each function is related to itself.
Symmetric: If f(x)-g(x)=k for all x, then g(x)-f(x)=-k for all x, and -k is an integer, so g is related to f.
Transitive: If f(x)-g(x)=k1 and g(x)-h(x)=k2 for all x, then f(x)-h(x)=k1+k2 for all x, and k1+k2 is an integer, so f is related to h.
Therefore the relation is reflexive, symmetric, and transitive, hence an equivalence relation. Equivalence classes consist of all functions obtained by adding the same integer constant to a representative function.
Why the other relations fail (brief):
Relation: f(x)-g(x)=1 for all x. Fails reflexivity because f(x)-f(x)=0≠1 for any f; also fails symmetry.
Relation: f(0)=g(0) or f(1)=g(1). Reflexive and symmetric but not transitive. Example: f with (0,0), g with (0,1), h with (1,1) at points 0 and 1: f~g and g~h but f is not related to h.
Relation: f(0)=g(1) and f(1)=g(0). Symmetric but not reflexive in general and not transitive. Example on values at 0 and 1: f with (0,1), g with (1,0), h with (0,1): f~g and g~h but f is not related to h.