# ACT4E Category Rel - Definition

###### Definition (Relation)

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

$R \subseteq X \times Y.$
###### Definition (Rel)

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\}$
##### Equivalent definition in relational algebra

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))$.