2

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.

Community
  • 1
Lehs
  • 852

2 Answers2

3

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.

Michal R. Przybylek
  • 4,096
  • 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)? – Lehs Aug 30 '14 at 11:39
  • @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) – Michal R. Przybylek Aug 30 '14 at 14:18
  • 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. – Michal R. Przybylek Aug 30 '14 at 14:19
  • Another question is whether one condition implies the other, but this is a simple student exercise and as such is not suitable for MO :-) – Michal R. Przybylek Aug 30 '14 at 14:20
  • 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. – Lehs Aug 30 '14 at 18:14
  • And I don't understand your arguing towards the implication $(1)\Rightarrow (2)$ - didn't you noticed the counter-example? – Lehs Aug 30 '14 at 18:43
  • @Lehs, the counter-example to what? Because I have proven my claim, there are no counter-examples to it :-) – Michal R. Przybylek Aug 30 '14 at 19:22
  • @Lehs, I am always happy when someone downvotes my answers --- it means that what I have written is not completely trivial :-) However, I think that downvoting an answer from someone who is trying to help you and make your student-level question a bit more interesting is a really strange way to say "thank you". Anyway, I have just made my final edit --- you may still be unhappy with it, but on no condition I will provide you a student-level (i.e. a low-level) answer to the question --- MO is not the right place to provide such answers. – Michal R. Przybylek Aug 31 '14 at 12:14
  • @MichalR.Przybylek i just checked Lehs reputation and it does not seem that he downvoted your answer. You can see this by noticing that he did not lose any reputation since starting in MO . Normally when one downvotes, he/she loses 1 rep. – magma Aug 31 '14 at 14:39
  • @magma: I sure have been downvoted several times. First I maid an upvote for mr MichalR.Przybyleks answer just because hes answer seemed somewhat interesting. When I realized it wasn't interesting and never was meant to be, I found to my great pleasure that he lost 2 votes when I voted him down. – Lehs Aug 31 '14 at 20:30
  • @MichalR.Przybylek: I accepted your answer, because your answer is perfectly right, I just didn't see it. Thank you very much! It sure was a simple explanation, but I was unable to see it. – Lehs Aug 31 '14 at 20:51
  • @MichalR.Przybylek: No! Your answer is not adequate! My condition is not equivalent with your reversed arrow commutativity. – Lehs Sep 01 '14 at 05:33
1

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.

Lehs
  • 852