ACT4E
Category Rel - Definition

Definition (Relation)

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

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\}$$