Category Rel - Definition

Definition (Relation)

Let XX and YY be sets. A relation RR from XX to YY is a subset

RX×Y. R \subseteq X \times Y.
Definition (Rel)

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

  • Objects: all sets;
  • Morphisms: For sets XX and YY, the set Hom Rel(X,Y)\text{Hom}_{\mathbf{Rel}}(X,Y) is the set of all relations from XX to YY;
  • Identity morphisms: For a set XX, its identity morphism id X\text{id}_X is the identity relation on XX, id X={(a,a)|aX}\text{id}_X = \{(a,a) | a \in X\};
  • Composition: For relations f:XY,g:YZf: X \rightarrow Y, g: Y \rightarrow Z, the composite (f;g):XZ(f;g): X \rightarrow Z is given by:
    {(x,z)|xX,zZ,there existsyYs.t.(x,y)fand(y,z)g} \{(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 ff and gg is their inner join on constraint codomain(f)=domain(g)\text{codomain}(f) = \text{domain}(g), then projected so that (domain,codomain)=(domain(f)(\text{domain}, \text{codomain}) = (\text{domain}(f), codomain(g))\text{codomain}(g)).