Category of relations
|This article needs additional citations for verification. (August 2015) (Learn how and when to remove this template message)|
A morphism (or arrow) R : A → B in this category is a relation between the sets A and B, so R ⊆ A × B.
The composition of two relations R: A → B and S: B → C is given by:
- (a, c) ∈ S o R if (and only if) for some b ∈ B, (a, b) ∈ R and (b, c) ∈ S.
The involutory operation of taking the inverse (or converse) of a relation, where (b, a) ∈ R−1 : B → A if and only if (a, b) ∈ R : A → B, induces a contravariant functor Relop → Rel that leaves the objects invariant but reverses the arrows and composition. This makes Rel into a dagger category. In fact, Rel is a dagger compact category.
- Allegory (category theory). The category of relations is the paradigmatic example of an allegory.