7 Constructions With Relations

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

  1. The existence or non-existence of Kan extensions and Kan lifts in the $2$-category $\textbf{Rel}$ (Section 7.2).
  2. The various kinds of constructions involving relations, such as graphs, domains, ranges, unions, intersections, products, inverse relations, composition of relations, and collages (Section 7.3).
  3. The adjoint pairs
    \begin{align*} R_{*} \dashv R_{-1} & \colon \mathcal{P}\webleft (A\webright ) \rightleftarrows \mathcal{P}\webleft (B\webright ),\\ R^{-1} \dashv R_{!} & \colon \mathcal{P}\webleft (B\webright ) \rightleftarrows \mathcal{P}\webleft (A\webright ) \end{align*}

    of functors (morphisms of posets) between $\mathcal{P}\webleft (A\webright )$ and $\mathcal{P}\webleft (B\webright )$ 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 7.4).

    Of particular note are the following points:

    1. 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 2: Constructions With Sets, Section 2.4;
    2. We have $R_{-1}=R^{-1}$ iff $R$ is total and functional (Item 8 of Proposition 7.4.2.1.3).
    3. 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 2: Constructions With Sets, Section 2.4.

    4. 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 (, ).
  • Section 7.1: Co/Limits in the Category of Relations
  • Section 7.2: Kan Extensions and Kan Lifts in the $2$-Category of Relations
    • Subsection 7.2.1: Left Kan Extensions in $\textbf{Rel}$
      • Proposition 7.2.1.1.1: Left Kan Extensions in $\textbf{Rel}$
      • Question 7.2.1.1.2: Existence of Specific Left Kan Extensions of Relations
      • Question 7.2.1.1.3: Explicit Description of Left Kan Extensions Along Functions
    • Subsection 7.2.2: Left Kan Lifts in $\textbf{Rel}$
      • Proposition 7.2.2.1.1: Left Kan Lifts in $\textbf{Rel}$
      • Question 7.2.2.1.2: Existence of Specific Left Kan Lifts of Relations
      • Question 7.2.2.1.3: Explicit Description of Left Kan Lifts Along Functions
    • Subsection 7.2.3: Right Kan Extensions in $\textbf{Rel}$
      • Proposition 7.2.3.1.1: Existence of Right Kan Extensions in $\textbf{Rel}$
    • Subsection 7.2.4: Right Kan Lifts in $\textbf{Rel}$
      • Proposition 7.2.4.1.1: Existence of Right Kan Lifts in $\textbf{Rel}$
  • Section 7.3: More Constructions With Relations
    • Subsection 7.3.1: The Graph of a Function
      • Definition 7.3.1.1.1: The Graph of a Function
      • Proposition 7.3.1.1.2: Properties of Graphs of Functions
    • Subsection 7.3.2: The Inverse of a Function
      • Definition 7.3.2.1.1: The Inverse of a Function
      • Proposition 7.3.2.1.2: Properties of Inverses of Functions
    • Subsection 7.3.3: Representable Relations
      • Definition 7.3.3.1.1: Representable Relations
    • Subsection 7.3.4: The Domain and Range of a Relation
      • Definition 7.3.4.1.1: The Domain and Range of a Relation
    • Subsection 7.3.5: Binary Unions of Relations
      • Definition 7.3.5.1.1: Binary Unions of Relations
      • Proposition 7.3.5.1.2: Properties of Binary Unions of Relations
    • Subsection 7.3.6: Unions of Families of Relations
      • Definition 7.3.6.1.1: The Union of a Family of Relations
      • Proposition 7.3.6.1.2: Properties of Unions of Families of Relations
    • Subsection 7.3.7: Binary Intersections of Relations
      • Definition 7.3.7.1.1: Binary Intersections of Relations
      • Proposition 7.3.7.1.2: Properties of Binary Intersections of Relations
    • Subsection 7.3.8: Intersections of Families of Relations
      • Definition 7.3.8.1.1: The Intersection of a Family of Relations
      • Proposition 7.3.8.1.2: Properties of Intersections of Families of Relations
    • Subsection 7.3.9: Binary Products of Relations
      • Definition 7.3.9.1.1: Binary Products of Relations
      • Proposition 7.3.9.1.2: Properties of Binary Products of Relations
    • Subsection 7.3.10: Products of Families of Relations
      • Definition 7.3.10.1.1: The Product of a Family of Relations
    • Subsection 7.3.11: The Inverse of a Relation
      • Definition 7.3.11.1.1: The Inverse of a Relation
      • Example 7.3.11.1.2: Examples of Inverses of Relations
      • Proposition 7.3.11.1.3: Properties of Inverses of Relations
    • Subsection 7.3.12: Composition of Relations
      • Definition 7.3.12.1.1: Composition of Relations
      • Example 7.3.12.1.2: Examples of Composition of Relations
      • Proposition 7.3.12.1.3: Properties of Composition of Relations
    • Subsection 7.3.13: The Collage of a Relation
      • Definition 7.3.13.1.1: The Collage of a Relation
      • Proposition 7.3.13.1.2: Properties of Collages of Relations
  • Section 7.4: Functoriality of Powersets

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


You can also use the contact form below: