跳转至

结合性：半群

约 1049 个字 预计阅读时间 3 分钟

符号首先将自身呈现为对事物的谋杀。（Jacques Lacan）

在这一章最开头，我们已经提到，要使岩浆冷凝，需要受到约束的是二元运算。那么，怎么给出一个足够自然的约束呢？事实上，现在的二元运算太过自由以至于我们不能定义“乘方”1：

习题

举一个反例，使得 \((aa)a \not = a(aa)\)。

为了保证这玩意能够是良定的，我们有两种径路。一种是保证交换律，一种是保证结合律。在此，我们采纳后面这种，因为有线性代数基础的读者都知道，矩阵作为一个重要的数学对象，它是结合的而不是交换的。因此，半群应运而生：

定义

称 \((S, \cdot)\) 构成一个半群（semigroup），如果它满足以下性质：

\[ \forall a, b, c \in S, (ab)c = a(bc) \]

这个性质被称为结合律（law of associativity）。

这个东西有什么用呢？最显然的就是记号上的简化。我们可以记下乘方为 \(a^n, n \in \mathbb{Z}\) 了，毕竟顺序不再影响结果了。类似的，对于三个元素甚至多个元素的乘积，我们也可以直接将其记作 \(abc\) 而非某种带括号的形式了。当然，需要用数学归纳法证明一下，这个证明留作练习。

习题

证明，对于一个连续乘积 \(x_1x_2\cdots x_n\)，在中间任意插入匹配的括号，计算结果不变。2

这个结构看起来简单到了平凡的程度。正整数在通常的加法或者乘法下构成半群，当然，这些都很简单。接下来，我们来看一个不那么平凡的例子。

字符串半群

考虑一个字母表（alphabet）\(A\)，它不过是一些符号的集合。要用这个字母表构成单词，当然我们需要把里面的符号串联起来。如果二十六个英文字母作为字母表，我们的单词就可以是其中字母的随意组合：

\[ word, pen, cil, pencil, apple, applepencil \]

当然，语义无关紧要，所以任意的字母组合都是有效的。这个集合被我们记作 \(A^+\) 即字母表 \(A\) 上的字符串半群，它上面的运算就是字符串的衔接。字符串的长度则按照常识定义，记为 \(|w|\)。这种结构被称为 \(A\) 上的自由半群（free semigroups），我们将其形式化地定义如下：

定义

一个集合 \(A\) 上的自由半群是一个半群 \(A^+ = \{a_1a_2\cdots a_n: a_i \in A, n \geqslant 1\}\)。注意，这里的 \(a_i\) 是可以重复的。它上面的运算定义为：

\[ a_1a_2 \cdots a_r \cdot b_1b_2 \cdots b_m = a_1a_2 \cdots a_rb_1b_2 \cdots b_m \]

它也被称为由 \(A\) 生成（generated）的半群。特别的，单元素集 \(\{a\}\) 生成的半群称为循环半群（cyclic semigroup），记作 \(\langle a \rangle^+\)

很舒服的一个定义，不是吗？那么接下来的几个结果就交给读者证明了：

习题

证明 Levi 引理：字符串 \(u, v, x, y \in A^\ast\) 满足 \(uv=xy\)。

  1. 若 \(|u| = |x|\)，则 \(u=x\) 且 \(t=y\)。
  2. 若 \(|u| > |x|\)，则存在 \(t \in A^+\) 使得 \(u=xt\) 且 \(y=tv\)。
  3. 若 \(|u| < |x|\)，那么存在 \(t \in A^+\) 使得 \(x=ut\) 且 \(v=ty\)。

提示：第一条看上去很显然。那么怎么严格证明它呢？你可以尝试对字串的长度做归纳。

习题

证明 Lyndon-Schützenberger 第一定理：设 \(y \in A^+\)，\(x, z \in A^+\) 且 \(x, z\) 的长度均大于等于 \(2\)。则 \(xy=yz\) 当且仅当存在 \(u, v \in A^+\) 和正整数 \(e\) 使得 \(x=uv, z=vu, y=(uv)^eu=u(vu)^e\)

习题

证明 Lyndon-Schützenberger 第二定理：设 \(x, y \in A^+\)，则以下三个条件等价：

  1. \(xy=yx\)；
  2. 存在正整数 \(i, j\) 使得 \(x^i = y^j\)；
  3. 存在 \(z \in A^+\) 和正整数 \(k, l\) 使得 \(x=z^k, y=z^l\)。

习题

证明 Fine-Wilf 定理：设 \(a, b\) 为两个无限长字符串，周期3分别为 \(m, n \geqslant 1\)，如果两者在长度 \(m + n - \text{gcd}(m, n)\) 的前缀上相同，那么 \(a=b\)。

这些结果看起来当然不复杂，甚至有点小学奥数的味道。它们的证明基本上都是用归纳法和一些简单的组合学结果完成的。

同态与同构

按照代数学的惯例，定义完一个结构之后，我们要定义两个结构之间的关系。这种关系一般用一个映射来描述：

定义

设 \(S, R\) 为两个半群，则 \(\varphi: S \to R\) 被称为一个半群的同态（morphism4），如果它保持乘法，即：

\[ \varphi(ab) = \varphi(a)\varphi(b), \forall a, b \in S \]

如果 \(\varphi\) 是一个双射，则称其为一个同构（isomorphism）。

很容易看出，同构是一个等价关系，如果两个半群之间有一个同构，那么我们就称这两个半群同构（isomorphic），这不会引起什么误解。事实上，两个东西同构也就往往意味着它们具备完全相同的结构，这对于代数结构的分类而言是相当关键的。另外，同构还有一个等价的定义，就是存在逆映射 \(\psi: R \to S\) 使得 \(\varphi \circ \psi = \mathrm{Id}\) 和 \(\psi \circ \varphi = \mathrm{Id}\)5 成立，验证应当不难。

一个半群到自身的同态往往被称为自同态（automorphism），它到自身的同构也被称为自同构（isomorphism）。下面的练习给出了自同态的一个性质：

习题

证明半群 \(S\) 的所有自同态 \(\mathrm{Aut}(S)\) 在逐点乘法（pointwise multiplication）下构成一个半群。设 \(\varphi, \psi: S \to S\)，逐点乘法 \(\varphi \star \psi\) 被定义为：

\[ (\varphi \star \psi)(s) = \varphi(s)\psi(s), \forall s \in S \]

这类性质往往是相当关键的，因为自同态/自同构的性质往往代表了结构本身的性质。在后面的章节中，这会得到更加充分的表现。接下来，我们要说明一个比较复杂的性质，它被称为自由半群的泛性质（universial property），事实上，这个性质对于所有“自由”的构造都是有效的。

命题

设 \(A\) 是一个集合，\(A^+\) 是 \(A\) 上的自由半群。对于任意半群 \(S\) 和映射 \(\varphi: A \to S\)，都存在一个唯一的半群同态 \(\bar\varphi: A^+ \to S\) 使得对任意 \(a \in A\) 都有 \(\bar\varphi(a) = \varphi(a)\)。

这个性质可能是本节中读起来最别扭的一个性质，为了看清楚几个东西之间的关系，我们不妨画出交换图（commutative diagram）如下：

其中 \(i\) 是包含映射。这种图之所以被称为交换图，是因为它“条条大路通罗马”。从每一条路径走过去的结果是一样的，这就蕴含了上面所述的那个结论。类似的图将一次又一次出现在我们的讨论当中。

那么这个结论到底表达了什么？这样的唯一半群同态事实上界定了 \(A^+\) 的某种特性。也就是说，在所有从 \(A\) 出发能到达的半群 \(S\) 中，\(A^+\) 是最“充要”的那个。所谓“最充要”，是因为这样一个唯一的映射 \(\bar\varphi\) 如果是单射而非满射，那么意味着 \(S\) 中多了一些东西，它们在把 \(A\) 做成半群的时候不是必要的；而如果它是一个满射而非单射，那就意味着有一些 \(A\) 中元素的关系在 \(S\) 中被额外引入了（就是说，有某些东西映过去相等，这样的性质多出来了）。当然，这样的评述还是有些抽象的，在后面类似的讨论中，这样的含义会越来越清晰。在此，我们先给出对这个结果的证明6：

证明

我们这样来定义映射 \(\bar\varphi\)：

\[ \bar\varphi(a_1a_2\cdots a_n) = \varphi(a_1)\varphi(a_2) \cdots \varphi(a_n) \]

那么很显然这个映射满足条件。还需要证明的是唯一性，这由半群同态保乘法的性质可以轻易得出。

这一节的最后，我们来看一点不那么烧脑但是很重要的东西。我们很容易表明，半群同态在它的定义域上诱导了一个等价关系：

定义

一个半群同态 \(\varphi: S \to R\) 诱导了一个 \(S\) 上的等价关系 \(~_\varphi\)：

\[ x \sim_\varphi y \iff \varphi(x) = \varphi(y) \]

这个等价关系被称为核等价（kernel congruence7）。

一个半群上的等价关系 \(\sim\) 意味着：

\[ s \sim t \implies usv \sim utv, \forall s, t, u, v \in S \]

这种性质意味着它与半群上的乘法是相容的。

这样的等价关系同时又诱导了一个半群 \(S/\sim_\varphi\)，其中的元素是 \(S\) 在这个等价关系下的等价类，我们称这样将每个元素映射到其对应的等价类的映射 \(\pi: S \to S/\sim_\varphi\) 为商映射（quotient map）。下面这个命题被称为第一同构定理（first isomorphism theorem），它的表述与自由半群的泛性质表述类似，因此证明留给读者：

习题

证明：设 \(\varphi: S \to R\) 为一个半群同态，对应的商映射为 \(\pi: S \to S/\sim_\varphi\)。则存在一个唯一的半群同态 \(\tilde\varphi: S/\sim_\varphi \to R\) 使得 \(\varphi = \tilde\varphi \circ \pi\)。事实上，\(\tilde\varphi\) 是一个 \(S/\sim_\varphi \to \varphi(S)\) 的同构。其可以用交换图表示如下：

这个命题表达了什么？它说明，对于两个半群之间，如果有了一个同态，那么这个同态的像可以用它的“核”表出。类似的结果在群论中也有，而且相当重要。基于此，当有一个满的半群同态 \(S \to R\) 时，我们往往将 \(R\) 称为 \(S\) 的商（quotient）。下一个结果被称为第二同构定理，可以看成它的推广，同样留作练习：

习题

画出交换图并证明：对于两个从 \(S\) 出发的半群同态 \(\varphi_1, \varphi_2\)，如果 \(\sim_{\varphi_2}\) 比 \(\sim_{\varphi_1}\) 更加粗糙（即它对应的等价类会被后者“继续切割”），则存在一个唯一的满射 \(\pi: S/\sim_{\varphi_1} \to S/\sim_{\varphi_2}\) 使得 \(\pi_2 = \pi \circ \pi_1\)，其中 \(\pi_1\) 和 \(\pi_2\) 为对应的商同态。

基于这样的想法，我们称 \(\langle A | R \rangle\) 是一个半群 \(A^+/R\) 的展示（presentation），如果其中 \(R\) 是一个半群 \(A^+\) 上的等价关系，从这里可以一窥自由半群定义的商映射的协同作用。

子半群与理想

接下来我们要在原来的集合的子集中安插一些性质。子半群的定义是很自然的：

定义

给定半群 \(S\)，它的子半群（subsemigroup） \(R\) 是集合 \(S\) 的一个子集，而且在乘法运算下封闭，也就是说：

\[ \forall a, b \in R, ab \in R \]

一个非常简单的例子是，字符串半群 \(A^+\) 总有子半群 \(\langle a \rangle^+, a \in A\)。下面这个简单的命题留作习题：

习题

证明：设 \(\varphi: S \to R\) 是一个半群同态，\(S'\) 是 \(S\) 的一个子半群。则 \(\varphi(S')\) 也是 \(R\) 的一个子半群。若 \(R'\) 是 \(R\) 的一个子半群，则 \(\varphi^{-1}(R')\) 也是 \(S\) 的一个子半群8。

这个命题表明，半群同态能够保子半群。这种类似的对应关系对于研究一个子结构来说往往是相当好的，在后面探讨环论的时候这会变得尤其重要。下一个定义则是环论上对应定义的移植，事实上，半群理论比起环论来说事实上年轻得多。

定义

一个半群 \(S\) 上的右（左）理想（right/left ideal）指的是一个它的子集 \(R\)，满足 \(RS \subseteq R\)（\(SR\subseteq R\)）9。如果一个子集同时是左理想和右理想，那么我们称其为双边理想，简称理想。

当然，半群同态也是保理想的：

习题

证明：设 \(\varphi: S \to R\) 是一个半群同态，\(I\) 是 \(S\) 的一个理想。则 \(\varphi(I)\) 也是 \(R\) 的一个理想。若 \(J\) 是 \(R\) 的一个理想，则 \(\varphi^{-1}(J)\) 也是 \(S\) 的一个理想。

零元和单位元

这一部分关于单位元的工作相当乏味，事实上只是对上面所谓“可能不存在”的一个讨论，用以引出下一节所谓的幺半群（monoid）。零元的讨论与之相反，在环论中也是比较麻烦的点，我们在那里再去展开。这里仅仅将几个基本性质作为习题列出。

定义

称一个元素 \(e\) 为右（左）零元（right/left zero），如果 \(se = e, \forall s \in S\)（\(es = e, \forall s \in S\)）。如果一个元素基是左零元又是右零元，那么称之为零元。

习题

证明：一个半群至多有一个零元。

定义

称一个元素 \(e\) 为右（左）单位元（right/left unit），如果 \(se = s, \forall s \in S\)（\(es = s, \forall s \in S\)）。如果一个元素基是左单位元又是右单位元，那么称之为零元。

带单位元的半群称为幺半群（monoid）。

习题

证明：任一个半群都可以添加至多一个元素得到幺半群。

习题

证明：一个幺半群的幺元唯一。

习题

写出幺半群同态、同构、子幺半群、理想、自由幺半群（记作 \(A^\ast\)）的定义，并证明或证伪相关的结论。

有限半群上的幂等元

这一部分研究对应于有限群的研究，我们以习题的形式呈现整一个模块的重要结果，希望有兴趣的读者可以完成它：

定义

如果 \(x^2 = x\)，则称 \(x\) 是幂等（idempotent）的。

习题

本题中提到的半群 \(S\) 均为有限的半群。

  1. 证明：\(s, e, f \in S\)，其中 \(e, f\) 为幂等元。如果 \(s = esf\)，那么 \(es = s = sf\)
  2. 证明：对于任意有限的循环半群 \(\langle x \rangle^+\)，存在整数 \(i, p\) 使得 \(x^{i + p} = x^i\)
  3. 证明：对于任意 \(x \in S\) 都有正整数 \(k\) 使得 \(x^k\) 是幂等的。
  4. 证明：设 \(n = |S|\) 为 \(S\) 中的元素个数，对于任意 \(n\) 个元素构成的序列，都能找到一个长为 \(i\) 的前缀序列和一个幂等元 \(e\) 使得 \(s_1\cdots s_ie = s_1\cdots s_i\)。（提示：考虑抽屉原理）

下面这个命题的证明需要用到 Ramsay 定理，这是组合学中的一个结论，在此不做证明：

定理

令 \(r, k, m\) 为满足 \(k \geqslant r, m > 0\) 的整数，那么存在一个整数 \(N = R(r, k, m)\) 使得对于任意至少有 \(N\) 个元素的有限集合 \(E\)，对它的所有 \(r\) 元素子集进行 \(m\)-染色，\(E\) 中一定存在一个 \(k\) 元素子集，使得它的所有 \(r\) 元素子集都有相同的颜色。

习题

  1. 对于任意 \(k > 0\)，存在整数 \(N > 0\) 使得对于任意字母表 \(A\) 和任意半群同态 \(\varphi: A^+ \to S\)，任意 \(A^+\) 中长度大于等于 \(N\) 的单词，都有一个幂等元 \(e \in S\) 和一个对 \(w\) 的分解：
\[ w = xu_1\cdots u_ky, u_i \in A^+ \]

满足 \(\varphi(u_i) = e, |xu_1\cdots u_k| \leqslant N\)，其中 \(x, y \in A^\ast\)。

在目前的条件下，这是一个比较好的结果了。在下一节介绍 Green 关系之后，我们能够得到更多有意思的结果10。

  1. 习惯上，我们仍然将二元运算称为加法或者乘法，虽然读者需要时刻记住，它不一定是加法或者乘法。事实上，在本小节的例子中，它往往都表示衔接（concatnation）。 ↩

  2. 当然，当然我知道这很显然，但是结合律毕竟只定义了三个元素的结合。如果要将其推广到多个元素，那也是要费一点笔墨的。在这里读者不妨验证更强的结论，即插括号不影响运算的结果。基本思路是将带括号的连乘积进行分段，按照乘积的长度做数学归纳法。 ↩

  3. 若存在 \(a' \in A^+\) 使得 \(a'^\infty = a\)，则把 \(a'\) 的长度称为 \(a\) 的周期。 ↩

  4. 有的地方将其称为 homomorphism，而将 morphism 译作态射。本系列一般不区分这两者，因为在后面可以注意到，它们讲的往往是一个东西。 ↩

  5. 这里所谓的 \(\mathrm{Id}\) 可能会让人感觉有点晕，在每次看到恒同映射时，它是什么东西上的恒同映射往往都是要根据语境决定的。 ↩

  6. 参考了 Jean-Éric Pin Mathematical Foundations of Automata Theory 命题 5.28 的证明。这也是一种通行的证明“自由”的方法，在各种地方都能看到。在这一章的前几节的大部分结果都能在这本书中找到。 ↩

  7. 在 Pin 的书上他称之为 nuclear congruence。为了说明它和核（kernel）的关系，我们用了现在这个也不太常见的英文术语。 ↩

  8. 我们写逆映射的方式往往比较随意，事实上它指的就是对应的原像。单个元素的原像有的时候会被称为纤维（fiber），例如 Artin 的书就是这样。这个名词事实上有一些几何意义，在后面用到时还会再提及。 ↩

  9. 我们记 \(SR=\{sr: s \in S, r \in R\}\)。 ↩

  10. 这类结果主要的文章都来自于 I. Simon, 我们将介绍的结果可以参看 M. Kufleitner 的论文。 ↩

评论