The Awodey book about Category Theory gives this definition for Rel:

The objects of $\text{Rel}$ are sets, and an arrow $A → B$ is a relation from $A$ to $B$, that is, a subset $R ⊆ A×B$.

The equality relation $ \{ \langle a, a\rangle ∈ A×A\;|\; a ∈ A\}$ is the identity arrow on a set $A$.

Composition in $\text{Rel}$ is to be given by: $$ S ◦ R = \{\langle a, c \rangle ∈ A × C \; |\; ∃b \;( \langle a, b\rangle ∈ R \; \text{ and }\; \langle b, c\rangle ∈ S) \}$$

for $R ⊆ A × B$ and $S ⊆ B × C$.

How can I actually prove that Rel is a category?

I'm not really into categories yet but this seem quite obvious since I know a category must have objects (that are the sets, in this case), arrows (relations), identity function (equality relation) and composition of functions (that is the association of relations).


What you've quoted is a definition of all the data needed to have a category: objects, morphisms, identity morphisms, and composition operation. To verify you have a category you then just have to check that this data satisfies the axioms for a category: that the identity morphisms are actually identities for the composition operation, and that composition is associative.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.