幺半群作用

形式陈述 ​

设 $(M,\ast ,e)$ 是幺半群公理库幺半群Monoid具有双侧单位元的半群。，$X$ 是集合。$M$ 在 $X$ 上的左作用是函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

$$\alpha :M\times X\to X,(m,x)⟼m\cdot x,$$

满足

$$e\cdot x=x,(m_1\ast m_2)\cdot x=m_1\cdot (m_2\cdot x).$$

等价地，作用是幺半群同态

$$M⟶\mathrm{End}(X),$$

其中 $\mathrm{End}(X)$ 是 $X$ 上所有自映射在复合下形成的幺半群。右作用采用 $x\cdot (m_1\ast m_2)=(x\cdot m_1)\cdot m_2$；左右约定会改变复合书写顺序，必须固定。

直觉 ​

幺半群作用把抽象操作解释为对象上的状态变换。单位元什么也不做，幺半群乘法对应连续执行操作。操作可以覆盖、丢失信息或不可撤销，因此一般只得到自映射，不要求双射。

群作用公理库群作用Group action群元素以保持单位元与乘法的方式作用于集合。是可逆特例：群元素的逆元保证每个作用映射都是双射。幺半群作用则更适合字符串追加、状态更新、区间标签和自动机转换。

例子与边界 ​

字符串幺半群 $({\mathrm{\Sigma }}^{\ast },\cdot ,\epsilon )$ 可通过前缀拼接作用于字符串集合：$u\cdot x=ux$。自然数加法幺半群可通过函数迭代作用于集合：

$$n\cdot x=f^n(x).$$

函数自映射幺半群 $\mathrm{End}(X)$ 对 $X$ 的求值作用是最通用例子。

区间加标签形成加法幺半群，并作用于带长度的区间摘要 $(s,\ell )$：

$$v\cdot (s,\ell )=(s+v\ell ,\ell ).$$

区间赋值也能形成带“无操作”单位元的标签幺半群，但复合通常不交换：后来的赋值覆盖早先赋值。若把标签合成顺序写反，单个更新测试可能通过，混合更新会出错。

推论与应用 ​

懒惰传播公理库懒惰传播Lazy propagation把作用于整个节点区间的可组合更新暂存为标记，仅在必要时下传。可把待处理标签组织成幺半群作用。若节点摘要还能按 $\oplus$ 合并，则通常还需验证同一标签对合并兼容：

$$m\cdot (x\oplus y)=(m\cdot x)\oplus (m\cdot y),$$

或在摘要中显式携带长度等使该式成立的元数据。只有“标签可复合”不够；还必须能从节点局部摘要计算整段更新后的值。

自动机的输入字通过转换幺半群作用于状态集；动力系统把时间幺半群作用于状态空间。加入拓扑、可测或线性结构后，还会要求每个作用映射保持相应结构，这些是附加条件，不属于集合层定义。

参考资料

• John M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, 1995, Chapters 1 and 5.
• Mark V. Lawson, Finite Automata, Chapman & Hall/CRC, 2004, chapters on transformation monoids.
• Benjamin Steinberg, Representation Theory of Finite Monoids, Springer, 2016, introductory chapters.