8 Relations

This chapter contains some material about relations. Notably, we discuss and explore:

  1. 1.

    The definition of relations (Section 8.1.1).

  2. 2.

    How relations may be viewed as decategorification of profunctors (Section 8.1.2).

  3. 3.

    The various kinds of categories that relations form, namely:

    1. (a)

      A category (Section 8.3.2).

    2. (b)

      A monoidal category (Section 8.3.3).

    3. (c)

      A 2-category (Section 8.3.4).

    4. (d)

      A double category (Section 8.3.5).

  4. 4.

    The various categorical properties of the 2-category of relations, including:

    1. (a)

      The self-duality of $\mathsf{Rel}$ and $\boldsymbol {\mathsf{Rel}}$ (Proposition 8.5.1.1.1).

    2. (b)

      Identifications of equivalences and isomorphisms in $\boldsymbol {\mathsf{Rel}}$ with bijections (Proposition 8.5.2.1.2).

    3. (c)

      Identifications of adjunctions in $\boldsymbol {\mathsf{Rel}}$ with functions (Proposition 8.5.3.1.1).

    4. (d)

      Identifications of monads in $\boldsymbol {\mathsf{Rel}}$ with preorders (Unresolved reference).

    5. (e)

      Identifications of comonads in $\boldsymbol {\mathsf{Rel}}$ with subsets (Unresolved reference).

    6. (f)

      A description of the monoids and comonoids in $\boldsymbol {\mathsf{Rel}}$ with respect to the Cartesian product (Remark 8.5.9.1.1).

    7. (g)

      Characterisations of monomorphisms in $\mathsf{Rel}$ (Unresolved reference).

    8. (h)

      Characterisations of 2-categorical notions of monomorphisms in $\boldsymbol {\mathsf{Rel}}$ (Unresolved reference).

    9. (i)

      Characterisations of epimorphisms in $\mathsf{Rel}$ (Unresolved reference).

    10. (j)

      Characterisations of 2-categorical notions of epimorphisms in $\boldsymbol {\mathsf{Rel}}$ (Unresolved reference).

    11. (k)

      The partial co/completeness of $\mathsf{Rel}$ (Proposition 8.5.14.1.1).

    12. (l)

      The existence or non-existence of Kan extensions and Kan lifts in $\mathsf{Rel}$ (Unresolved reference).

    13. (m)

      The closedness of $\boldsymbol {\mathsf{Rel}}$ (Proposition 8.5.19.1.1).

    14. (n)

      The identification of $\boldsymbol {\mathsf{Rel}}$ with the category of free algebras of the powerset monad on $\mathsf{Sets}$ (Proposition 8.5.20.1.1).

  5. 5.

    The adjoint pairs

    \begin{align*} R_{!} \dashv R_{-1} & \colon \mathcal{P}(A) \rightleftarrows \mathcal{P}(B),\\ R^{-1} \dashv R_{*} & \colon \mathcal{P}(B) \rightleftarrows \mathcal{P}(A) \end{align*}

    of functors (morphisms of posets) between $\mathcal{P}(A)$ and $\mathcal{P}(B)$ induced by a relation $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$, as well as the properties of $R_{!}$, $R_{-1}$, $R^{-1}$, and $R_{*}$ (Section 8.7).

    Of particular note are the following points:

    1. (a)

      These two pairs of adjoint functors are the counterpart for relations of the adjoint triple $f_{!}\dashv f^{-1}\dashv f_{*}$ induced by a function $f\colon A\to B$ studied in Chapter 4: Constructions With Sets, Section 4.6.

    2. (b)

      We have $R_{-1}=R^{-1}$ iff $R$ is total and functional (Unresolved reference of Unresolved reference).

    3. (c)

      As a consequence of the previous item, when $R$ comes from a function $f$, the pair of adjunctions

      \[ R_{!}\dashv R_{-1}=R^{-1}\dashv R_{*} \]

      reduces to the triple adjunction

      \[ f_{!}\dashv f^{-1}\dashv f_{*} \]

      from Chapter 4: Constructions With Sets, Section 4.6.

    4. (d)

      The pairs $R_{!}\dashv R_{-1}$ and $R^{-1}\dashv R_{*}$ turn out to be rather important later on, as they appear in the definition and study of continuous, open, and closed relations between topological spaces (Unresolved reference, Unresolved reference).

  6. 6.

    A description of two notions of “skew composition” on $\mathbf{Rel}(A,B)$, giving rise to left and right skew monoidal structures analogous to the left skew monoidal structure on $\mathsf{Fun}(\mathcal{C},\mathcal{D})$ appearing in the definition of a relative monad (Section 8.8 and Section 8.9).

