Transitivity is the property of a relation: $R_{ab}\land R_{bc} \to R_{ac}$. Compositionality is an operation on functions: $\circ : (A\to B) \times (B \to C) \to (A \to C)$.

Intuitively, these are very similar. (In fact, the product $\times$ in the category of propositional logic is equal to $\land$, and functions are a subclass of relations).

Is there a deeper connection between these two concepts?

  • $\begingroup$ Well, given a category $C$, the "relation" $R$ on the objects of $C$ given by "$(A,B)\in R\iff $ there is a morphism from $A$ to $B$" is transitive. $\endgroup$ – Arthur Jan 30 at 16:35
  • $\begingroup$ @Arthur, yes, I thought of that, but the $\exists$ here drops information, and I find it not very elegant. $\endgroup$ – user56834 Jan 30 at 16:45
  • 2
    $\begingroup$ I don't know if this is what you're looking for, but: for a reflexive relation $R\subseteq X^2$, let $Ob_R=X$ and (for $a,b\in X$) set $Hom(a,b)=\{*_{a,b}: aRb\}$ (so $Hom(a,b)$ has a unique element iff $aRb$, and has no elements otherwise). Then $(Ob_R, (Hom(a,b))_{a,b\in Ob_R})$ forms a category iff $R$ is transitive, and in particular the act of composition here corresponds to the fact of transitivity of $R$. $\endgroup$ – Noah Schweber Jan 30 at 18:37
  • $\begingroup$ Another point is that Arthur's comment shows that composition is the categorification of transitivity : a morphism $f: A\to B$ is a witness that $ARB$, and composition says that given a witness $f$ that $ARB$, and a witness $g$ that $BRC$, we can get a new witness $g\circ f$ of $ARB$. In this sense, composition is a categorification of transitivity. $\endgroup$ – Max Jan 31 at 0:11
  • $\begingroup$ That can also be seen from the fact that a monad in the $2$-category $\mathbf{Rel}$ of sets, relations, and inclusions of relations is a preorder (reflexivity corresponds to identities); and a monad in the $2$-category $\mathbf{Span}$ of spans, pullbacks and compatible maps (which is a categorification of $\mathbf{Rel}$, because a span is nothing more than a relation with witnesses) is nothing but a category $\endgroup$ – Max Jan 31 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.