Use the following information for both discussion prompts this week: Any functio
ID: 1888169 • Letter: U
Question
Use the following information for both discussion prompts this week:Any function induces a surjection by restricting its codomain to its range. This should be obvious. What may or may not be obvious is that any onto function induces a bijection defined on a quotient of its domain. Let f: A ? B be an onto function. Let Q be the set of all equivalence classes of domain A under the equivalence relation x ~ y if and only if f(x) = f(y). (Equivalently, Q is the set of all pre-images under f).
1. Prove that ~ is an equivalence relation.
Explanation / Answer
For a A, f(a) = f(a). Thus a ~ a. This means ~ is reflexive.
If a ~ b, then f(a) = f(b).
By the symmetric property of = , f(b) = f(a).
This means b ~ a.
Therefore ~ is symmetric.
If a ~ b and b ~ c, then f(a) = f(b) and f(b) = f(c).
Since = is transitive, we have f(a) = f(c).
This means a ~ c.
Thus ~ is transitive.
In conclusion, ~ is an equivalence relation.