# nLab Rel

category theory

## Applications

#### Categories of categories

$\left(n+1,r+1\right)$-categories of (n,r)-categories

# $\mathrm{Rel}$

## Idea

Roughly, $\mathrm{Rel}$ is the category whose objects are sets and whose morphisms are (binary) relations between sets. It becomes a 2-category (in fact, a 2-poset) by taking 2-morphisms to be inclusions of relations.

## Definition

$\mathrm{Rel}$ is a 2-poset (a category enriched in the category of posets), whose objects or $0$-cells are sets, whose morphisms or $1$-cells $X\to Y$ are relations $R\subseteq X×Y$, and whose 2-morphisms or $2$-cells $R\to S$ are inclusions of relations. The composite $S\circ R$ of morphisms $R:X\to Y$ and $S:Y\to Z$ is defined by the usual relational composite

$\left\{\left(x,z\right)\in X×Z:{\exists }_{y\in Y}\left(x,y\right)\in R\wedge \left(y,z\right)\in S\right\}↪X×Z$\{(x, z) \in X \times Z: \exists_{y \in Y} (x, y) \in R \wedge (y, z) \in S\} \hookrightarrow X \times Z

and the identity ${1}_{X}:X\to X$ is the equality relation, in other words the usual diagonal embedding

$\left\{\left(x,x\right):x\in X\right\}↪X×X.$\{(x, x): x \in X\} \hookrightarrow X \times X.

Another important operation on relations is taking the opposite: any relation $R:X\to Y$ induces a relation

${R}^{\mathrm{op}}=\left\{\left(y,x\right)\in Y×X:\left(x,y\right)\in R\right\}↪Y×X$R^{op} = \{(y, x) \in Y \times X: (x, y) \in R\} \hookrightarrow Y \times X

and this operation obeys a number of obvious identities, such as $\left(S\circ R{\right)}^{\mathrm{op}}={R}^{\mathrm{op}}\circ {S}^{\mathrm{op}}$ and ${1}_{X}^{\mathrm{op}}={1}_{X}$.

## Relations and spans

It is useful to be aware of the connections between the bicategory of relations and the bicategory of spans. Recall that a span from $X$ to $Y$ is a diagram of the form

$X←S\to Y$X \leftarrow S \to Y

and there is an obvious category whose objects are spans from $X$ to $Y$ and whose morphisms are morphisms between such diagrams. The terminal span from $X$ to $Y$ is

$X\stackrel{{\pi }_{1}}{←}X×Y\stackrel{{\pi }_{2}}{\to }Y$X \stackrel{\pi_1}{\leftarrow} X \times Y \stackrel{\pi_2}{\to} Y

and a relation from $X$ to $Y$ is just a subobject of the terminal span, in other words an isomorphism class of monos into the terminal span.

To each span $S$ from $X$ to $Y$, there is a corresponding relation from $X$ to $Y$, defined by taking the image of the unique morphism of spans $S\to X×Y$ between $X$ and $Y$. It may be checked that this yields a lax morphism of bicategories

$\mathrm{Span}\to \mathrm{Rel}$Span \to Rel

## Relations in a category

More generally, given any regular category $C$, one can form a 2-category of relations $\mathrm{Rel}\left(C\right)$ in similar fashion. The objects of $\mathrm{Rel}\left(C\right)$ are objects of $C$, the morphisms $r:c\to d$ in $\mathrm{Rel}\left(C\right)$ are defined to be subobjects of the terminal span from $c$ to $d$, and 2-cells $r\to s$ are subobject inclusions. To form the composite of $r\subseteq c×d$ and $s\subseteq d×e$, one takes the image of the unique span morphism

$r{×}_{c}s\to c×e$r \times_c s \to c \times e

in the category of spans from $c$ to $e$, thus giving a mono into the terminal span from $c$ to $e$. The subobject class of this mono defines the relation

$s\circ r\subseteq c×e$s \circ r \subseteq c \times e

and the axioms of a regular category ensure that $\mathrm{Rel}\left(C\right)$ is a 2-category with desirable properties. Similar to what was said above, there is again a lax morphism of bicategories

$\mathrm{Span}\left(C\right)\to \mathrm{Rel}\left(C\right)$Span(C) \to Rel(C)

There is also a functor

$i:C\to \mathrm{Rel}\left(C\right)$i: C \to Rel(C)

that takes a morphism $f:c\to d$ to the functional relation defined by $f$, i.e., the relation defined by the subobject class of the mono

$⟨1,f⟩:c\to c×d$\langle 1, f\rangle: c \to c \times d

Such functional relations may also be characterized as precisely those 1-cells in $\mathrm{Rel}\left(C\right)$ which are left adjoints; the right adjoint of $⟨1,f⟩$ is the opposite relation $⟨f,1⟩$. The unit amounts to a condition

${1}_{c}\subseteq ⟨f,1⟩\circ ⟨1,f⟩$1_c \subseteq \langle f, 1 \rangle \circ \langle 1, f \rangle

which says that the functional relation is total, and the counit amounts to a condition

$⟨1,f⟩\circ ⟨f,1⟩\subseteq {1}_{d}$\langle 1, f \rangle \circ \langle f, 1 \rangle \subseteq 1_d

which says the functional relation is well-defined.

For generalizations of $\mathrm{Rel}$ see

category: category

Revised on October 30, 2012 20:00:43 by Urs Schreiber (131.174.189.66)