6.2.2 The Category of Relations

The category of relations is the category $\mathsf{Rel}$ where

  • Objects. The objects of $\mathsf{Rel}$ are sets.
  • Morphisms. For each $A,B\in \text{Obj}\webleft (\mathsf{Sets}\webright )$, we have

    \[ \mathsf{Rel}\webleft (A,B\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathrm{Rel}\webleft (A,B\webright ). \]

  • Identities. For each $A\in \text{Obj}\webleft (\mathsf{Rel}\webright )$, the unit map

    \[ \mathbb {1}^{\mathsf{Rel}}_{A} \colon \text{pt}\to \mathrm{Rel}\webleft (A,A\webright ) \]

    of $\mathsf{Rel}$ at $A$ is defined by

    \[ \text{id}^{\mathsf{Rel}}_{A} \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{A}\webleft (-_{1},-_{2}\webright ), \]

    where $\chi _{A}\webleft (-_{1},-_{2}\webright )$ is the characteristic relation of $A$ of Chapter 2: Constructions With Sets, of .

  • Composition. For each $A,B,C\in \text{Obj}\webleft (\mathsf{Rel}\webright )$, the composition map

    \[ \circ ^{\mathsf{Rel}}_{A,B,C}\colon \mathrm{Rel}\webleft (B,C\webright )\times \mathrm{Rel}\webleft (A,B\webright )\to \mathrm{Rel}\webleft (A,C\webright ) \]

    of $\mathsf{Rel}$ at $\webleft (A,B,C\webright )$ is defined by

    \[ S\mathbin {{\circ }^{\mathsf{Rel}}_{A,B,C}}R \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}S\mathbin {\diamond }R \]

    for each $\webleft (S,R\webright )\in \mathrm{Rel}\webleft (B,C\webright )\times \mathrm{Rel}\webleft (A,B\webright )$, where $S\mathbin {\diamond }R$ is the composition of $S$ and $R$ of Chapter 7: Constructions With Relations, Definition 7.3.12.1.1.


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


You can also use the contact form below: