5 Relations
This chapter contains some material about relations. Notably, we discuss and explore:
-
The definition of relations (Section 5.1.1).
-
How relations may be viewed as decategorification of profunctors (Section 5.1.2).
-
The various kind of categories that relations form, namely:
-
A category (Section 5.2.1).
-
A monoidal category (Section 5.2.2).
-
A $2$-category (Section 5.2.3).
-
A double category (Section 5.2.4).
-
The various categorical properties of the $2$-category of relations, including:
-
The self-duality of $\mathsf{Rel}$ and $\textbf{Rel}$ (Proposition 5.3.1.1.1).
-
Identifications of equivalences and isomorphisms in $\textbf{Rel}$ with bijections (Proposition 5.3.2.1.1).
-
Identifications of adjunctions in $\textbf{Rel}$ with functions (Proposition 5.3.3.1.1).
-
Identifications of monads in $\textbf{Rel}$ with preorders (Proposition 5.3.4.1.1).
-
Identifications of comonads in $\textbf{Rel}$ with subsets (Proposition 5.3.5.1.1).
-
A description of the monoids and comonoids in $\textbf{Rel}$ with respect to the Cartesian product (Remark 5.3.6.1.1).
-
Characterisations of monomorphisms in $\mathsf{Rel}$ (Proposition 5.3.7.1.1).
-
Characterisations of $2$-categorical notions of monomorphisms in $\textbf{Rel}$ (Proposition 5.3.8.1.1).
-
Characterisations of epimorphisms in $\mathsf{Rel}$ (Proposition 5.3.9.1.1).
-
Characterisations of $2$-categorical notions of epimorphisms in $\textbf{Rel}$ (Proposition 5.3.10.1.1).
-
The partial co/completeness of $\mathsf{Rel}$ (Proposition 5.3.11.1.1).
-
The existence or non-existence of Kan extensions and Kan lifts in $\mathsf{Rel}$ (Remark 5.3.12.1.1).
-
The closedness of $\textbf{Rel}$ (Proposition 5.3.13.1.1).
-
The identification of $\textbf{Rel}$ with the category of free algebras of the powerset monad on $\mathsf{Sets}$ (Proposition 5.3.14.1.1).
-
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 5.4 and Section 5.5).
-
Section 5.1: Relations
-
Subsection 5.1.1: Foundations
-
Definition 5.1.1.1.1: Relations
-
Notation 5.1.1.1.2: Further Notation for Relations
-
Definition 5.1.1.1.3: The Po/Set of Relations Over Two Sets
-
Remark 5.1.1.1.4: Equivalent Definitions of Relations
-
Proposition 5.1.1.1.5: Properties of Relations
-
Subsection 5.1.2: Relations as Decategorifications of Profunctors
-
Remark 5.1.2.1.1: Relations as Decategorifications of Profunctors I
-
Remark 5.1.2.1.2: Relations as Decategorifications of Profunctors II
-
Subsection 5.1.3: Examples of Relations
-
Subsection 5.1.4: Functional Relations
-
Definition 5.1.4.1.1: Functional Relations
-
Proposition 5.1.4.1.2: Properties of Functional Relations
-
Subsection 5.1.5: Total Relations
-
Definition 5.1.5.1.1: Total Relations
-
Proposition 5.1.5.1.2: Properties of Total Relations
-
Section 5.2: Categories of Relations
-
Subsection 5.2.1: The Category of Relations
-
Definition 5.2.1.1.1: The Category of Relations
-
Subsection 5.2.2: The Closed Symmetric Monoidal Category of Relations
-
Subsubsection 5.2.2.1: The Monoidal Product
-
Definition 5.2.2.1.1: The Monoidal Product of $\mathsf{Rel}$
-
Subsubsection 5.2.2.2: The Monoidal Unit
-
Definition 5.2.2.2.1: The Monoidal Unit of $\mathsf{Rel}$
-
Subsubsection 5.2.2.3: The Associator
-
Definition 5.2.2.3.1: The Associator of $\mathsf{Rel}$
-
Subsubsection 5.2.2.4: The Left Unitor
-
Definition 5.2.2.4.1: The Left Unitor of $\mathsf{Rel}$
-
Subsubsection 5.2.2.5: The Right Unitor
-
Definition 5.2.2.5.1: The Right Unitor of $\mathsf{Rel}$
-
Subsubsection 5.2.2.6: The Symmetry
-
Definition 5.2.2.6.1: The Symmetry of $\mathsf{Rel}$
-
Subsubsection 5.2.2.7: The Internal Hom
-
Definition 5.2.2.7.1: The Internal Hom of $\mathsf{Rel}$
-
Proposition 5.2.2.7.2: Properties of the Internal Hom of $\mathsf{Rel}$
-
Subsubsection 5.2.2.8: The Closed Symmetric Monoidal Category of Relations
-
Proposition 5.2.2.8.1: The Closed Symmetric Monoidal Category of Relations
-
Subsection 5.2.3: The $2$-Category of Relations
-
Definition 5.2.3.1.1: The $2$-Category of Relations
-
Subsection 5.2.4: The Double Category of Relations
-
Subsubsection 5.2.4.1: The Double Category of Relations
-
Definition 5.2.4.1.1: The Double Category of Relations
-
Subsubsection 5.2.4.2: Horizontal Identities
-
Definition 5.2.4.2.1: The Horizontal Identities of $\mathsf{Rel}^{\mathsf{dbl}}$
-
Subsubsection 5.2.4.3: Horizontal Composition
-
Definition 5.2.4.3.1: The Horizontal Composition of $\mathsf{Rel}^{\mathsf{dbl}}$
-
Subsubsection 5.2.4.4: Vertical Composition of 2-Morphisms
-
Definition 5.2.4.4.1: The Vertical Composition of 2-Morphisms in $\mathsf{Rel}^{\mathsf{dbl}}$
-
Subsubsection 5.2.4.5: The Associators
-
Definition 5.2.4.5.1: The Associators of $\mathsf{Rel}^{\mathsf{dbl}}$
-
Subsubsection 5.2.4.6: The Left Unitors
-
Definition 5.2.4.6.1: The Left Unitors of $\mathsf{Rel}^{\mathsf{dbl}}$
-
Subsubsection 5.2.4.7: The Right Unitors
-
Definition 5.2.4.7.1: The Right Unitors of $\mathsf{Rel}^{\mathsf{dbl}}$
-
Section 5.3: Properties of the $2$-Category of Relations
-
Subsection 5.3.1: Self-Duality
-
Proposition 5.3.1.1.1: Self-Duality for the (2-)Category of Relations
-
Subsection 5.3.2: Isomorphisms and Equivalences in $\textbf{Rel}$
-
Proposition 5.3.2.1.1: Isomorphisms and Equivalences in $\textbf{Rel}$
-
Subsection 5.3.3: Adjunctions in $\textbf{Rel}$
-
Proposition 5.3.3.1.1: Adjunctions in $\textbf{Rel}$
-
Subsection 5.3.4: Monads in $\textbf{Rel}$
-
Proposition 5.3.4.1.1: Monads in $\textbf{Rel}$
-
Subsection 5.3.5: Comonads in $\textbf{Rel}$
-
Proposition 5.3.5.1.1: Comonads in $\textbf{Rel}$
-
Subsection 5.3.6: Co/Monoids in $\textbf{Rel}$
-
Remark 5.3.6.1.1: Co/Monoids in $\textbf{Rel}$
-
Subsection 5.3.7: Monomorphisms in $\mathsf{Rel}$
-
Proposition 5.3.7.1.1: Characterisations of Monomorphisms in $\mathsf{Rel}$
-
Subsection 5.3.8: 2-Categorical Monomorphisms in $\textbf{Rel}$
-
Proposition 5.3.8.1.1: 2-Categorical Monomorphisms in $\textbf{Rel}$
-
Question 5.3.8.1.2: Better Characterisations of Representably Full Morphisms in $\textbf{Rel}$
-
Subsection 5.3.9: Epimorphisms in $\mathsf{Rel}$
-
Proposition 5.3.9.1.1: Characterisations of Epimorphisms in $\mathsf{Rel}$
-
Subsection 5.3.10: 2-Categorical Epimorphisms in $\textbf{Rel}$
-
Proposition 5.3.10.1.1: 2-Categorical Epimorphisms in $\textbf{Rel}$
-
Question 5.3.10.1.2: Better Characterisations of Corepresentably Full Morphisms in $\textbf{Rel}$
-
Subsection 5.3.11: Co/Limits in $\mathsf{Rel}$
-
Proposition 5.3.11.1.1: Co/Limits in $\mathsf{Rel}$
-
Subsection 5.3.12: Kan Extensions and Kan Lifts in $\textbf{Rel}$
-
Remark 5.3.12.1.1: Kan Extensions and Kan Lifts in $\textbf{Rel}$
-
Subsection 5.3.13: Closedness of $\textbf{Rel}$
-
Proposition 5.3.13.1.1: Closedness of $\textbf{Rel}$
-
Subsection 5.3.14: $\textbf{Rel}$ as a Category of Free Algebras
-
Proposition 5.3.14.1.1: $\textbf{Rel}$ as a Category of Free Algebras
-
Section 5.4: The Left Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.1: The Left Skew Monoidal Product
-
Definition 5.4.1.1.1: The Left $J$-Skew Monoidal Product of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.2: The Left Skew Monoidal Unit
-
Definition 5.4.2.1.1: The Left $J$-Skew Monoidal Unit of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.3: The Left Skew Associators
-
Definition 5.4.3.1.1: The Left $J$-Skew Associator of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.4: The Left Skew Left Unitors
-
Definition 5.4.4.1.1: The Left $J$-Skew Left Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.5: The Left Skew Right Unitors
-
Definition 5.4.5.1.1: The Left $J$-Skew Right Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.4.6: The Left Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
-
Proposition 5.4.6.1.1: The Left $J$-Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
-
Section 5.5: The Right Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.1: The Right Skew Monoidal Product
-
Definition 5.5.1.1.1: The Right $J$-Skew Monoidal Product of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.2: The Right Skew Monoidal Unit
-
Definition 5.5.2.1.1: The Right $J$-Skew Monoidal Unit of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.3: The Right Skew Associators
-
Definition 5.5.3.1.1: The Right $J$-Skew Associator of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.4: The Right Skew Left Unitors
-
Definition 5.5.4.1.1: The Right $J$-Skew Left Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.5: The Right Skew Right Unitors
-
Definition 5.5.5.1.1: The Right $J$-Skew Right Unitor of $\mathbf{Rel}\webleft (A,B\webright )$
-
Subsection 5.5.6: The Right Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$
-
Proposition 5.5.6.1.1: The Right $J$-Skew Monoidal Structure on $\mathbf{Rel}\webleft (A,B\webright )$