# Which are the natural morphisms between binary relations?

Which properties should morphisms $\alpha$ between binary relations have?

$(1) \qquad R \overset \alpha \longrightarrow R\,', \;R\subseteq X\times Y, \;R\,'\subseteq X'\times Y'$

Can those properties be expressed as relations $M_1$, $M_2$ below?

$(2) \qquad M_1\subseteq X\times X', \;M_2\subseteq Y\times Y'$

If so, is the diagram commutative then? $\require{AMScd}$ \begin{CD} X @>M_1>> X'\\ @VRV V @VV R\,'V\\ Y @>>M_2> Y' \end{CD} Except for the commutative condition there is an other natural condition considering $R$ and $R\,'$ as (bipartite) graphs:

$(3) \qquad (x,x')\in M_1\wedge(y,y')\in M_2\Rightarrow [(x,y)\in R\Rightarrow (x',y')\in R\,']$

There is a counter-example below showing that the condition on the diagram being commutative, not in general imply $(3)$, if $M_1$ and $M_2$ not are functions.

What about if $M_1$ and $M_2$ are functions?

Counter-example? $X=X'=Y=Y'=\mathbb{N}$ and $R=R\,'=M_1=M_2\wedge [(x,y)\in R \Leftrightarrow x<y]$

## 1 Answer

I think the most natural definition might just be

A morphism of relations $\alpha\colon R\to R'$ is a pair $(M_1,M_2)$ of relations $M_1\colon X\to X'$ and $M_2\colon Y\to Y'$ such that $R'\circ M_1=M_2\circ R$.

This definition at least makes the class of relations and morphisms into a category, and your diagram commutes by definition. You could of course restrict the hom sets to just functions making the diagram commute. I'm not sure how interesting these two categories are though.

• Do you think that the morphism should have the property that $(x,y)\in R \wedge ((x,y),(x',y'))\in\alpha \Rightarrow (x',y')\in R'$? If so, can you prove that for your suggestion? – Lehs Aug 28 '14 at 21:06
• $M_1$ is a subset of $X\times X'$, not $X\times Y$ (similarly for $M_2$). Did you mean something else? – Dan Rust Aug 28 '14 at 21:09
• No, but I just call the morphism $\alpha$. I mean $((x,y),(x',y'))\in\alpha\Leftrightarrow (x,x')\in M_1 \wedge (y,y')\in M_2$. Have I made a mistake? – Lehs Aug 28 '14 at 21:13
• Ah I see. Suppose for $y\in Y$, we have $(x,y)\in R$ and $(y,y')\in M_2$. Then $(x,y')\in M_2\circ R$ and so $(x,y')\in R'\circ M_1$. It follows that there must exist some $x'\in X'$ such that $(x,x')\in M_1$ and $(x',y')\in R'$. Is this the sort of thing you wanted? – Dan Rust Aug 28 '14 at 21:24
• What I would like is: if $(x,x')\in M_1 \wedge (y,y')\in M_2$, then $(x,y)\in R \Rightarrow (x',y')\in R'$. And I wonder if that can be proved from the commuting construction? – Lehs Aug 28 '14 at 21:32