Use the following information for both discussion prompts this week: Any functio

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.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.