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

149 Views Asked by At

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

There are 1 best solutions below

7
On BEST 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.