Name for mathematical structure that generalizes function composition and application

Question

I was wondering what the name is for a mathematical structure equipped with two operations, composition ($\circ$ or juxtaposition) and application ($\cdot [ \cdot ]$) where the two operations satisfy the following laws. It's a bit like a category, but also has application and constrains application to distribute over composition. It's possible that it's just a category equipped with additional structure and doesn't have a specific name.

composition is associative when defined✱.

$$ a \circ bc \sqsubseteq ab \circ c $$ $$ a \circ bc \sqsupseteq ab \circ c $$

application distributes over compoisiton when defined

$$ f[ab] \sqsubseteq f[a] \circ f[b] $$ $$ f[ab] \sqsupseteq f[a] \circ f[b] $$

---

For motivation, consider a monoid $A$ with operation $+$ . Consider a homomorphism $f$ from $A$ to $B$. Further suppose that $B \subseteq A$ and is therefore a submonoid of $A$ . So we have

$$ f : A \to B $$

where

$$ f[a+b] = f[a] \circ_{\small{B}} f[b] = f[a] + f[b]$$

I was trying to figure out how to create a larger structure with some new term based on $f$ as an element, i.e. $A^* \stackrel{\small{df}}{=} A \cup \{ \; (\cdots f \cdots ) \; \} $ , but there didn't seem to be a general way to get a new element based on $f$ that was "on the same plane" as the elements of $A$ .

However, the endomorphisms on $A$ themselves form a monoid, $\text{End}(A)$ .

$A \cup \text{End}(A)$ with application given by endomorphism application (where defined) and composition given by $\circ_{\small{A}}$ or $\circ_{\small\text{End}(A)}$ seems like a reasonable object in its own right. At most one of the composition operators is defined for any pair of items in $A \cup \text{End}(A)$ . Since $\text{End}(A)$ is a monoid, we can iterate the construction $A \cup \text{End}(A) \cup \text{End}(\text{End}(A)) \cdots $ and get back an "application category".

---

There's another unrelated example I can think of on $\mathbb{N}$ where $x \circ y \stackrel{\small{df}}{=} x \times y$ and $x[y] \stackrel{\small{df}}{=} y^x $ . I think it also works with $+$ and $\times$ .

---

Another example of something satisfying this structure is the class of sets $U$ with $\bot$ and $\top$ . In this setting, $x \circ y \stackrel{\small{df}}{=} x \cup y \text{ or } x \lor y $ and $x[y] \stackrel{\small{df}}{=} y \in x$ . The truth values $\{ \top, \bot \}$ are not sets and are not elements of any set.

Anyway, what do you call this kind of thing?

---

✱ $\sqsubseteq$ is true if the elements are equal, or the left hand side is undefined. It is false if the elements are unequal or the right hand is defined while the left is undefined.

Answer 1

Ignoring partiality for the moment, I'd call this a semigroup acted on by its underlying set. Although I don't know if anyone else would ...

---

Recall that a semigroup is just a set equipped with an associative binary operation. If $G=(G,*)$ is a semigroup and $X$ is a set, an action of $G$ on $X$ is a map $\cdot:G\times X\rightarrow X$ such that $(g*h)\cdot x=g\cdot(h\cdot x)$ for all $g,h\in G$ and all $x\in X$.

That doesn't look like the equation you've written, though. What you have is rather $$(1)\quad\quad(g*h)\cdot x=(g\cdot x)*(h\cdot x).$$ This is basically what an action would be if it went $G\times X\rightarrow G$ instead of $G\times X\rightarrow X$: it satisfies the most natural "simplification" principle which makes sense for its new context. Inasmuch as we think of a map $A\times B\rightarrow A$ or $B\times A\rightarrow A$ as describing a way for elements of $B$ to alter elements of $A$, we should think of the situation above as a set acting on a semigroup.

• The "structure on the 'acted-on part'" is a crucial feature here. In particular, we can generalize the defining equation $(1)$ above from semigroups to magmas without introducing any weirdness. When we do that, a fundamental asymmetry emerges: one can argue that when $M$ is a magma and $X$ is a set a magma action of $M$ on $X$ should just be any map $M\times X\rightarrow X$, but not every map $M\times X\rightarrow M$ satisfies $(1)$.

---

Of course, there's one major question here:

Where did Condition $(1)$ above come from?

In some sense it's obvious: to reiterate what I said above, if we're looking at a semigroup $G$ and a set $X$ then $(1)$ seems the most obvious "simplifying equation" we might expect a map $G\times X\rightarrow G$ to have. However, this doesn't feel satisfying for more than a few minutes, and even then only if you don't look to closely.

Here's the best argument I can think of at the moment:

• As with actions in any context, we're looking for a collection of equations that will let us break down any complicated term involving $g_1,...,g_n\in G$ and $x_1,...,x_k\in X$ into a combination of "basic" terms of the form $g_i\cdot x_j$. (No "unnamed" elements of $G$ or $X$ should show up since neither $G$ nor $X$ have already-distinguished elements.)

• $G$ has only one operation, namely $*$, and $X$ has no operations at all. This means it's enough to understand how to simplify a term of the form $(g_1*g_2)\cdot x$. Since moreover $*$ is associative, our simplification rule will be determined entirely by choosing an expression of the form $$(g_{i_1}\cdot x)*(g_{i_2}\cdot x)*...*(g_{i_n}\cdot x)$$ where $i_1,i_2,...,i_n\in\{1,2\}$ (parentheses aren't needed since $*$ is associative).

• The "obvious" rule $(g_1*g_2)\cdot x=(g_1\cdot x)*(g_2\cdot x)$ then amounts to the decision to use each of the "basic terms" we're allowed exactly once, and to use them according to the "order" that their constituents appear in the starting expression. As far as the order-preserving aspect goes, there's no big deal here: if you wanted to work with $(g_1*g_2)\cdot x=(g_2\cdot x)*(g_1\cdot x)$ instead, just switch from $G$ to $G^{op}$. Finally, note that this is especially natural in case $*$ is commutative: in that case each option for $(g_1*g_2)\cdot x$ has the form $(g_1^a\cdot x)*(g_2^b\cdot x)$ for some $a,b\in\mathbb{N}$, and "clearly" $a=b=1$ is the most natural choice.

This has a little bit of logic to it, but is still pretty heuristic. Ultimately I don't have anything truly satisfying.

---

Now back to your specifics.

In your case the underlying set of $G$ is $X$ itself, but I don't know a snappy way to express that. The problem is that it really isn't a self-action in any good sense: the "acting part" lacks crucial data that the "acted-on part" has, namely the semigroup operation itself. So as mentioned above, the best description I can think of currently is $$\mbox{semigroup acted on by its underlying set.}$$

Rejecting the implicit totality assumption yields the perfectly cromulent "partial semigroup partially acted on by its underlying set."

On the note of partiality, a useful bit of notation is "$\simeq$," meaning "are each undefined or are each defined and equal - the LaTeX code is "\$\simeq\$."