(I'm not asking for a true/false answer; I have a true algebraic fact and I'm looking for a reference in the literature. By the way, there is a version of this theorem that replaces monoid with $R$-module, monoid multiplication with module addition, and monoid homomorpism with $R$-linear transformation where $R$ is a commutative ring.)

Let $G$ be a set and $E$ a transitive non-empty binary relation on $G$. (Note: to obtain such a relation from any directed graph, just take the transitive closure of the edges.) Let $F_0 = \langle (g,h)\colon g\,E\,h \wedge g,h\in G\rangle = \langle E \rangle$ be the free monoid generated by the edges, and let $\sim$ be the congruence on $F_0$ generated by $(g,i)\sim(g,h)(h,i)$ for all $g,h,i\in G$ such that $(g,i),(g,h),(h,i)\in E$. Let $F=F_0/\sim$ be the *interval monoid* for $E$.

Let $G$ be a set, $E$ a transitive non-empty binary relation on $G$, and $W$ a monoid. An *interval measure* on $(G,E)$ taking values in $W$ is a map $I\colon E\rightarrow W$ such that $I(g,h)\,I(h,i)=I(g,i)$ for all $g,h,i\in G$ and $(g,h),(h,i),(g,i)\in E$.

The following theorem says that the interval monoid is the initial object in the category with objects the interval measures and morphisms the measure-preserving monoid homomorphisms. (A morphism of interval measures $(W,I)$ to $(V,J)$, $\varphi\colon W\rightarrow V$, must be both a monoid homomorphism and satisfy $J(g,h)=\varphi(I(g,h))$ for all $g,h\in G$.)

Theorem. Let $G,E$ and $F$ be as above. For every monoid $W$ and interval measure $I$ on $(G,E)$ taking values in $W$, there exists a unique monoid homomorphism $J\colon F\rightarrow W$ such that $J(s,t)=I(s,t)$ for all $(s,t)\in E$.

Proof. (Almost trivial.)

7more comments