Any function induces a surjection by restricting its codomain to its range. This

Question

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). 2. Let p be the function that sends every element of A into its equivalence class; p(x) ? [x]. The induced map g: Q ? B given by g([x]) = f(x) is a well defined. Show that g is a bijection and that f = g ? p. Comment on the importance of such a result.

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.

We want to show that g is a bijection (that is, one-to-one and onto).

Onto is already given.

Suppose g([x]) = g([y]).

Then f(x) = f(y)

This means x ~ y

or [x] = [y] by equivalence.

Thus g is a bijection.

Next, suppose x A.

g o p(x) = g(p(x))

= g([x])

= f(x).

Thus g o p = f.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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