抽象代数基础：半群、群

抽象代数，顾名思义，就是把具体的数字暂时放在一边，研究集合与运算本身有什么规律。

大一学离散数学时，大概已经跟这些概念打过照面了。抽象代数最有趣的地方在于：研究了一大堆运算，最后发现它们甚至不一定是在算数字（笑）。

话不多说，从最基础的结构开始。

1 定义

1.1 二元运算

设 $G$ 是一个非空集合。如果某种运算 $\cdot$ 可以接受 $G$ 中的两个元素，并且运算结果仍属于 $G$，即

$$ \cdot:G\times G\longrightarrow G, $$

我们便称它为 $G$ 上的一个二元运算。这里的 $\cdot$ 只是一个记号，不一定代表普通乘法。

例如，整数集合 $\mathbb Z$ 上的加法就是二元运算，因为两个整数相加还是整数；但自然数（取 $\{0,1,2,\ldots\}$）上的减法就不是，因为 $2-3=-1$ 不属于这个集合。

这种“运算完以后还在原集合里”的要求称为封闭性。

1.2 半群（Semigroup）

如果 $G$ 上的二元运算满足结合律：

$$ \forall a,b,c\in G,\qquad(a\cdot b)\cdot c=a\cdot(b\cdot c), $$

那么 $(G,\cdot)$ 就称为一个半群。

注意，结合律不等于交换律。前者允许我们随意改变括号的位置，后者才允许调换元素顺序。

例如，$(\mathbb Z,+)$ 是半群；非空字符串在拼接运算下也是半群，因为 (ab)c 和 a(bc) 拼出来的内容相同。但字符串拼接通常不满足交换律，ab 和 ba 显然不同。

1.3 幺半群（Monoid）

如果在半群中还存在一个元素 $e\in G$，使得

$$ \forall a\in G,\qquad e\cdot a=a\cdot e=a, $$

那么 $e$ 称为幺元（单位元），$(G,\cdot)$ 称为幺半群。

整数加法的幺元是 $0$，整数乘法的幺元是 $1$；字符串拼接的幺元则是空字符串 ""。

这里需要特别注意：幺元由运算决定，不是固定等于 $0$ 或 $1$。

1.4 群（Group）

如果一个幺半群中的每个元素 $a$ 都存在对应的元素 $a^{-1}\in G$，满足

$$ a\cdot a^{-1}=a^{-1}\cdot a=e, $$

那么 $(G,\cdot)$ 就称为一个群，$a^{-1}$ 称为 $a$ 的逆元。

于是我们得到了四个条件：

1. 封闭性：$a\cdot b\in G$；
2. 结合律：$(a\cdot b)\cdot c=a\cdot(b\cdot c)$；
3. 幺元存在：存在 $e$，使 $e\cdot a=a\cdot e=a$；
4. 逆元存在：每个 $a$ 都有 $a^{-1}$，使 $a\cdot a^{-1}=a^{-1}\cdot a=e$。

整理一下结构关系：

$$ \boxed{\text{半群}}\xrightarrow{\text{存在幺元}} \boxed{\text{幺半群}}\xrightarrow{\text{每个元素可逆}} \boxed{\text{群}} $$

例如，$(\mathbb Z,+)$ 是群，因为每个整数 $a$ 都有加法逆元 $-a$；但 $(\mathbb Z,\times)$ 不是群，因为整数 $2$ 在整数范围内没有乘法逆元。

若一个群还满足

$$ a\cdot b=b\cdot a, $$

则称为交换群（阿贝尔群，Abelian Group）。整数加法群就是最经典的例子。

2 群的基本性质

群的定义看起来只有几条，但其实能推导出不少结论。

2.1 幺元是唯一的

证明： 假设 $e_1,e_2$ 都是幺元。

因为 $e_1$ 是幺元，所以 $e_1\cdot e_2=e_2$；又因为 $e_2$ 是幺元，所以 $e_1\cdot e_2=e_1$。

于是

$$ e_1=e_1\cdot e_2=e_2. $$

所以幺元唯一。证毕。

这里甚至不需要用到结合律，也不需要讨论到底假设存在几个幺元。

2.2 结合律允许我们省略括号

对于任意有限个元素 $a_1,a_2,\ldots,a_n\in G$，只要不改变元素的顺序，整个运算结果就不会因为括号的放置方式不同而改变。

这是结合律反复应用的结果，严格证明可以对 $n$ 做数学归纳法。

因此，以后可以放心地把

$$ ((a\cdot b)\cdot c)\cdot d $$

简写成 $a\cdot b\cdot c\cdot d$。

但千万别偷偷变成 $b\cdot a\cdot c\cdot d$。一般群并不保证交换律！

2.3 逆元也是唯一的

证明： 假设 $b,c$ 都是 $a$ 的逆元，即

$$ a\cdot b=b\cdot a=e,\qquad a\cdot c=c\cdot a=e. $$

那么

$$ \begin{aligned} b&=b\cdot e\\ &=b\cdot(a\cdot c)\\ &=(b\cdot a)\cdot c\\ &=e\cdot c\\ &=c. \end{aligned} $$

所以逆元唯一。证毕。

顺带一提，幺元自己的逆元就是自己，且 $(a^{-1})^{-1}=a$。

2.4 消去律

在整数乘法中，不能直接从 $ab=ac$ 推出 $b=c$，因为 $a$ 可能为 $0$。

但群内的每一个元素都有逆元，于是可以这样做：

$$ \begin{aligned} a\cdot b&=a\cdot c\\ a^{-1}\cdot(a\cdot b)&=a^{-1}\cdot(a\cdot c)\\ (a^{-1}\cdot a)\cdot b&=(a^{-1}\cdot a)\cdot c\\ e\cdot b&=e\cdot c\\ b&=c. \end{aligned} $$

同理，$b\cdot a=c\cdot a$ 也能推出 $b=c$。这便是群的左消去律与右消去律。

2.5 乘积的逆元

一个很好用的公式：

$$ (a\cdot b)^{-1}=b^{-1}\cdot a^{-1}. $$

证明只需要验证右边与 $a\cdot b$ 相乘能得到幺元：

$$ \begin{aligned} (a\cdot b)\cdot(b^{-1}\cdot a^{-1}) &=a\cdot(b\cdot b^{-1})\cdot a^{-1}\\ &=a\cdot e\cdot a^{-1}=e. \end{aligned} $$

反方向相乘也同样得到 $e$，因此结论成立。

注意顺序反过来了！ 在不满足交换律的群中，不能随意写成 $a^{-1}\cdot b^{-1}$。

2.6 群中的方程一定有唯一解

例如

$$ a\cdot x=b, $$

在左边乘 $a^{-1}$，得到唯一的解

$$ x=a^{-1}\cdot b. $$

类似地，$x\cdot a=b$ 的唯一解为 $x=b\cdot a^{-1}$。

这也解释了为什么逆元这么重要：它让群中的运算在某种意义上能够被“撤销”。

3 从例子理解群

3.1 模 $n$ 加法群

定义

$$ \mathbb Z_n=\{0,1,\ldots,n-1\}, $$

运算为模 $n$ 加法。例如，在 $\mathbb Z_5$ 中：

$$ 3+4\equiv 2\pmod 5. $$

幺元是 $0$，元素 $3$ 的逆元为 $2$，因为 $3+2\equiv0\pmod5$。

每个元素都有加法逆元，因此 $(\mathbb Z_n,+)$ 是阿贝尔群。

3.2 置换群

考虑三个对象 $\{1,2,3\}$。将它们重新排列的所有双射构成一个集合 $S_3$，运算规定为函数复合。

两个置换复合还是置换，函数复合满足结合律，恒等置换是幺元，每个置换也都能反向还原，所以 $S_3$ 是一个群。

不过它通常不交换。比如先交换 $1,2$ 再交换 $2,3$，与反过来操作，结果并不一样。

这便说明了一个容易误解的地方：群不一定交换。

3.3 可逆矩阵群

所有 $n\times n$ 的实可逆矩阵，在矩阵乘法下构成 $GL_n(\mathbb R)$。

它的幺元是单位矩阵 $E$；每个矩阵 $A$ 都存在逆矩阵 $A^{-1}$。当 $n\ge2$ 时，矩阵乘法通常不交换，因此这也是非阿贝尔群。

到这里就可以发现：群不只是数字运算，也可以是置换、矩阵，甚至某种几何变换。

4 子群（Subgroup）

假设 $(G,\cdot)$ 是群，而 $H\subseteq G$。如果 $H$ 在同一个运算下也构成群，就称 $H$ 是 $G$ 的子群，记作

$$ H\le G. $$

例如，偶数集合 $2\mathbb Z$ 在加法下就是整数加法群 $(\mathbb Z,+)$ 的子群：两个偶数相加还是偶数，包含幺元 $0$，并且每个偶数的相反数还是偶数。

实际判断时，还有一个更省事的判定方法：

对于群 $G$ 的非空子集 $H$，若任意 $a,b\in H$ 都满足 $a\cdot b^{-1}\in H$，那么 $H$ 是 $G$ 的子群。

为什么？任选 $a\in H$，令 $b=a$ 就能得到 $e=a\cdot a^{-1}\in H$；接着利用 $e\cdot a^{-1}=a^{-1}$ 得出逆元属于 $H$；最后利用逆元和上述条件得出封闭性。结合律直接继承自 $G$。

5 循环群与元素的阶

5.1 循环群

对群中的某个元素 $a$，不断重复它的运算：

$$ \langle a\rangle=\{a^k\mid k\in\mathbb Z\}. $$

这里约定 $a^0=e$，负整数指数代表逆元的相应幂。$\langle a\rangle$ 称为由 $a$ 生成的循环子群。

如果 $G=\langle a\rangle$，那么 $G$ 本身就是循环群，$a$ 称为生成元。

对于加法群，我们通常把 $a^k$ 写成 $ka$。例如

$$ \mathbb Z=\langle1\rangle $$

表示整数加法群可以由 $1$ 不断相加及取逆得到。

在 $\mathbb Z_6$ 中，$1$ 能生成全部六个元素，而 $2$ 只能生成 $\{0,2,4\}$。

5.2 元素的阶

如果存在正整数 $k$ 使得 $a^k=e$，那么满足条件的最小正整数 $k$ 就称为 $a$ 的阶，记作 $\operatorname{ord}(a)$；如果不存在这样的 $k$，则称其阶为无穷。

在 $\mathbb Z_6$ 的加法运算下：

$$ 2+2+2\equiv0\pmod6, $$

因此 $\operatorname{ord}(2)=3$。注意，元素的阶不是元素的数值大小，而是它需要经过多少次重复运算才能回到幺元。

5.3 拉格朗日定理（Lagrange's Theorem）

对于有限群 $G$ 及其子群 $H$，有

$$ |H|\mid |G|. $$

换句话说：子群的阶一定整除原群的阶。

直观地理解，可以把 $G$ 分成若干个互不重叠的左陪集 $gH$。每个陪集与 $H$ 的元素个数相同，所以整个群的元素数量必然是 $|H|$ 的整数倍。

因为 $\langle a\rangle$ 本身就是子群，我们还得到

$$ \operatorname{ord}(a)\mid |G|, $$

以及

$$ a^{|G|}=e. $$

例如，一个只有 $7$ 个元素的群，非幺元的阶只能是 $7$（因为它的阶必须整除 $7$，且不可能是 $1$）。因此，每个非幺元都可以生成整个群。

这里也别反过来误用：一个整数整除 $|G|$，不代表一定存在那个阶的子群。

6 和计算机科学有什么关系？

看到这里可能会觉得，研究这些东西特喵的就是把加减乘除重新命名了一遍吧？但这些东西确实用得很多，尤其在IT。

6.1 模运算与密码学

若 $p$ 是素数，所有非零模 $p$ 剩余类

$$ \mathbb Z_p^{\times}=\{1,2,\ldots,p-1\} $$

在模 $p$ 乘法下构成一个群，阶为 $p-1$。

这里的条件是“模 $p$ 乘法”，而不是刚才的模 $n$ 加法。运算一换，群结构就变了。

由Lagrange定理可得，对于 $a\not\equiv0\pmod p$，

$$ a^{p-1}\equiv1\pmod p. $$

这就是费马小定理的一种群论解释。它与模逆元、快速幂以及不少密码学算法都有联系。

RSA 也利用模运算的结构。不过需要注意：当模数 $n$ 不是素数时，并非所有非零剩余类都有乘法逆元，只有与 $n$ 互素的剩余类才构成乘法群。

6.2 椭圆曲线密码学

椭圆曲线上的点，在适当定义的“点加法”下能够形成阿贝尔群。密码学中常见的标量乘法

$$ kP=\underbrace{P+P+\cdots+P}_{k\text{ 次}} $$

本质上就是在群中反复进行同一种运算。相关协议的安全性依赖于特定群中离散对数问题的计算困难性。

6.3 置换、对称性与程序

打乱数组顺序是置换；可逆的状态变换可以通过逆运算还原；对图形执行旋转、反射等对称变换，也经常出现群结构。

它们的对象与具体运算完全不同，却共享结合律、幺元与逆元这些性质。所以抽象代数研究的并不是数字，而是不同系统背后相同的结构。

7 总结

这一篇从半群出发，逐步添加条件，得到了幺半群和群：

群论最重要的不是背下这几个定义，而是学会识别：给定一个集合和一种运算，它们究竟构成什么结构？以及如果是群，又可以利用哪些性质简化问题？

至此，半群和群的基础内容就先告一段落。再往下可以研究群同态、正规子群、商群；如果给集合再加上一种运算，就会走向环与域。

不得不说，抽象代数确实很擅长一件事：看起来什么也没算，实际上是把所有能算的都算了...