# 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]$

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$.
• 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