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

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.

• What lecture notes are you working on ? – Maxime Ramzi Jan 19 '18 at 21:51
• – izzorts Jan 19 '18 at 22:14

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}\}.$$

• I was confused about the nature of $\mathcal{R}f$. But it seems all that is needed is to reinterpret $f$ as the relation $\Gamma(f)$ (since they are actually the same set/class), and consider that a morphism in Rel is a relation $r : X \rightarrow Y$, with r being a subset of $X \times Y$. Then $\Gamma(f)$ = $r_{AB}$ – izzorts Jan 19 '18 at 21:20

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.

• Although it wasn't clear to me, that was essentially what I was thinking of. Mainly, the problem was to perceive what exactly was to be understood by the arrows in Rel. More specifically, I was thinking of them as relations, as it evidently must be, but I was confused about how could them be a relation (what would imply it being a subset of $A \times B$) and yet an arrow from $A$ to $B$. The point was to see that the definition of a map $r$ in Rel is $r: A \rightarrow B$ $\coloneqq R \subseteq A \times B$. – izzorts Jan 21 '18 at 1:17
• Yeah! Sometimes there's just one piece of information missing. – user326210 Jan 21 '18 at 4:32