2
$\begingroup$

For the category of functions, pairs of functions making commutative diagrams are the canonical morphisms $\alpha:f\rightarrow g$. For binary relations there is an alternative, to consider the relations as (bipartite) graphs with canonical morphisms that preserves the graph structure. $\require{AMScd}$ \begin{CD} X @>M_1>> X'\\ @VRV V @VV R\,'V\\ Y @>>M_2> Y' \end{CD} $(1)\quad$ $R\,'\circ M_1=M_2\circ R$

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

In general, $(1)$ do not imply $(2)$. Define $(x,y)\in S \Leftrightarrow x\leq y$: \begin{CD} \mathbb{N} @>S>> \mathbb{N}\\ @VSV V\# @VV SV\\ \mathbb{N} @>>S> \mathbb{N} \end{CD} The diagram is trivially commutative, but of course $x\leq x'\wedge y\leq y'\wedge x\leq y \nRightarrow x'\leq y'$.

The condition $(2)$ is a generalization of $(1)$ and they are equivalent in case of functions.

Both $(1)$ and $(2)$ meets the conditions for morphisms, but which is the "most natural"?

Do $(1)$ imply $(2)$ for functions $M_1,M_2$?

The latter alternative gives a category of (simple) mathematical structures, with objects $F(X)\longrightarrow X$, for some functor $F$ on Rel, with some interesting properties that I have tried to indicate here and there.


I asked similar questions on Mathematics. And a related question also on Mathematics.

$\endgroup$

2 Answers 2

3
$\begingroup$

If you write your diagram in the right way: $$\begin{CD} X @<M^{co}_1<< X'\\ @VRV V @VV R\,'V\\ Y @>>M_2> Y' \end{CD}$$ (where $M^{co}_1 \colon X' \rightarrow X$ is obtained from $M_1 \colon X \rightarrow X'$ by swapping domain with codomain) and restate the second condition in the right way: $$(x',x)\in M^{co}_1 \wedge (x,y)\in R \wedge (y,y')\in M_2 \Rightarrow (x',y')\in R\,'$$ then it will become obvious, that your condition says that the diagram is weakly commutative --- i.e. it is commutative up to a 2-morphism in $\mathit{Rel}$ (recall that $\mathit{Rel}$ has a 2-categorical structure):

$$M_2 \circ R \circ M_1^{co} \leq R'$$

Therefore, you have described two different constructions over a (2-)category. Which is "more natural", depends on your applications.


I do not want to go into unnecessary detail, but here is an abstract argument why (1) implies (2) if $M_1$ is a function. Let us assume that: $$M_2 \circ R = R' \circ M_1$$ Because $M_1$ is a function, it has a right adjoint relation $M_1^\mathit{co}$. Now, we may postcompose our expression with $M_1^\mathit{co}$ to obtain $M_2 \circ R \circ M_1^\mathit{co} = R' \circ M_1 \circ M_1^\mathit{co}$. However, since $M_1^\mathit{co}$ is right adjoint to $M_1$, there is evaluation $M_1 \circ M_1^\mathit{co} \leq \mathit{id}$. Thus: $$M_2 \circ R \circ M_1^\mathit{co} = R' \circ M_1 \circ M_1^\mathit{co} \leq R' \circ \mathit{id} = R'$$

In fact, the above proof works in a more general context of any single-valued relation $M_1$. Moreover, this is the optimal general condition --- if $M_1$ is not single-valued, then one may easily find $R, R', M_2$ such that (1) is true, but (2) does not hold.

$\endgroup$
12
  • $\begingroup$ That was a nice way to show that (2) implies half (1). But there is a significant difference between (1) and (2), and I wonder if there are any interesting categories using (1)? $\endgroup$
    – Lehs
    Aug 30, 2014 at 11:39
  • $\begingroup$ @Lehs, I am not sure if I understand you --- I meant that given any 2-category $\mathbb{C}$, you may build a category of "weakly commutative twisted diagrams", whose objects are morphisms $R \colon X \rightarrow Y$, $R' \colon X' \rightarrow Y'$ in $\mathbb{C}$ and whose morphisms from $R$ to $R'$ are triples $\langle M \colon X' \rightarrow X, N \colon Y \rightarrow Y', \tau \colon N \circ R \circ M \rightarrow N \rangle$, where $M, N$ are morphisms in $\mathbb{C}$ and $\tau$ is a 2-morphism in $\mathbb{C}$. (cont) $\endgroup$ Aug 30, 2014 at 14:18
  • $\begingroup$ Your construction is exactly the above construction for $\mathbb{C} = \mathbf{Rel}$ --- you have just "relabeled" $N$ with $M_2$, and $M$ with $M_1^\mathit{co}$. In other words, because the category of relations is self-dual, you could mistakenly write relation $M_1$ in the wrong direction. I think, this is the crucial observation --- that you drew a wrong diagram. I am writing about this, because I made a very similar "mistake" once --- I drew a distributor in "a wrong direction", and it took me a few days until I realized, that the property I had been looking for was completely obvious. $\endgroup$ Aug 30, 2014 at 14:19
  • $\begingroup$ Another question is whether one condition implies the other, but this is a simple student exercise and as such is not suitable for MO :-) $\endgroup$ Aug 30, 2014 at 14:20
  • $\begingroup$ I would have loved an "reversed arrow" solution, because that would have solved a heuristic problem. I haven't tried to make a category theoretical construction, but found that the "canonical" morphisms between relations in a concrete category wasn't canonical at all and that there are an other condition on the diagram that prompts for some attention. $\endgroup$
    – Lehs
    Aug 30, 2014 at 18:14
1
$\begingroup$

By reconsidering facts I've come to the conclusion that there might be several morphisms to be used in categories with binary relations $ R\subseteq X\times Y$, eventually depending on the interpretation of the objects. $\require{AMScd}$ \begin{CD} X @>M_1>> X'\\ @VRV V ?@VV R\,'V\\ Y @>>M_2> Y' \end{CD}

Alternative morphisms:

  1. Two arbitrary relations $M_1,M_2$, that does not preserve anything.
  2. Two arbitrary functions $M_1,M_2$, that does not preserve anything.
  3. Two relations $M_1,M_2$ such that $(x,x')\in M_1\wedge(y,y')\in M_2\Rightarrow [(x,y)\in R\Rightarrow (x',y')\in R']$
  4. Two functions $M_1,M_2$ such that $(x,y)\in R\Rightarrow (M_1(x),M_2(y))\in R'$
  5. An arbitrary relation $\rho\subset R\times R'$
  6. An arbitrary function $f\subset R\times R'$
  7. $M_1$ and $M_2$ are such that $M_2\circ R\circ M_1^{op}=R'$, that is the diagram is commutative for reversed arrow with $M_1^{op}$. (7 implies 3).
  8. $M_2\circ R\subseteq R'\circ M_1$
  9. Commutative diagram. (If $M_1$ and $M_2$ are functions all alternatives except 1 gives commutative diagrams).

There are even some more, but perhaps also some of the conditions are equivalent.

In Abstract and Concrete Categories (p. 22) the category of binary relations $R\subseteq X\times X$ on a set $X$ is called Rel and have morphisms in accordance with 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.