We return to equivalence relations, now with functions at our disposal. The quotient set of Definition 1.2.7 comes with a map from .
Definition 1.6.1 (The quotient map). Let be an equivalence relation on . The quotient map (or canonical map) of is
The quotient map is surjective, since every element of has the form . By Lemma 1.2.5, if and only if ; so the fiber of over a class is the class itself, . In particular, is injective exactly when every class has a single element, that is, when is equality on .
Conversely, every function produces an equivalence relation.
Proposition 1.6.2 (Fibers of a map). Let , and for set if .
is an equivalence relation on , and the class of is the fiber . Thus the nonempty fibers ,, form a partition of .
The map ,, is well defined and bijective. Its inverse sends to the fiber . In particular, if is surjective, then is in bijection with .
Proof. (a) Reflexivity, symmetry, and transitivity of follow from the same properties of equality in . The class of is , and the fiber over is nonempty exactly when . Proposition 1.2.8 shows that the classes form a partition.
(b) The value depends only on the class : if , then , that is, . So is a function. It is injective, since means , and surjective, since each is for some . The class sent to is .∎
Putting the pieces together, three kinds of data on a set carry the same information.
Theorem 1.6.3 (Relations, partitions, and surjections). Let be a set.
Equivalence relations on correspond to partitions of : an equivalence relation corresponds to , and a partition to .
Every equivalence relation on is the relation determined by a surjection, namely its quotient map .
Every surjection determines the equivalence relation , whose classes are the fibers of , and is the quotient map followed by the bijection ; that is, .
So an equivalence relation on , a partition of , and a surjection from onto another set (up to a bijection of the target) are three descriptions of the same thing.
Proof. Part (a) is Proposition 1.2.8. For (b), if and only if , by Lemma 1.2.5; so is . For (c), Proposition 1.6.2 shows that is a bijection onto , and for every .∎
More generally, given an equivalence relation on and an arbitrary function , we may ask whether induces a function on the quotient by the rule . The difficulty is that a class has many representatives, and the proposed value must not depend on which one we pick.
Proposition 1.6.4 (Maps descending to a quotient). Let be an equivalence relation on with quotient map , and let . There is a function with if and only if is compatible with , meaning that In that case is unique, it is given by , and its image is .
Proof. If exists and , then , so . Conversely, suppose is compatible with , and let . Its domain is , and if two of its pairs and have the same first coordinate, then , so and . Hence is a function, and for all . It is unique because is surjective: any with satisfies for every class . Finally, .∎
When is compatible with , we say that descends to , or factors through. The diagram above commutes: the two routes from to give the same map. The induced map is injective if and only if implies , that is, if and only if is exactly the relation ; and is surjective if and only if is. This principle will return many times: quotient groups (Theorem 3.3.2) and quotient vector spaces (Definition 7.1.1) are built on it. Here is its first use.
Example 1.6.5 (Addition mod ). Let be congruence mod on (Example 1.2.9). We would like to add classes by the rule . For this to make sense, the right side must depend only on the classes and , not on the representatives and . It does: if and , then divides and , hence their sum , so . In the language of Proposition 1.6.4: for fixed , the map ,, is compatible with , so it descends to a map ,; and the result depends only on , since whenever . Hence is a well-defined operation on . Under the bijection ,, it becomes addition of remainders: is the class , where is the remainder of on division by . This is the group of the next chapter (Example 2.2.3), which we describe there as with addition mod .