8 Relations

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

1.
The definition of relations (Section 8.1.1).
2.
How relations may be viewed as decategorification of profunctors (Section 8.1.2).
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.
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.4.1.1.1).
2. (b)
  Identifications of equivalences and isomorphisms in $\boldsymbol {\mathsf{Rel}}$ with bijections (Proposition 8.4.2.1.1).
3. (c)
  Identifications of adjunctions in $\boldsymbol {\mathsf{Rel}}$ with functions (Proposition 8.4.3.1.1).
4. (d)
  Identifications of monads in $\boldsymbol {\mathsf{Rel}}$ with preorders (Proposition 8.4.4.1.1).
5. (e)
  Identifications of comonads in $\boldsymbol {\mathsf{Rel}}$ with subsets (Proposition 8.4.5.1.1).
6. (f)
  A description of the monoids and comonoids in $\boldsymbol {\mathsf{Rel}}$ with respect to the Cartesian product (Remark 8.4.6.1.1).
7. (g)
  Characterisations of monomorphisms in $\mathsf{Rel}$ (Proposition 8.4.7.1.1).
8. (h)
  Characterisations of $2$-categorical notions of monomorphisms in $\boldsymbol {\mathsf{Rel}}$ (Proposition 8.4.8.1.1).
9. (i)
  Characterisations of epimorphisms in $\mathsf{Rel}$ (Proposition 8.4.9.1.1).
10. (j)
  Characterisations of $2$-categorical notions of epimorphisms in $\boldsymbol {\mathsf{Rel}}$ (Proposition 8.4.10.1.1).
11. (k)
  The partial co/completeness of $\mathsf{Rel}$ (Proposition 8.4.11.1.1).
12. (l)
  The existence or non-existence of Kan extensions and Kan lifts in $\mathsf{Rel}$ (Remark 8.4.12.1.1).
13. (m)
  The closedness of $\boldsymbol {\mathsf{Rel}}$ (Proposition 8.4.13.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.4.14.1.1).
5.
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 8.5).

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 (Item 8 of Proposition 8.5.2.1.3).
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 (, ).
6.
A description of two notions of “skew composition” on $\mathbf{Rel}\webleft (A,B\webright )$, giving rise to left and right skew monoidal structures analogous to the left skew monoidal structure on $\mathsf{Fun}\webleft (\mathcal{C},\mathcal{D}\webright )$ appearing in the definition of a relative monad (Section 8.6 and Section 8.7).

TODO:

1.
Define apartness composition
2.
Revise Section 8.3
3.
Replicate Section 8.3 for apartness composition
4.
Revise Section 8.4
1. (a)
  Add modules over monads in $\boldsymbol {\mathsf{Rel}}$
2. (b)
  internal relations,
3. (c)
  Co/limits in $\boldsymbol {\mathsf{Rel}}$.
4. (d)
  Codensity monad $\operatorname {\mathrm{Ran}}_{J}\webleft (J\webright )$ of a relation (What about $\operatorname {\mathrm{Rift}}_{J}\webleft (J\webright )$?)
  1. (i)
    Density comonad $\operatorname {\mathrm{Lan}}_{J}\webleft (J\webright )$ of a relation when it exists (what about $\operatorname {\mathrm{Lift}}_{J}\webleft (J\webright )$?)
5. (e)
  Fibrations in $\boldsymbol {\mathsf{Rel}}$, like discrete fibrations and Street fibrations
5.
Replicate Section 8.4 for apartness composition
6.
Revise Section 8.5
7.
Add subsection “A Six Functor Formalism for Sets, Part 2”, now with relations, building upon Section 8.5.
8.
Replicate Section 8.5 for apartness composition
9.
Revise sections on skew monoidal structures on $\mathbf{Rel}\webleft (A,B\webright )$
10.
Replicate the sections on skew monoidal structures on $\mathbf{Rel}\webleft (A,B\webright )$ for apartness composition.
11.
Explore relative co/monads in $\boldsymbol {\mathsf{Rel}}$, defined to be co/monoids in $\mathbf{Rel}\webleft (A,B\webright )$ with its left/right skew monoidal structures of Chapter 8: Relations, Section 8.6 and Section 8.7
12.
Consider adding the sections
- •
  The Monoidal Bicategory of Relations
- •
  The Monoidal Double Category of Relations
to Chapter 8: Relations .

Section 8.1: Relations
- Subsection 8.1.1: Foundations
  - Definition 8.1.1.1.1: Relations
  - Remark 8.1.1.1.2: Unwinding Item 1, I
  - Remark 8.1.1.1.3: Unwinding Item 2, II
  - Notation 8.1.1.1.4: Further Notation for Relations
  - Proposition 8.1.1.1.5: Properties of Relations
- 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
  - Example 8.1.3.1.2: Examples of Composition of Relations
  - Proposition 8.1.3.1.3: Properties of Composition of Relations
- Subsection 8.1.4: Apartness Composition of Relations
  - Definition 8.1.4.1.1: 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
  - Example 8.2.1.1.1: The Trivial Relation
  - Example 8.2.1.1.2: The Cotrivial Relation
  - Example 8.2.1.1.3: The Characteristic Relation of a Set
  - Example 8.2.1.1.4: Square Roots
  - Example 8.2.1.1.5: Complex Logarithms
  - Example 8.2.1.1.6: More 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: Properties of the $2$-Category of Relations
- Subsection 8.4.1: Self-Duality
  - Proposition 8.4.1.1.1: Self-Duality for the (2-)Category of Relations
- Subsection 8.4.2: Isomorphisms and Equivalences
  - Proposition 8.4.2.1.1: Isomorphisms and Equivalences in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.3: Internal Adjunctions
  - Proposition 8.4.3.1.1: Adjunctions in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.4: Internal Monads
  - Proposition 8.4.4.1.1: Monads in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.5: Internal Comonads
  - Proposition 8.4.5.1.1: Comonads in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.6: Co/Monoids
  - Remark 8.4.6.1.1: Co/Monoids in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.7: Monomorphisms
  - Proposition 8.4.7.1.1: Characterisations of Monomorphisms in $\mathsf{Rel}$
- Subsection 8.4.8: 2-Categorical Monomorphisms
  - Proposition 8.4.8.1.1: 2-Categorical Monomorphisms in $\boldsymbol {\mathsf{Rel}}$
  - Question 8.4.8.1.2: Better Characterisations of Representably Full Morphisms in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.9: Epimorphisms
  - Proposition 8.4.9.1.1: Characterisations of Epimorphisms in $\mathsf{Rel}$
- Subsection 8.4.10: 2-Categorical Epimorphisms
  - Proposition 8.4.10.1.1: 2-Categorical Epimorphisms in $\boldsymbol {\mathsf{Rel}}$
  - Question 8.4.10.1.2: Better Characterisations of Corepresentably Full Morphisms in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.11: Co/Limits
  - Proposition 8.4.11.1.1: Co/Limits in $\mathsf{Rel}$
- Subsection 8.4.12: Internal Kan Extensions and Lifts
  - Remark 8.4.12.1.1: Kan Extensions and Kan Lifts in $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.13: Closedness
  - Proposition 8.4.13.1.1: Closedness of $\boldsymbol {\mathsf{Rel}}$
- Subsection 8.4.14: $\mathsf{Rel}$ as a Category of Free Algebras
  - Proposition 8.4.14.1.1: $\mathsf{Rel}$ as a Category of Free Algebras
Section 8.5: The Adjoint Pairs $R_{!}\dashv R_{-1}$ and $R^{-1}\dashv R_{*}$
- Subsection 8.5.1: Direct Images
  - Definition 8.5.1.1.1: Direct Images
  - Remark 8.5.1.1.2: Unwinding Definition 8.5.1.1.1
  - Proposition 8.5.1.1.3: Properties of Direct Image Functions
  - Proposition 8.5.1.1.4: Properties of the Direct Image Function Operation
- Subsection 8.5.2: Strong Inverse Images
  - Definition 8.5.2.1.1: Strong Inverse Images
  - Remark 8.5.2.1.2: Unwinding Definition 8.5.2.1.1
  - Proposition 8.5.2.1.3: Properties of Strong Inverse Images
  - Proposition 8.5.2.1.4: Properties of the Strong Inverse Image Function Operation
- Subsection 8.5.3: Weak Inverse Images
  - Definition 8.5.3.1.1: Weak Inverse Images
  - Remark 8.5.3.1.2: Unwinding Definition 8.5.3.1.1
  - Proposition 8.5.3.1.3: Properties of Weak Inverse Image Functions
  - Proposition 8.5.3.1.4: Properties of the Weak Inverse Image Function Operation
- Subsection 8.5.4: Codirect Images
  - Definition 8.5.4.1.1: Codirect Images
  - Remark 8.5.4.1.2: Unwinding Definition 8.5.4.1.1
  - Proposition 8.5.4.1.3: Properties of Codirect Images
  - Proposition 8.5.4.1.4: Properties of the Codirect Image Function Operation
- Subsection 8.5.5: Functoriality of Powersets
  - Proposition 8.5.5.1.1: Functoriality of Powersets I
- Subsection 8.5.6: Functoriality of Powersets: Relations on Powersets
  - Definition 8.5.6.1.1: The Relation on Powersets Associated to a Relation
  - Remark 8.5.6.1.2: Unwinding Definition 8.5.6.1.1
  - Proposition 8.5.6.1.3: Functoriality of Powersets II
Section 8.6: The Left Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.1: The Left Skew Monoidal Product
  - Definition 8.6.1.1.1: The Left $J$-Skew Monoidal Product of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.2: The Left Skew Monoidal Unit
  - Definition 8.6.2.1.1: The Left $J$-Skew Monoidal Unit of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.3: The Left Skew Associators
  - Definition 8.6.3.1.1: The Left $J$-Skew Associator of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.4: The Left Skew Left Unitors
  - Definition 8.6.4.1.1: The Left $J$-Skew Left Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.5: The Left Skew Right Unitors
  - Definition 8.6.5.1.1: The Left $J$-Skew Right Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.6.6: The Left Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
  - Proposition 8.6.6.1.1: The Left $J$-Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
Section 8.7: The Right Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.1: The Right Skew Monoidal Product
  - Definition 8.7.1.1.1: The Right $J$-Skew Monoidal Product of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.2: The Right Skew Monoidal Unit
  - Definition 8.7.2.1.1: The Right $J$-Skew Monoidal Unit of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.3: The Right Skew Associators
  - Definition 8.7.3.1.1: The Right $J$-Skew Associator of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.4: The Right Skew Left Unitors
  - Definition 8.7.4.1.1: The Right $J$-Skew Left Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.5: The Right Skew Right Unitors
  - Definition 8.7.5.1.1: The Right $J$-Skew Right Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
- Subsection 8.7.6: The Right Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
  - Proposition 8.7.6.1.1: The Right $J$-Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: