(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.)

  • $\begingroup$ People would usually associate to a transitive relation the semigroup where you make zero any product not in the relation and have a 0 $\endgroup$ Dec 30, 2020 at 19:09
  • $\begingroup$ What are the elements of the semigroup? $\endgroup$ Dec 30, 2020 at 19:21
  • $\begingroup$ The elements are pairs $(g,h)$ in the relation and a zero. Then the product if $(g,h)(k,l)=(g,l)$ if $h=k$ and 0 else and of course zero is a multiplicative zero. This is the quotient of your monoid by a certain ideal (except that I didn't include the identity). $\endgroup$ Dec 30, 2020 at 19:39
  • 1
    $\begingroup$ In all honesty though I think you should work with the semigroupoid (or semi-category) with objects $G$ and arrows $E$ where $(g,h)$ goes from $h$ to $g$ and the product is as you defined above. Then your interval measures are functors from this semigroupoid to the monoid (viewed as a one-object semigroupoid) and you don't have to worry about the issue that you interval measures aren't really homomorphisms. $\endgroup$ Dec 30, 2020 at 19:41
  • $\begingroup$ O.K. So (1) the elements of any transitive relation form a semigroupoid according to the product you defined, and (2) an interval measure is really a semigroupoid homomorphism. Every semigroupoid homomorphism with domain a transitive relation and codomain a monoid factors through the interval monoid. The elements in the category are then pairs, monoids together with homomorphisms (index map) from a fixed semigroupoid to the monoid, and the morphisms are monoid homomorphisms that commute with the index maps. Only one term remains: what is the real name for "interval monoid"? $\endgroup$ Dec 30, 2020 at 20:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.