Let $M, T$ be monoids (or, semigroups) with $M \subset T$. Then we can consider subsets $S$ of $T$ that are closed under left-multiplication by something in $M$, i.e. $$ a \in S, m \in M \implies ma \in S \tag{$*$} $$ Have these subsets been studied? What can we say about the structure of them? References would be appreciated.

Motivation: this setup seems to be a natural abstraction for the idea of complexity classes. As a simple example, let $M$ be the set of Turing-computable functions $\mathbb{N} \to \mathbb{N}$, and let $T$ be the set of all functions $\mathbb{N} \to \mathbb{N}$, with multiplication given by $fg := g \circ f$. Let $L_1, L_2$ be languages in $T$, by which I mean functions $\mathbb{N} \to \{0,1\}$. Then a mapping reduction from $L_1$ to $L_2$ is simply a function $f$ such that $fL_2 = L_1$. The set of Turing-recognizable (recursively enumerable) languages naturally satisfies $(*)$, as does the set of co-Turing-recognizable languages.

Similarly, if $T$ is before and $M$ is the set of polynomial time computable functions, then a complexity class could be defined as a set of languages satisfying $(*)$. In particular, standard examples like NP, coNP, NP$\cap$coNP, ExpTime, and PSpace are just examples of subsets of $T$ satisfying $(*)$, and we might naturally be interested in considering all such subsets, or at least in considering the structure of such subsets.

Other concepts can be formalized nicely. For example, a language $l$ is NP-complete if and only if NP is "generated" by $l$, i.e. $\text{NP} = \text{P}l$.


Why not simply call them left-$M$-invariant subsets of $T$? Such terminology fits similar things throughout algebra.

By definition $\color{red}{\text{some}}\,$ are just (either the empty set or the) left ideals of $M$ anyway since $M\subset T$. Quoting Howie's "Fundamentals of Semigroup Theory" (with different notation):

Definition: A non-empty subset $S$ of a semigroup $M$ is called a left ideal if $MS\subseteq S$.

But the condition $$(\forall a\in S\,\forall m\in M)\quad ma\in S$$ is equivalent to $MS\subseteq S$. We can thus say a lot about the structure of $\color{red}{\text{these}}$ "left-$M$-invariant subsets".

They're semigroup actions of $M$ on $T$ (or "$M$-sets in $T$", etc.). They're not all such actions but that's what your sets are. See the Actions section of Chapter 1 in Cain's "Nine Chapters on the Semigroup Art", particularly Example 1.32(b).

To highlight an important bit:

There is a [ . . . ] notion of a left semigroup action of $M$ on $S$ [$\subseteq T$], which is an operation $\cdot:M\times S\to S$ satisfying $$m\cdot(n\cdot s)=(mn)\cdot s.$$

We're in some semigroup $T$ though so left-multiplication fits the bill.

(Left) semigroup actions have been studied extensively.

  • $\begingroup$ Well, the thing is they are more like modules over a ring than the special case of ideals over a ring. The set $S$ is not a subset of $M$, but rather a subset of $T$. So it is closed under multiplication by things in $M$, but it is a bigger set. $\endgroup$ – 6005 Dec 4 '14 at 0:17
  • $\begingroup$ "[I]t is closed under multiplication by things in M, but it is a bigger set." I tried to acknowledge that. I'm sorry if it's not clear. The subsets of $T$ (under your conditions) that happen to be subsets of $M$ are semigroup-theoretic left ideals of M. The rest are invariant under left-multiplication by $M$, so are "left-$M$-invariant subsets of $T$". $\endgroup$ – Shaun Dec 4 '14 at 8:22
  • $\begingroup$ Ah, I see. Thanks, yeah. They definitely behave a lot like ideals, and not just for the ones restricted to $M$. $\endgroup$ – 6005 Dec 5 '14 at 5:40
  • $\begingroup$ I'm going to talk to a semigroup theorist later today in fact. I'll mention this if we have time :) $\endgroup$ – Shaun Dec 5 '14 at 10:54
  • 2
    $\begingroup$ Ah! Very helpful. Thanks a ton! I will wait for any other answers to come around, then accept this some time later. $\endgroup$ – 6005 Dec 6 '14 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.