Proof that Rel is a Category

Question

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).

Answer 1

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.

Answer 2

Even though this question was posted quite some time ago I feel like this exercise is very useful for anyone getting into category theory, which is why I provided a solution.

As Eric said, to show that $\mathbf{Rel}$ is a category we need to show that the identity arrows satisfy the identity law and the composition satisfies the associativity law.

Let $f: A \to B$ be a subset $f \subseteq A \times B$, $g: B \to C$ be subset $g \subseteq B \times C$, and $h: C \to D$ be a subset $h \subseteq C \times D$.

To show that $f \circ 1_A = f$, we use the axiom of extensionality (for both are sets). For the forward direction, let $(a, b) \in f \circ 1_A$. Then we see by definition that there exists some $p$ s.t. $(a, p) \in 1_A$ and $(p, b) \in f$. Since $(a, p) \in 1_A$ implies that $p=a$, we have that $(a, b) \in f$. For the backward direction, let $(a, b) \in f$. Moreover, since $(a, a) \in 1_A$, we have per definition that $(a, b) \in f \circ 1_A$. The argument that $1_B \circ f = f$ is similar.

For the associativity, we want to show that $(h \circ g) \circ f = h \circ (g \circ f)$. We know that \begin{align*} (a, d) \in (h \circ g) \circ f &\iff \exists b: (a, b) \in f, (b, d) \in (h \circ g) \\ &\iff \exists b, c: (a, b) \in f, (b, c) \in g, (c, d) \in h \\ &\iff \exists c: (a, c) \in (g \circ f), (c, d) \in h \\ &\iff (a, d) \in h \circ (g \circ f), \end{align*} which is what we wanted to show.