Category of relations

In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms.

A morphism (or arrow) "R" : "A" → "B" in this category is a relation between the sets "A" and "B", so nowrap| "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".

Properties

Category Rel has the category of sets Set as a (wide) subcategory, where the arrow (function) nowrap| "f" : "X" → "Y" in Set corresponds to the functional relation nowrap| "F" ⊆ "X" × "Y" defined by: nowrap|1= ("x", "y") ∈ "F" ⇔ "f"("x") = "y".

Category Rel can be obtained from category Set as the Kleisli category for the monad whose functor corresponds to power set, interpreted as a covariant functor.

The involutary operation of taking the inverse (or converse) of a relation, where nowrap| ("b", "a") ∈ "R"⁻¹ : "B" → "A" if and only if nowrap| ("a", "b") ∈ "R" : "A" → "B", induces a contravariant functor nowrap| Rel^op → 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.

ee also

*Allegory (category theory). The category of relations is the paradigmatic example of an allegory.