# Subsets of a monoid closed under left-multiplication by elements of a submonoid

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$.

## 1 Answer

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.

• 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. – 6005 Dec 4 '14 at 0:17
• "[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$". – Shaun Dec 4 '14 at 8:22
• Ah, I see. Thanks, yeah. They definitely behave a lot like ideals, and not just for the ones restricted to $M$. – 6005 Dec 5 '14 at 5:40
• I'm going to talk to a semigroup theorist later today in fact. I'll mention this if we have time :) – Shaun Dec 5 '14 at 10:54
• Ah! Very helpful. Thanks a ton! I will wait for any other answers to come around, then accept this some time later. – 6005 Dec 6 '14 at 3:09