Category Rel - Definition

Let $X$ and $Y$ be sets. A relation $R$ from $X$ to $Y$ is a subset

$R \subseteq X \times Y.$

The category of sets and relations $\mathbf{Rel}$ consists of:

*Objects*: all sets;*Morphisms*: For sets $X$ and $Y$, the set $\text{Hom}_{\mathbf{Rel}}(X,Y)$ is the set of all relations from $X$ to $Y$;*Identity morphisms*: For a set $X$, its identity morphism $\text{id}_X$ is the identity relation on $X$, $\text{id}_X = \{(a,a) | a \in X\}$;*Composition*: For relations $f: X \rightarrow Y, g: Y \rightarrow Z$, the composite $(f;g): X \rightarrow Z$ is given by:$\{(x,z) | x \in X, z \in Z, \text{there exists} \ y \in Y\ \text{s.t.} \ (x,y) \in f \ \text{and} \ (y,z) \in g\}$

The composition of binary relations $f$ and $g$ is their inner join on constraint $\text{codomain}(f) = \text{domain}(g)$, then projected so that $(\text{domain}, \text{codomain}) = (\text{domain}(f)$, $\text{codomain}(g))$.