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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Michal R. Przybylek
    Commented 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$
    – Michal R. Przybylek
    Commented 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$
    – Michal R. Przybylek
    Commented 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
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .