A demi ...

• ... is a 3-tuple $(X, F, \ell)$ where $\ell : F \to (X \to X)$
  • Intuition: $X$ is values, $F$ is actions, $\ell$ lifts actions into functions. Generalizes semigroups.
• ... with composition assumes $\exists \star \in F^2 \to F : \ell(a \star b) = \ell a \circ \ell b$
  • Intuition: this allows us to compose actions before lifting them
  • Intuition: associativity states that $\times(a \times b) = \times a \circ \times b$, which says that an operator is both a composition and a lift; demis decouple these two ideas.
• ... with identity assumes $\exists \zeta \in F : \ell \zeta = id$
  • Intuition: this gives is an identity action

Thoughts

• $(A, A \to A, id)$ is a demi with identity $\zeta = id$ and composition $\star = \circ$
• $(\Sigma^*, \mathbb N, \text{repeat})$ is a demi with identity $\zeta = 1$ and composition $\star = \times$
• $(A, B, \text{const})$ is a demi s.t. each $\zeta : B$ is an identity and each $\star : B^2 \to B$ is a composition
• $(\Sigma^*, \Sigma, \text{prepend or append})$ are demis without identity or composition
• $(\text{Set } a, a, \text{delete or insert})$ are demis without identity or composition
• Demis are a generalization of semigroups. This is motivated by the existence of the following injection $(\leftrightarrow)$ from semigroups to demis.
  • For any semigroup $(S, \times)$, let $(\rightarrow)(S, \times) = (S, S, \ell = \times, \star = \times)$. This is a demi with composition: since $\times$ is associative, then we know that $\times(a \times b) = \times a \circ \times b$, in other words, $\ell(a \star b) = \ell a \circ \ell b$, meaning that $\star$ is a composition.
  • For any demi with composition $(X, F, \ell, \star)$ where $X = F$ and $\ell = \star$, define $(\leftarrow)(S, S, \times, \times) = (S, \times)$. We now need to show that $\times$ is associative. $\times(f \times g) = \ell(f \star g) = \ell f \circ \ell g = \times f \circ \times g$. Done.
  • Now note that $(\leftarrow)\circ (\to) = id$; for some $(S, \times)$, see $(\leftarrow)(\to)(S, \times) = (S, \times)$. Also, $(\to) \circ (\leftarrow) = id$ for similarly trivial reasons.
  • Thus we have shown that the set of semigroups is isomorphic to a subset of demis with composition. This motivates demis as a generalization of semigroups.
  • Also, this gives a new perspective on semigroups:
• If we also assume a monoidal identity $\zeta \in S$, then $\zeta$ is also a demi identity; since it's a monoidal identity, then $\times \zeta = id$, and $\ell = \times$, so $\ell \zeta = id$.
• For a demi $(X, F, \ell)$, with $\ell$ bijective:
  • we get identity for free: $\zeta = \ell^{-1}(id)$
  • we get composition for free: $a \star b = \ell^{-1}(\ell a \circ \ell b)$.
• For a demi with composition $(X, F, \ell, \star)$, we aren't guaranteed that $\star$ is associative, but we are guaranteed that $\ell(a \star (b \star c)) = \ell((a \star b) \star c) = \ell a \circ \ell b \circ \ell c$
  • Counter-example to associativity of $\star$: consider the demi with composition $(X, F=\mathbb N, \ell=\text{const } id, \star=-)$ for any $X$.