Show that the graph $\Gamma(f)$ of a function defines a functor from $\mathbf{Set}$ to $\mathbf{Rel}$

Question

Recently I have started studying the very basics of category theory by myself, but since I'm using just some lecture notes (with are pretty concise and are more directed to categorical logic), I'm quite lost on how to deal with the few exercises I'm supposed to work on. One of them is this:

Show that taking the graph $\Gamma(f) = \{ (x, f(x))$, $x \in A \}$ of a function $f : A \rightarrow B$ defines a functor from $\mathbf{Set}$ to $\mathbf{Rel}$, which acts as identity over the objects

where Set is the category of sets with functions as morphisms and Rel, although not yet defined in the notes, I suppose is the category whose objects are sets and morphisms are relations. This exercise is in the section of forgetful functors, by the way.

What I've tried was pretty naive, essentially I've started arguing that $\Gamma$ is a subset of $A \times B$, hence a relation, but I couldn't manage to devise a functor $\mathcal{R}$ s.t. $\mathcal{R}f : A \rightarrow B$ (implicitly using that $\mathcal{R}x = x, \forall x \in \mathbf{Set}_0$) that is a relation over $A \times B$, which actually doesn't even seem to be possible and therefore suggests me that I may have assumed what Rel is wrongly.

Answer 1

I think you are getting confused about something here, though I'm not quite sure what. As you say, $\Gamma(f)$ is a subset of $A\times B$, so it is a relation from $A$ to $B$. So, you can just define $\mathcal{R}f=\Gamma(f)$.

To be clear, the objects of the category $\mathbf{Rel}$ are sets, and a morphism $A\to B$ in $\mathbf{Rel}$ is a relation from $A$ to $B$, i.e. a subset of $A\times B$. Composition is the usual composition of relations: if $R\subseteq A\times B$ and $S\subseteq B\times C$ then their composition is $$S\circ R=\{(a,c):\text{there exists $b\in B$ such that $(a,b)\in R$ and $(b,c)\in S$}\}.$$

Answer 2

Let's start by agreeing on a definition of the category Rel. The objects in the category Rel are sets. The arrows in the category Rel are relations. A relation between $A$ and $B$ is any subset of $A\times B$. Composition of relations is defined as follows: if $R$ is a relation between $A$ and $B$, and $S$ is a relation between $B$ and $C$, then $S\circ R$ is the composed relation between $A$ and $C$; it's defined by:

$$S\circ R = \{\langle a, c\rangle : \exists b\in B : aRb \text{ and }bSc\}$$

And every set $A$ has an identity relation $id_{A}:A\times A$, which is defined by:$$id_A = \{\langle a, a\rangle : a\in A\}$$

(You can verify that composing any relation with the identity yields the original relation, as required.)

---

1. A functor from Set to Rel is a function mapping sets and functions (in Set) to sets and relations (in Rel).

2. The map which sends every function $f$ to its graph $\Gamma(f)$ does send each function (in Set) to some relation (in Rel). All we need to prove is that it is "functorial"; that is, that it preserves identities and composition.

3. And indeed, first we note that it behaves properly on objects: it sends functions $A\rightarrow B$ to relations on $A \times B$.

4. And it preserves identities because it sends each identity function in Set $1_A : A \rightarrow A$ to the graph $\Gamma(1_A)$ in Rel; this graph is the identity relation $id_A : A\times A = \{\langle a,a\rangle : a\in A\}$.

5. And it preserves composition: if $f:B\leftarrow A$ and $g:C\leftarrow B$, then $(g\circ f):C\leftarrow A$, and the graph of $(g\circ f)$ is actually the composition of the graph of $g$ and the graph of $f$. (The composition of two relations is defined in the expected way.)

6. This shows that the graph construction is a functor.