1
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\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$
    – Benjamin Steinberg
    Dec 30, 2020 at 19:09
  • $\begingroup$ What are the elements of the semigroup? $\endgroup$
    – David Pokorny
    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$
    – Benjamin Steinberg
    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$
    – Benjamin Steinberg
    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$
    – David Pokorny
    Dec 30, 2020 at 20:32

0

Reset to default

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.