8.5.2 Quotients of Sets by Equivalence Relations

Let A be a set and let R be a relation on A.

The quotient of X by R is the set X/R defined by

X/R=def{[a]P(X) | aX}.

The reason we define quotient sets for equivalence relations only is that each of the properties of being an equivalence relation—reflexivity, symmetry, and transitivity—ensures that the equivalences classes [a] of X under R are well-behaved:

  • Reflexivity. If R is reflexive, then, for each aX, we have a[a].
  • Symmetry. The equivalence class [a] of an element a of X is defined by

    [a]=def{xX | xRa},

    but we could equally well define

    [a]=def{xX | aRx}

    instead. This is not a problem when R is symmetric, as we then have [a]=[a].1

  • Transitivity. If R is transitive, then [a] and [b] are disjoint iff aRb, and equal otherwise.


1When categorifying equivalence relations, one finds that [a] and [a] correspond to presheaves and copresheaves; see .

Let f:XY be a function and let R be a relation on X.

  1. 1. As a Coequaliser. We have an isomorphism of sets
    X/ReqCoEq(RX×Xpr2pr1X),

    where Req is the equivalence relation generated by R.

  2. 2. As a Pushout. We have an isomorphism of sets1
    where Req is the equivalence relation generated by R.
  3. 3. The First Isomorphism Theorem for Sets. We have an isomorphism of sets23
    X/Ker(f)Im(f).
  4. 4. Descending Functions to Quotient Sets, I. Let R be an equivalence relation on X. The following conditions are equivalent:
    1. (a) There exists a map
      f:X/RY

      making the diagram

      commute.

    2. (b) We have RKer(f).
    3. (c) For each x,yX, if xRy, then f(x)=f(y).
  5. 5. Descending Functions to Quotient Sets, II. Let R be an equivalence relation on X. If the conditions of Item 4 hold, then f is the unique map making the diagram

    commute.

  6. 6. Descending Functions to Quotient Sets, III. Let R be an equivalence relation on X. We have a bijection
    HomSets(X/R,Y)HomSetsR(X,Y),

    natural in X,YObj(Sets), given by the assignment ff of Item 4 and Item 5, where HomSetsR(X,Y) is the set defined by

    HomSetsR(X,Y)=def{fHomSets(X,Y) | for each x,yX,if xRy, thenf(x)=f(y)}.
  7. 7. Descending Functions to Quotient Sets, IV. Let R be an equivalence relation on X. If the conditions of Item 4 hold, then the following conditions are equivalent:
    1. (a) The map f is an injection.
    2. (b) We have R=Ker(f).
    3. (c) For each x,yX, we have xRy iff f(x)=f(y).
  8. 8. Descending Functions to Quotient Sets, V. Let R be an equivalence relation on X. If the conditions of Item 4 hold, then the following conditions are equivalent:
    1. (a) The map f:XY is surjective.
    2. (b) The map f:X/RY is surjective.
  9. 9. Descending Functions to Quotient Sets, VI. Let R be a relation on X and let Req be the equivalence relation associated to R. The following conditions are equivalent:
    1. (a) The map f satisfies the equivalent conditions of Item 4:
      • There exists a map
        f:X/ReqY

        making the diagram

        commute.

      • For each x,yX, if xReqy, then f(x)=f(y).

    2. (b) For each x,yX, if xRy, then f(x)=f(y).


1Dually, we also have an isomorphism of sets
2Further Terminology: The set X/Ker(f) is often called the coimage of f, and denoted by CoIm(f).
3In a sense this is a result relating the monad in Rel induced by f with the comonad in Rel induced by f, as the kernel and image

Ker(f):X|X,Im(f)Y

of f are the underlying functors of (respectively) the induced monad and comonad of the adjunction

of Chapter 7: Constructions With Relations, Item 2 of Proposition 7.3.1.1.2.

Item 1: As a Coequaliser
Omitted.
Item 2: As a Pushout
Omitted.
Item 3: The First Isomorphism Theorem for Sets
Clear.
Item 4: Descending Functions to Quotient Sets, I
See [Proof Wiki, Condition For Mapping From Quotient Set To Be Well Defined].
Item 5: Descending Functions to Quotient Sets, II
See [Proof Wiki, Mapping From Quotient Set When Defined Is Unique].
Item 6: Descending Functions to Quotient Sets, III
This follows from Item 5 and Item 6.
Item 7: Descending Functions to Quotient Sets, IV
See [Proof Wiki, Condition For Mapping From Quotient Set To Be An Injection].
Item 8: Descending Functions to Quotient Sets, V
See [Proof Wiki, Condition For Mapping From Quotient Set To Be A Surjection].
Item 9: Descending Functions to Quotient Sets, VI
The implication Item (a)Item (b) is clear. Conversely, suppose that, for each x,yX, if xRy, then f(x)=f(y). Spelling out the definition of the equivalence closure of R, we see that the condition xReqy unwinds to the following:
  • There exist (x1,,xn)R×n satisfying at least one of the following conditions:

    1. (a) The following conditions are satisfied:
      1. (i) We have xRx1 or x1Rx;
      2. (ii) We have xiRxi+1 or xi+1Rxi for each 1in1;
      3. (iii) We have yRxn or xnRy;
    2. (b) We have x=y.

Now, if x=y, then f(x)=f(y) trivially; otherwise, we have

f(x)=f(x1),f(x1)=f(x2),f(xn1)=f(xn),f(xn)=f(y),

and f(x)=f(y), as we wanted to show.


Noticed something off, or have any comments? Feel free to reach out!


You can also use the contact form below: