1 半群的基本定义
1.1 二元运算与集合结构
半群以一个集合 \(S\) 和一个二元运算 \(*:S\times S\to S\) 为起点。运算将任意两元素 \(a,b\in S\) 的“组合”得到新的元素 \(a*b\in S\)。在半群中，我们不预设特殊元素（如单位元），也不要求存在逆元，因此它比群的结构更“宽松”。
将半群看作“可组合的对象集合”，其中每次组合的结果仍落在同一集合里，是理解半群最直观的方式之一。例如，把字符串的拼接视作运算时，其结果仍是一条字符串；在自动机里把状态转移视作运算时，组合后的转移仍是同类对象。
1.2 结合律的要求
半群的关键性质是结合律：对任意 \(a,b,c\in S\)，应满足 \[ (a*b)*c=a*(b*c). \] 这条规则允许我们忽略括号，从而把长链式表达 \[ a_1*a_2*\cdots *a_n \] 视为不依赖具体括号排列的运算结果。结合律并不保证其他结构（例如存在单位元或可逆性），但它为统一地研究“重复组合”“分解与归约”提供了基本语法。
1.3 半群同态与保持运算
若 \((S,*)\) 与 \((T,\circ)\) 是半群，映射 \(\varphi:S\to T\) 称为半群同态，当且仅当对任意 \(a,b\in S\) 都有 \[ \varphi(a*b)=\varphi(a)\circ \varphi(b). \] 半群同态的意义在于：它把“组合规则”忠实地搬运到另一个半群里。因而同态既保持结构，又允许研究者把复杂半群映射到更易分析的对象上；在语言与自动机语境里，常见做法是把词或状态变换“投影”为更小的等价类。
1.4 子半群、商半群与直积
子半群：给定半群 \((S,*)\)，若 \(U\subseteq S\) 在运算下封闭且满足同样的结合律，则 \((U,*)\) 是半群。结合律自动继承于 \(S\)。子半群常对应“只用某些元素、仍能闭合组合”的情形。
商半群：通常由某种等价关系 \(\sim\) 产生。若 \(\sim\) 与运算相容（即 \(a\sim a'\) 且 \(b\sim b'\) 推出 \(a*b\sim a'*b'\)），则在等价类上定义运算，得到新的半群。商半群将结构通过“识别相同的行为”进行压缩。
直积：给定半群 \((S,*)\) 与 \((T,\circ)\)，在集合 \(S\times T\) 上定义 \[ (s_1,t_1)\star (s_2,t_2)=(s_1*s_2,\ t_1\circ t_2), \] 则 \((S\times T,\star)\) 仍是半群。直积体现了半群结构如何并行组合，也常用于构造具有指定性质的例子。
2 常见特例与相关结构
2.1 幺半群：带单位元的半群
如果在半群 \((S,*)\) 中存在元素 \(e\in S\) 使得对任意 \(a\in S\)，都有 \[ e*a=a,\quad a*e=a, \] 则称其为幺半群。单位元将“空操作”纳入结构，使得表达式能在更自然的形式下书写。在许多计算模型与语言理论里，幺半群与“空词”对应关系非常常见。
2.2 群：半群加逆元的加强
若半群进一步满足：对每个元素 \(a\in S\)，存在 \(a^{-1}\in S\) 以及单位元 \(e\)，使得 \[ a*a^{-1}=e,\quad a^{-1}*a=e, \] 则得到群。群可视为“最强”的代数形式之一，它比半群多了对可逆性与单位元的要求。半群与群的对比常用于理解哪些性质依赖于可逆性，哪些仅依赖结合律。
2.3 交换半群与非交换半群
若对任意 \(a,b\in S\) 都有 \(a*b=b*a\)，则称为交换半群。交换性使得许多推理可简化，但半群理论同样关注一般情形，即非交换半群。在非交换中，“组合顺序”会影响结果，因此结构通常更丰富，也更能刻画序列化过程的差异。
2.4 自同态半群与变换半群
给定半群 \(S\)，所有从 \(S\) 到自身的半群同态构成集合 \(\operatorname{End}(S)\)。以复合作为运算，\(\operatorname{End}(S)\) 是半群（一般不要求存在单位同态或逆元）。这类结构常用于研究半群的内部对称性与“可自我变形的方式”。
在自动机语境中，还常见“变换半群”：把状态集合上的函数视为元素，把函数复合当作运算，得到半群。它天然连接到“串如何驱动状态改变”的观点。
3 结构性质与分类线索
3.1 幂与指数：元素的重复运算
对半群中的元素 \(a\)，可定义幂： \[ a^1=a,\quad a^{n+1}=a^n*a. \] 结合律使得幂的定义一致，不依赖括号。通过考察 \(a,a^2,a^3,\dots\) 的行为，可以研究元素是否会“进入循环”“趋向稳定”。在很多分类问题中，幂的增长与重复出现是抓手。
3.2 幂等元素与幂等半群
若某元素 \(a\in S\) 满足 \[ a^2=a, \] 则称为幂等元素。若半群中每个元素都幂等，则该半群称为幂等半群。幂等性意味着元素“组合自身不会改变结果”，因此结构常呈现强烈的吸收与稳定特征。
3.3 可逆元（在半群语境下的讨论）
半群中谈“可逆性”需要谨慎：因为未必有单位元。常见做法是讨论在某种幺化环境中是否存在逆或局部可逆。一般而言，如果半群含有单位元，则元素 \(a\) 可逆当且仅当存在 \(a^{-1}\) 使得 \(a*a^{-1}=e=a^{-1}*a\)。在缺少单位元时，“逆”的意义可能只在理想、幺元补全或特定子结构中成立，因此通常用更结构化的方式定义相关概念。
3.4 生成元与生成子半群
给定半群 \(S\) 与一组元素 \(X\subseteq S\)，可以考虑由 \(X\) 通过有限次运算构成的所有元素。最小包含 \(X\) 且在运算下封闭的子半群称为由 \(X\) 生成的子半群，记作 \(\langle X\rangle\)。在计算与表示理论里，生成集合刻画了“用少量基本操作能否产生整个结构”。
4 Green 关系与理想理论（半群的“路标”）
4.1 \(\mathcal{L}\)、\(\mathcal{R}\)、\(\mathcal{H}\) 关系
Green 关系用于在半群内按“可由左乘或右乘得到”来分层。直观上，\(\mathcal{L}\) 关系对应“生成相同的左理想”，\(\mathcal{R}\) 对应“生成相同的右理想”，\(\mathcal{H}\) 则取两者的交。它们把半群分解为更有组织性的块，从而把复杂的运算结构转化为关于理想与可达性的结构问题。
4.2 \(\mathcal{D}\)、\(\mathcal{J}\) 关系
在 Green 理论中，\(\mathcal{D}\) 与 \(\mathcal{J}\) 提供了更粗的划分。常见理解是：\(\mathcal{J}\) 主要由双侧理想控制，而 \(\mathcal{D}\) 可被视为与左右结构相关联的方式。它们在理想分解、有限半群分类等问题上尤为重要，因为粗粒度的等价划分往往更稳定、更可计算。
4.3 理想、双侧理想与商结构
理想在半群中起到“结构骨架”的作用。一般地，左理想、右理想、双侧理想分别对应在左乘、右乘、双侧乘之后仍保持在集合内。由理想可构造商结构：当一个等价关系由理想诱导时，商半群会把被“压缩”的部分视为同类。借助这些构造，可以更清楚地理解半群如何由更简单的部分拼接而成。
4.4 分解与等价分类的直观图景
把 Green 关系看作“在半群里标出相同行为路径的节点”，则可得到一个直观图景：半群可以被分解为若干互不混杂但彼此通过乘法影响的区域。等价分类越细，信息越多；越粗，结构越易把握。Green 理论的价值就在于提供一套可系统比较与组织这些区域的方法。
5 表示方式与表示定理
5.1 乘法表、Cayley 表与具体构造
半群是“有运算的集合”。当半群有限时，最直接的表示方式是给出其乘法表（或 Cayley 表）：对每对元素 \(a,b\) 标注结果 \(a*b\)。这种表示适合计算验证，但对于大规模结构通常不够直观。
另一类具体构造是把抽象元素映射为某类可操作对象，例如函数、关系或变换。这样，半群运算就变成对象上的组合，从而把抽象问题转化为可执行的算法步骤。
5.2 由表示刻画半群：变换表示
变换表示把半群嵌入到变换半群中：选取集合 \(X\)，让每个 \(s\in S\) 对 \(X\) 施加一个函数（或部分变换），并要求该映射保持运算结构。通过这种方式，半群的抽象结合律体现为函数复合的结合性。
变换表示的好处是：它把“抽象乘法”变为“具体作用”。在自动机与语言理论中，这往往对应“读入字符后状态如何变化”的机制。
5.3 由生成与关系给出：呈现（presentation）
呈现（presentation）强调“用生成元与关系描述半群”。形式上，给定生成集合 \(X\) 及一组等式（或等价约束）作为关系，通过在自由半群上施加这些关系得到目标半群。呈现使得半群的定义更接近“规范书”：先说明基本操作来源，再说明哪些操作序列应当被视为等价。
这类描述在理论研究和计算中都重要，因为同一个半群可用不同的生成—关系系统给出，从而影响可计算性与推理便利性。
5.4 计算与化简：从关系到算法
当半群以呈现方式给出时，可以尝试把元素表示为生成元的串（词），再通过关系进行化简与判等。化简的目标通常是构造某种规范形式，使得判等问题转化为字符串比较或可执行的归约步骤。
实际实现往往依赖对关系系统的组织方式，例如采用重写规则、确定归约策略或引入能够保证终止与一致性的工具。尽管细节属于更深入的计算理论范畴，但总体思路是：从“关系”出发，导出可计算的“化简”流程。
6 重要的构造与例子（入门口袋指南）
6.1 自由半群与自由结构的直观
自由半群可理解为：给定一组生成符号，所有有限长度的符号串构成集合，运算为串的连接。自由性体现为：对任意满足结合律的解释，任意对生成符号的赋值都能唯一延拓为半群同态。它提供了一个“最不加约束”的基准模型。
自由半群在呈现理论里尤为常用，因为许多半群都可视为自由半群再加上一组等式关系后的商。
6.2 零半群、左零/右零半群
零半群指满足对任意 \(a,b\in S\)，都有 \[ a*b=z \] 其中 \(z\) 为某个固定元素（因此所有乘积都坍缩到同一结果）。更一般地，还可定义：
- 左零半群：\(a*b=a\)，即左边元素决定结果；
- 右零半群：\(a*b=b\)，即右边元素决定结果。
这些极端例子帮助快速理解“运算如何主导结构”，也能作为检验定理与定义边界的参照。
6.3 零元半群与吸收元现象
若存在元素 \(0\in S\) 使得对任意 \(a\in S\)，都有 \[ 0*a=0,\quad a*0=0, \] 则称 \(0\) 为吸收元或“零元”对应的结构特征。该性质意味着只要序列里出现该元素，后续组合都将坍缩到同一个结果。与零半群相比，吸收元更强调“特殊元素的吸收作用”，可用于构造带有“失败态”“终止态”味道的模型。
6.4 以幂等性为核心的例子
把每个元素视作某种“状态筛选器”，幂等性 \(a^2=a\) 表示重复施加同一个筛选器不会再改变效果。由此得到的幂等半群常出现在把过程压缩成规则的情境中：一旦某条规则已被应用，其再次应用不会产生新变化。这样的直观解释有助于把抽象性质与具体模型联系起来。
7 半群与其他数学领域的联系
7.1 半群与自动机/正规语言
正规语言理论中，字串的拼接与状态变换天然形成半群结构。一个自动机可以把读入不同字串看作对状态集合的复合变换：不同字串对应不同“变换效果”。在这种对应下，语言的接受行为由这些变换决定，而半群理论则提供分析这些变换的代数工具。
因此，“半群—自动机—正规语言”之间常以代数刻画与结构分解为桥梁：把语言性质转译为半群性质，再通过半群的分类与理想结构来推回语言结论。
7.2 半群与形式幂级数（概念性联系）
形式幂级数可以在非交换或更一般的代数背景下讨论，其中“系数对应组合方式”。半群元素的重复运算与幂的展开常能在形式幂级数的操作中出现，例如把串视作幂级数中的项，通过运算规则体现“组合等价”。这是一种概念上的同构联系：半群的组合逻辑可以嵌入到形式代数的展开与变换框架里。
7.3 与范畴论：半群作为幺范畴的离散实例
范畴论研究对象与态的组合结构。若把半群视作只有一个对象的幺范畴：半群元素对应从该对象到自身的态，运算对应态的复合，则结合律与复合的结合性一致。因而半群可以被看作“范畴论里最简单的离散复合结构”之一，这种视角帮助理解同态如何自然对应为函子。
7.4 与组合结构：串联、变换与路径
更广义地，半群强调的是“可组合但不必可逆”的过程结构。许多组合对象（如串的连接、路径的拼接、变换的复合）都符合结合律与封闭性，从而能归入半群框架。把不同领域的“组合规则”统一到同一个抽象语言里，是半群作为基础工具的核心价值。
8 应用视角与计算问题
8.1 词的求值与规范化
在以词（由生成元构成的串）作为半群元素表示时，计算任务往往是“求值”：把一个串在半群中归约为单个元素。这一步依赖于半群的具体表示方式（如乘法表或变换表示）。为便于反复比较，通常还希望找到某种规范形式，让同一个半群元素对应的词能被归约到同一表示。
规范化常与重写系统、化简规则相关：通过反复替换把任意词转化为“标准写法”。
8.2 等价与同态判定的常见问题类型
同态判定通常问：给定两个半群及候选映射，是否对所有元素对都满足运算保持条件。对于有限半群，这通常可通过穷举检验或基于生成元的缩减来完成。
等价判定可能指由同一等价关系诱导的判等（例如商半群中的等价类识别），也可能指两个表示（如两组生成—关系）是否生成同一个结构。此类问题在形式化系统与算法分析中常见，是半群理论进入计算领域的入口。
8.3 研究对象的规模化：有限半群
有限半群是理论与计算的交汇点。由于元素数量有限，可以采用表格、图结构或状态遍历来实现运算。有限性也便于研究结构分解：理想链、Green 分层、生成元大小等指标都更可操作。
同时，有限半群也常被用作近似或测试对象：先在可计算范围内验证性质，再尝试外推到一般情形。
8.4 从性质到算法：可计算性线索
许多半群问题都可归结为某种可计算任务：元素判等、可达性、最小表示、等价类划分等。可计算性的关键线索通常来自结构性质是否提供“减少搜索”的机制，例如：
- 幂等性是否导致状态稳定，减少迭代长度；
- 理想与分解是否把问题拆成更小子问题；
- 变换表示是否将运算转化为函数复合从而利于模拟。
因此，结构理论与算法设计之间经常是互相促进的：理论告诉你该如何缩减，算法再反过来帮助理解理论边界。
9 常用术语与符号约定（新手友好）
9.1 乘法记号与运算省略
半群运算常用乘号或星号表示。若上下文明确，也可省略运算符，直接写成 \(ab\) 表示 \(a*b\)。结合律保证了在乘积表达中不必纠结括号位置，但前提仍是半群运算始终满足结合律。
9.2 元素、子集、理想与等价关系的标记
通常约定：
- 元素用 \(a,b,c,s,t\) 等表示；
- 子集用 \(U,V,X\) 等；
- 理想用 \(\text{LeftIdeal}\)、\(\text{RightIdeal}\) 等概念性符号或直接用“左理想/右理想/双侧理想”表述；
- 等价关系用 \(\sim\) 或类似符号表示，商结构依赖其与运算的相容性。
清晰的记号有助于在推理中避免把“元素级别”与“类级别”混用。
9.3 常见性质的命名规则
常见性质以“是否对所有元素成立”“是否对某个元素成立”为线索来命名。例如：
- 幂等：对某元素或对所有元素是否满足 \(x^2=x\)；
- 交换：运算是否满足 \(ab=ba\)；
- 单位元相关性质：是否存在 \(e\) 使 \(ea=a=ae\)。
这种命名方式通常直观且与定义对齐，便于快速定位一个概念在结构中的地位。
9.4 典型例句与“别忘结合律”的提醒
常见表述包括：
- “在半群中我们可以忽略乘积的括号，因为结合律成立。”
- “若某映射满足 \(\varphi(ab)=\varphi(a)\circ\varphi(b)\)，则它是半群同态。”
- “若存在吸收元 \(0\)，则一旦出现它，后续组合结果保持不变。”
对于新手，最大的提醒就是结合律：它是半群最核心的语法规则。只要结合律不满足，很多“括号可省略”“重复组合定义良好”的结论就无法使用。