Let there be three relations:

$g\subseteq D\times A\\ h\subseteq D\times B\\ R\subseteq(A\times B)\times C$

For the purposes of this post, the "composite of $R$ with $g$ and $h$," a subset of $D\times C$, is defined as

$R_{g,h}=\{(d,c)\in D\times C\mid \exists (d,x)\in g, (d,y)\in h \text{ such that } ((x,y),c)\in R\}$

I know the category Rel of binary relations uses sets as objects and relation as arrows, and relation composition (in the sense described here) as composition. Otherwise I have not worked in it, and to be honest it's a little bit weird.

I keep feeling like what's being described above is some simple categorical construct interpreted in Rel (like a pushout or some product), but it's hovering just outside of my grasp.

I'm faced with the given three arrows above, and the final arrow constructed with them, and I try to organize them in a diagram.

There should be an arrow from $D\to A\times B$ making a commutative diagram connecting $D,A,B$ and $A\times B$. Then $R$ gives this arrow to $C$, then naively I would look at the composition of arrows from $D$ to $A\times B$ to $C$, but I'm not sure this diagram is useful at all.

My two specific questions are:

  1. What's the interpretation of this composition categorically (if there is one)?

  2. Does it have a less bland name in the literature somewhere? (I would like to search for it.)


1 Answer 1


If I'm not mistaken, the relation $R_{g,h}$ is just $R\circ (g,h)$, where $(g,h) = g\times h \circ (\operatorname{id}_D, \operatorname{id}_D)$ is a relation from $D$ to $A\times B$.

The function / morphism $(\operatorname{id}_D, \operatorname{id}_D)$ is identified with its graph for the purpose of composing relations and $\times$ is just the Cartesian product applied to relations. So this makes sense categorically as well.

I don't know whether this has any special name.

  • $\begingroup$ Tell me if you need more details about the categorical constructions involved. $\endgroup$ Oct 10, 2017 at 15:34
  • $\begingroup$ OK, then I wasn't totally off when I suggested this composition. Thank you for help putting things in perspective. You might be interested in the one example that was given: $f_{I, w}$ where $I$ is the identity function on $\mathbb R$, $w$ is the function which is constantly $w$ on $\mathbb R$, and $f$ is a differentiable function $\mathbb R\to \mathbb R$. Look familiar? It appears in every calculus book, but definitely not in this guise... $\endgroup$
    – rschwieb
    Oct 10, 2017 at 16:29
  • $\begingroup$ @rschwieb Sorry, I don't get your example. With what kind of relations do you identify $f$ and $w$? If $w : \mathbb R \to \mathbb R$, then $f$ should be $\mathbb R^2 \to \mathbb R$. - In any case it is probably a good idea to put the example into the question to provide more context. $\endgroup$ Oct 10, 2017 at 16:41
  • $\begingroup$ Doh, you're right, I see what you mean. I haven't given $R$ correctly. Hang on... $\endgroup$
    – rschwieb
    Oct 10, 2017 at 17:17
  • $\begingroup$ Given a differentiable function $f$, use the relation $R^f(x,y)=\frac{f(x)-f(y)}{x-y}-f'(y)$ when $x\neq y$ and $R^f(x,x)=0$. Then compose $R^f_{I, w}$. Maybe not as amusing as I first found it. It's certainly a weird way to look at the difference quotient. $\endgroup$
    – rschwieb
    Oct 10, 2017 at 17:22

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.