This chapter is under revision. TODO:

  1. 1.

    Replicate Section 8.5 for apartness composition

  2. 2.

    Revise Section 8.7

  3. 3.

    Add subsection “A Six Functor Formalism for Sets, Part 2”, now with relations, building upon Section 8.7.

  4. 4.

    Replicate Section 8.7 for apartness composition

  5. 5.

    Revise sections on skew monoidal structures on $\mathbf{Rel}(A,B)$

  6. 6.

    Replicate the sections on skew monoidal structures on $\mathbf{Rel}(A,B)$ for apartness composition.

  7. 7.

    Explore relative co/monads in $\boldsymbol {\mathsf{Rel}}$, defined to be co/monoids in $\mathbf{Rel}(A,B)$ with its left/right skew monoidal structures of Chapter 8: Relations, Section 8.8 and Section 8.9

  8. 8.

    functional total relations defined with “satisfying the following equivalent conditions:”

  • Section 8.1: Relations
    • Subsection 8.1.1: Foundations
    • Subsection 8.1.2: Relations as Decategorifications of Profunctors
      • Remark 8.1.2.1.1: Relations as Decategorifications of Profunctors I
      • Remark 8.1.2.1.2: Relations as Decategorifications of Profunctors II
    • Subsection 8.1.3: Composition of Relations
      • Definition 8.1.3.1.1: Composition of Relations
      • Remark 8.1.3.1.2: Composing Relations With Right Kan Extensions
      • Example 8.1.3.1.3: Examples of Composition of Relations
      • Proposition 8.1.3.1.4: Properties of Composition of Relations
    • Subsection 8.1.4: Apartness Composition of Relations
      • Definition 8.1.4.1.1: Apartness Composition of Relations
      • Example 8.1.4.1.2: Examples of Apartness Composition of Relations
      • Proposition 8.1.4.1.3: Properties of Apartness Composition of Relations
    • Subsection 8.1.5: The Converse of a Relation
      • Definition 8.1.5.1.1: The Converse of a Relation
      • Example 8.1.5.1.2: Examples of Converses of Relations
      • Proposition 8.1.5.1.3: Properties of Converses of Relations
  • Section 8.2: Examples of Relations
    • Subsection 8.2.1: Elementary Examples of Relations
    • Subsection 8.2.2: The Graph of a Function
      • Definition 8.2.2.1.1: The Graph of a Function
      • Proposition 8.2.2.1.2: Properties of Graphs of Functions
    • Subsection 8.2.3: The Inverse of a Function
      • Definition 8.2.3.1.1: The Inverse of a Function
      • Proposition 8.2.3.1.2: Properties of Inverses of Functions
    • Subsection 8.2.4: Representable Relations
      • Definition 8.2.4.1.1: Representable Relations
  • Section 8.3: Categories of Relations
    • Subsection 8.3.1: The Category of Relations Between Two Sets
      • Definition 8.3.1.1.1: The Category of Relations Between Two Sets
    • Subsection 8.3.2: The Category of Relations
      • Definition 8.3.2.1.1: The Category of Relations
    • Subsection 8.3.3: The Closed Symmetric Monoidal Category of Relations
      • Subsubsection 8.3.3.1: The Monoidal Product
        • Definition 8.3.3.1.1: The Monoidal Product of $\mathsf{Rel}$
      • Subsubsection 8.3.3.2: The Monoidal Unit
        • Definition 8.3.3.2.1: The Monoidal Unit of $\mathsf{Rel}$
      • Subsubsection 8.3.3.3: The Associator
        • Definition 8.3.3.3.1: The Associator of $\mathsf{Rel}$
      • Subsubsection 8.3.3.4: The Left Unitor
        • Definition 8.3.3.4.1: The Left Unitor of $\mathsf{Rel}$
      • Subsubsection 8.3.3.5: The Right Unitor
        • Definition 8.3.3.5.1: The Right Unitor of $\mathsf{Rel}$
      • Subsubsection 8.3.3.6: The Symmetry
        • Definition 8.3.3.6.1: The Symmetry of $\mathsf{Rel}$
      • Subsubsection 8.3.3.7: The Internal Hom
        • Definition 8.3.3.7.1: The Internal Hom of $\mathsf{Rel}$
        • Proposition 8.3.3.7.2: Properties of the Internal Hom of $\mathsf{Rel}$
      • Subsubsection 8.3.3.8: The Closed Symmetric Monoidal Category of Relations
        • Proposition 8.3.3.8.1: The Closed Symmetric Monoidal Category of Relations
    • Subsection 8.3.4: The 2-Category of Relations
      • Definition 8.3.4.1.1: The 2-Category of Relations
    • Subsection 8.3.5: The Double Category of Relations
      • Subsubsection 8.3.5.1: The Double Category of Relations
        • Definition 8.3.5.1.1: The Double Category of Relations
      • Subsubsection 8.3.5.2: Horizontal Identities
        • Definition 8.3.5.2.1: The Horizontal Identities of $\mathsf{Rel}^{\mathsf{dbl}}$
      • Subsubsection 8.3.5.3: Horizontal Composition
        • Definition 8.3.5.3.1: The Horizontal Composition of $\mathsf{Rel}^{\mathsf{dbl}}$
      • Subsubsection 8.3.5.4: Vertical Composition of 2-Morphisms
        • Definition 8.3.5.4.1: The Vertical Composition of 2-Morphisms in $\mathsf{Rel}^{\mathsf{dbl}}$
      • Subsubsection 8.3.5.5: The Associators
        • Definition 8.3.5.5.1: The Associators of $\mathsf{Rel}^{\mathsf{dbl}}$
      • Subsubsection 8.3.5.6: The Left Unitors
        • Definition 8.3.5.6.1: The Left Unitors of $\mathsf{Rel}^{\mathsf{dbl}}$
      • Subsubsection 8.3.5.7: The Right Unitors
        • Definition 8.3.5.7.1: The Right Unitors of $\mathsf{Rel}^{\mathsf{dbl}}$
  • Section 8.4: Categories of Relations With Apartness Composition
    • Subsection 8.4.1: The Category of Relations With Apartness Composition
      • Definition 8.4.1.1.1: The Category of Relations With Apartness Composition
      • Proposition 8.4.1.1.2: Isomorphism Between $\mathsf{Rel}$ and $\mathsf{Rel}^{\mathord {\mathbin {\square }}}$
    • Subsection 8.4.2: The 2-Category of Relations With Apartness Composition
      • Definition 8.4.2.1.1: The 2-Category of Relations With Apartness Composition
      • Proposition 8.4.2.1.2: 2-Isomorphism Between $\boldsymbol {\mathsf{Rel}}$ and $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }},\mathsf{co}}$
    • Subsection 8.4.3: The Linear Bicategory of Relations
      • Definition 8.4.3.1.1: The Linear Bicategory of Relations
    • Subsection 8.4.4: Other Categorical Structures With Apartness Composition
      • Remark 8.4.4.1.1: Other Categorical Structures With Apartness Composition
  • Section 8.5: Properties of the 2-Category of Relations
    • Subsection 8.5.1: Self-Duality
      • Proposition 8.5.1.1.1: Self-Duality for the (2-)Category of Relations
    • Subsection 8.5.2: Isomorphisms and Equivalences
      • Lemma 8.5.2.1.1: Conditions Involving a Relation and Its Converse I
      • Proposition 8.5.2.1.2: Isomorphisms and Equivalences in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.3: Internal Adjunctions
      • Proposition 8.5.3.1.1: Adjunctions in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.4: Internal Monads
      • Proposition 8.5.4.1.1: Internal Monads in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.4.1.2: Codensity Monads in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.5: Internal Comonads
      • Proposition 8.5.5.1.1: Internal Comonads in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.5.1.2: Density Comonads in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.6: Modules Over Internal Monads
      • Proposition 8.5.6.1.1: Modules Over Internal Monads in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.7: Comodules Over Internal Comonads
      • Proposition 8.5.7.1.1: Comodules Over Internal Comonads in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.8: Eilenberg–Moore and Kleisli Objects
      • Proposition 8.5.8.1.1: Eilenberg–Moore and Kleisli Objects in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.9: Co/Monoids
      • Remark 8.5.9.1.1: Co/Monoids in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.10: Monomorphisms and 2-Categorical Monomorphisms
      • Explanation 8.5.10.1.1: Monomorphisms in $\mathsf{Rel}$
      • Proposition 8.5.10.1.2: Characterisations of Monomorphisms in $\mathsf{Rel}$ I
      • Proposition 8.5.10.1.3: Characterisations of Monomorphisms in $\mathsf{Rel}$ II
      • Corollary 8.5.10.1.4: Characterisations of Monomorphisms in $\mathsf{Rel}$ III
      • Corollary 8.5.10.1.5: Characterisations of Monomorphisms in $\mathsf{Rel}$ V
      • Warning 8.5.10.1.6: Natural Conditions That Fail To Characterise Monomorphisms in $\mathsf{Rel}$
      • Remark 8.5.10.1.7: Monomorphisms in $\mathsf{Rel}$ Give Rise to Antichains
      • Proposition 8.5.10.1.8: Characterisations of 2-Categorical Monomorphisms in $\boldsymbol {\mathsf{Rel}}$ I
      • Proposition 8.5.10.1.9: Characterisations of 2-Categorical Monomorphisms in $\boldsymbol {\mathsf{Rel}}$ II
    • Subsection 8.5.11: Epimorphisms and 2-Categorical Epimorphisms
      • Explanation 8.5.11.1.1: Epimorphisms in $\mathsf{Rel}$
      • Proposition 8.5.11.1.2: Characterisations of Epimorphisms in $\mathsf{Rel}$ I
      • Proposition 8.5.11.1.3: Characterisations of Epimorphisms in $\mathsf{Rel}$ II
      • Corollary 8.5.11.1.4: Characterisations of Epimorphisms in $\mathsf{Rel}$ III
      • Corollary 8.5.11.1.5: Characterisations of Epimorphisms in $\mathsf{Rel}$ IV
      • Corollary 8.5.11.1.6: Characterisations of Epimorphisms in $\mathsf{Rel}$ V
      • Warning 8.5.11.1.7: Natural Conditions That Fail To Characterise Epimorphisms in $\mathsf{Rel}$
      • Remark 8.5.11.1.8: Epimorphisms in $\mathsf{Rel}$ Give Rise to Antichains
      • Proposition 8.5.11.1.9: Characterisations of 2-Categorical Epimorphisms in $\boldsymbol {\mathsf{Rel}}$ I
      • Proposition 8.5.11.1.10: Characterisations of 2-Categorical Epimorphisms in $\boldsymbol {\mathsf{Rel}}$ II
    • Subsection 8.5.12: Retractions
      • Proposition 8.5.12.1.1: Retractions in $\mathsf{Rel}$
    • Subsection 8.5.13: Sections
      • Proposition 8.5.13.1.1: Sections in $\mathsf{Rel}$
    • Subsection 8.5.14: Co/Limits
      • Proposition 8.5.14.1.1: Co/Limits in $\mathsf{Rel}$
    • Subsection 8.5.15: Internal Left Kan Extensions
      • Proposition 8.5.15.1.1: Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.15.1.2: Internal Left Kan Extensions Along Functions
      • Remark 8.5.15.1.3: Illustrating the Failure of Internal Left Kan Extensions in $\boldsymbol {\mathsf{Rel}}$ to Exist
      • Question 8.5.15.1.4: Existence of Specific Internal Left Kan Extensions of Relations
    • Subsection 8.5.16: Internal Left Kan Lifts
      • Proposition 8.5.16.1.1: Internal Left Kan Lifts in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.16.1.2: Internal Left Kan Lifts Along Functions
      • Question 8.5.16.1.3: Existence of Specific Internal Left Kan Lifts of Relations
    • Subsection 8.5.17: Internal Right Kan Extensions
      • Motivation 8.5.17.1.1: Setting for Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$
      • Proposition 8.5.17.1.2: Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.17.1.3: Examples of Internal Right Kan Extensions of Relations
      • Proposition 8.5.17.1.4: Properties of Internal Right Kan Extensions in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.18: Internal Right Kan Lifts
      • Motivation 8.5.18.1.1: Setting for Internal Right Kan Lifts in $\boldsymbol {\mathsf{Rel}}$
      • Proposition 8.5.18.1.2: Internal Right Kan Lifts in $\boldsymbol {\mathsf{Rel}}$
      • Example 8.5.18.1.3: Examples of Internal Right Kan Extensions of Relations
      • Proposition 8.5.18.1.4: Properties of Internal Right Kan Lifts in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.19: Closedness
      • Proposition 8.5.19.1.1: Closedness of $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.5.20: $\mathsf{Rel}$ as a Category of Free Algebras
      • Proposition 8.5.20.1.1: $\mathsf{Rel}$ as a Category of Free Algebras
  • Section 8.6: Properties of the 2-Category of Relations With Apartness Composition
    • Subsection 8.6.1: Self-Duality
      • Proposition 8.6.1.1.1: Self-Duality for the (2-)Category of Relations With Apartness Composition
    • Subsection 8.6.2: Isomorphisms and Equivalences
      • Lemma 8.6.2.1.1: Conditions Involving a Relation and Its Converse II
      • Remark 8.6.2.1.2: Unwinding Lemma 8.6.2.1.1
      • Proposition 8.6.2.1.3: Isomorphisms and Equivalences in $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$
    • Subsection 8.6.3: Internal Adjunctions
      • Proposition 8.6.3.1.1: Adjunctions in $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$
    • Subsection 8.6.4: Internal Monads
      • Proposition 8.6.4.1.1: Internal Monads in $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$
    • Subsection 8.6.5: Internal Comonads
      • Proposition 8.6.5.1.1: Internal Comonads in $\boldsymbol {\mathsf{Rel}}^{\mathord {\mathbin {\square }}}$
      • Example 8.6.5.1.2: Density Comonads in $\boldsymbol {\mathsf{Rel}}$
    • Subsection 8.6.6: Modules Over Internal Monads
    • Subsection 8.6.7: Comodules Over Internal Comonads
    • Subsection 8.6.8: Eilenberg–Moore and Kleisli Objects
    • Subsection 8.6.9: Monomorphisms
    • Subsection 8.6.10: 2-Categorical Monomorphisms
    • Subsection 8.6.11: Epimorphisms
    • Subsection 8.6.12: 2-Categorical Epimorphisms
    • Subsection 8.6.13: Co/Limits
    • Subsection 8.6.14: Internal Left Kan Extensions
    • Subsection 8.6.15: Internal Left Kan Lifts
    • Subsection 8.6.16: Internal Right Kan Extensions
    • Subsection 8.6.17: Internal Right Kan Lifts
    • Subsection 8.6.18: Coclosedness
  • Section 8.7: The Adjoint Pairs $R_{!}\dashv R_{-1}$ and $R^{-1}\dashv R_{*}$
  • Section 8.8: The Left Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
    • Subsection 8.8.1: The Left Skew Monoidal Product
      • Definition 8.8.1.1.1: The Left $J$-Skew Monoidal Product of $\mathbf{Rel}(A,B)$
    • Subsection 8.8.2: The Left Skew Monoidal Unit
      • Definition 8.8.2.1.1: The Left $J$-Skew Monoidal Unit of $\mathbf{Rel}(A,B)$
    • Subsection 8.8.3: The Left Skew Associators
      • Definition 8.8.3.1.1: The Left $J$-Skew Associator of $\mathbf{Rel}(A,B)$
    • Subsection 8.8.4: The Left Skew Left Unitors
      • Definition 8.8.4.1.1: The Left $J$-Skew Left Unitor of $\mathbf{Rel}(A,B)$
    • Subsection 8.8.5: The Left Skew Right Unitors
      • Definition 8.8.5.1.1: The Left $J$-Skew Right Unitor of $\mathbf{Rel}(A,B)$
    • Subsection 8.8.6: The Left Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
      • Proposition 8.8.6.1.1: The Left $J$-Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
  • Section 8.9: The Right Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
    • Subsection 8.9.1: The Right Skew Monoidal Product
      • Definition 8.9.1.1.1: The Right $J$-Skew Monoidal Product of $\mathbf{Rel}(A,B)$
    • Subsection 8.9.2: The Right Skew Monoidal Unit
      • Definition 8.9.2.1.1: The Right $J$-Skew Monoidal Unit of $\mathbf{Rel}(A,B)$
    • Subsection 8.9.3: The Right Skew Associators
      • Definition 8.9.3.1.1: The Right $J$-Skew Associator of $\mathbf{Rel}(A,B)$
    • Subsection 8.9.4: The Right Skew Left Unitors
      • Definition 8.9.4.1.1: The Right $J$-Skew Left Unitor of $\mathbf{Rel}(A,B)$
    • Subsection 8.9.5: The Right Skew Right Unitors
      • Definition 8.9.5.1.1: The Right $J$-Skew Right Unitor of $\mathbf{Rel}(A,B)$
    • Subsection 8.9.6: The Right Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
      • Proposition 8.9.6.1.1: The Right $J$-Skew Monoidal Structure on $\mathbf{Rel}(A,B)$
Previous
Next

View Chapter 8 as PDF
5 tags refer to this tag
Statistics Cite

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

You can also use the contact form below: