# Is there a formal connection between transitivity and compositionality?

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?

• 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. – Arthur Jan 30 at 16:35
• @Arthur, yes, I thought of that, but the $\exists$ here drops information, and I find it not very elegant. – user56834 Jan 30 at 16:45
• 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$. – Noah Schweber Jan 30 at 18:37
• 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. – Max Jan 31 at 0:11
• 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 – Max Jan 31 at 0:11