# What is the real name for the initial object in the category of "monoid-valued measures of intervals" on transitive relations?

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

• People would usually associate to a transitive relation the semigroup where you make zero any product not in the relation and have a 0 Dec 30, 2020 at 19:09
• What are the elements of the semigroup? Dec 30, 2020 at 19:21
• 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). Dec 30, 2020 at 19:39
• 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. Dec 30, 2020 at 19:41
• 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"? Dec 30, 2020 at 20:32