一、二元运算
1.1 定义
代数结构的基本组成：一个集合 + 若干个二元运算。
定义：设 $S$ 是一个非空集合。一个从 $S \times S$ 到 $S$ 的映射
\[*: S \times S \to S\]称为 $S$ 上的一个二元运算。
“二元”是因为定义域是 $S \times S$（有序对，涉及两个元素）。类似地，可定义三元运算（$S \times S \times S \to S$）或 $n$ 元运算，但本课程只考虑二元运算。
多元函数（如 $f: \mathbb{R}^n \to \mathbb{R}$）其实就是某种意义上的多元运算。
1.2 记号
形式化的写法是 $*(a, b)$，但在代数中通常采用更方便的中缀记号：
\[a * b\]例如加法写 $x + y$ 而不是 $+(x, y)$。如果运算明确，甚至可以省略符号，直接写 $ab$（如数的乘法、矩阵乘法）。
如果用函数记号，多个元素运算时会变得非常复杂：
\[+(+(x, y), z) \quad \text{vs.} \quad x + y + z\]1.3 封闭性
二元运算最基本的要求是封闭性：
\[\forall a, b \in S: \quad a * b \in S\]即集合中两个元素运算后的结果仍在集合中。
等价说法：$*$ 是 $S$ 上的二元运算，只要对 $S$ 中任意两个元素有定义，且运算结果仍在 $S$ 中。
二、半群
2.1 结合律
二元运算可以有各种性质，其中最基本、最重要的是结合律。
定义：设 $*$ 是 $S$ 上的二元运算。若对任意 $a, b, c \in S$，
\[(a * b) * c = a * (b * c)\]则称 $*$ 在 $S$ 上满足结合律。
2.2 半群的定义
定义：若非空集合 $S$ 配上二元运算 $*$ 满足结合律，则称 $(S, *)$ 为一个半群。
代数结构一般写成 $(S, *)$ 的形式——集合和运算都要给定。
2.3 半群的例子
数的运算
- $(\mathbb{Z}, +)$：整数关于加法构成半群
- $(\mathbb{Z}, \times)$：整数关于乘法构成半群
- $(\mathbb{Q}, +)$, $(\mathbb{R}, +)$, $(\mathbb{C}, +)$：有理数/实数/复数关于加法构成半群
- $(\mathbb{Q}, \times)$, $(\mathbb{R}, \times)$, $(\mathbb{C}, \times)$：关于乘法也构成半群
从群的角度看，$(\mathbb{Z}, +)$ 比 $(\mathbb{Z}, \times)$ 性质更好（每个整数都有加法逆元即相反数，但不是每个整数都有乘法逆元——$\frac{1}{2}$ 不是整数）。
矩阵的运算
$M_n(\mathbb{R})$ 表示所有 $n$ 阶实方阵的集合。$(M_n(\mathbb{R}), \times)$ 在矩阵乘法下构成半群。
回忆矩阵乘法的定义：若 $A, B \in M_n(\mathbb{R})$，则
\[(AB)_{ij} = \sum_{k=1}^{n} A_{ik} B_{kj}\]即 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列做内积。矩阵乘法的结合律证明并不平凡（涉及求和号的交换），但确实成立。
集合的运算
设 $Y$ 是一个非空集合，$\mathcal{P}(Y)$ 为 $Y$ 的全体子集（幂集）。
- $(\mathcal{P}(Y), \cup)$：关于并运算构成半群（并运算有结合律，且可推广到任意多个集合的并）
- $(\mathcal{P}(Y), \cap)$：关于交运算构成半群（交运算有结合律）
- $(\mathcal{P}(Y), \triangle)$：关于对称差运算构成半群
对称差的定义：
\[A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\]即属于 $A$ 或 $B$，但不同时属于两者的元素。图示上就是两个圈去掉中间交叉部分。
三个集合的对称差可以写成四部分的不交并：
\[A \triangle B \triangle C = (A \setminus (B \cup C)) \cup (B \setminus (A \cup C)) \cup (C \setminus (A \cup B)) \cup (A \cap B \cap C)\]即：只属于一个集合的元素，加上同时属于三个集合的元素。由这个对称的表达式可以立即看出结合律成立（括号打在哪里都得到同样的形式）。
对称差的两个重要性质：
- $A \triangle \varnothing = A$（空集是幺元）
- $A \triangle A = \varnothing$（每个元素是自己的逆元）
字符串拼接
设 $\Sigma$ 是一个有限字母表（如 $\Sigma = {0, 1}$），$\Sigma^*$ 为 $\Sigma$ 上全体字符串（包括空字符串 $\varepsilon$）的集合。
字符串可以是任意长度的。长为 $n$ 的字符串 $a_1 a_2 \cdots a_n$，其中 $n = 0$ 时为空字符串 $\varepsilon$。
拼接运算：长为 $n$ 的字符串与长为 $m$ 的字符串拼接，得到长为 $n + m$ 的字符串。
\[(\Sigma^*, \cdot)\]构成半群。结合律显然成立（拼接只是按顺序排列，不改变任何内容）。空字符串 $\varepsilon$ 是幺元：$\varepsilon \cdot s = s \cdot \varepsilon = s$。
这个例子在计算机科学中非常重要，因为计算机处理的基本对象就是 ${0, 1}$ 上的字符串（二进制表示）。
关系与映射的复合
设 $Y$ 是非空集合。
- $Y$ 上全体二元关系在关系复合下构成半群（关系复合有结合律）
- $M(Y) = {f: Y \to Y}$（$Y$ 到 $Y$ 的全体映射）在映射复合下构成半群
$M(Y)$ 的重要性：任何半群都可以看成某个 $M(Y)$ 的子结构（后面会严格证明）。
不满足结合律的例子：向量叉积
$\mathbb{R}^3$ 上的叉积（向量积）$\times$ 是一个二元运算，但不满足结合律。
叉积的定义：
\[\mathbf{a} \times \mathbf{b} = \begin{vmatrix} \mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \end{vmatrix}\]结果是与 $\mathbf{a}$ 和 $\mathbf{b}$ 都垂直的向量。
因为不满足结合律，$\mathbf{a} \times \mathbf{b} \times \mathbf{c}$ 这种写法没有意义——必须明确指定括号的位置。
虽然叉积没有结合律，但它有其他重要的运算律，例如 Jacobi 恒等式：
\[\mathbf{a} \times (\mathbf{b} \times \mathbf{c}) + \mathbf{b} \times (\mathbf{c} \times \mathbf{a}) + \mathbf{c} \times (\mathbf{a} \times \mathbf{b}) = \mathbf{0}\]三、结合律的推广：任意打括号
3.1 连乘的递归定义
设 $(S, *)$ 是半群，$a_0, a_1, \ldots, a_n \in S$。定义连乘（递归定义）：
\[\prod_{i=k}^{k} a_i := a_k\] \[\prod_{i=k}^{m+1} a_i := \left(\prod_{i=k}^{m} a_i\right) * a_{m+1}\]即从左到右逐步运算，每次多加一个元素并打一层括号。
3.2 广义结合律
命题：设 $(S, *)$ 是半群，$a_0, a_1, \ldots, a_n \in S$。则对任意 $0 \le k \le n-1$，
\[\prod_{i=0}^{n} a_i = \left(\prod_{i=0}^{k} a_i\right) * \left(\prod_{i=k+1}^{n} a_i\right)\]含义：可以在任意位置”切断”，分别计算前后两部分再合并，结果不变。这就是”任意打括号”的严格表述——只要运算满足结合律，括号怎么打都不影响结果，因此可以放心地省略括号。
证明思路：固定 $n$，对 $k$ 从 $n-1$ 到 $0$ 进行（反向）归纳。
- 基础：$k = n-1$ 时，右边即递归定义本身，显然成立。
- 归纳步：假设对 $k$ 成立，证明对 $k-1$ 也成立。利用结合律和归纳假设（后半部分的项数严格小于 $n+1$，可用归纳假设）即可完成。
建议用 $n = 4$ 的具体例子体会这个归纳过程。
四、幺元（单位元）
4.1 定义
设 $(S, *)$ 是一个代数结构。
- 若 $\exists x_0 \in S,\ \forall a \in S:\ x_0 * a = a$，则称 $x_0$ 为左幺元
- 若 $\exists x_0 \in S,\ \forall a \in S:\ a * x_0 = a$，则称 $x_0$ 为右幺元
- 若 $x_0$ 既是左幺元又是右幺元，即 $\forall a \in S:\ x_0 * a = a * x_0 = a$，则称 $x_0$ 为幺元（单位元、恒等元）
常用记号：$e$ 或 $1$（类比乘法中 $1$ 的作用）。
4.2 各例子中的幺元
| 半群 | 幺元 |
|---|---|
| $(\mathbb{Z}, +)$ | $0$（加法幺元） |
| $(\mathbb{Z}, \times)$ | $1$（乘法幺元） |
| $(M_n(\mathbb{R}), \times)$ | $I_n$（$n$ 阶单位矩阵，主对角线为 $1$，其余为 $0$） |
| $(\mathcal{P}(Y), \cap)$ | $Y$（全集是交运算的幺元） |
| $(\mathcal{P}(Y), \cup)$ | $\varnothing$（空集是并运算的幺元） |
| $(\mathcal{P}(Y), \triangle)$ | $\varnothing$（空集是对称差的幺元） |
| $(\Sigma^*, \cdot)$ | $\varepsilon$（空字符串） |
| $(M(Y), \circ)$ | $\operatorname{id}_Y$（$Y$ 上的恒等映射） |
$0$ 和 $1$ 在数中具有特殊地位，正是因为它们分别是加法和乘法的幺元。单位矩阵在线性代数中的重要性也源于此。
4.3 幺元的唯一性
命题：设 $(S, *)$ 是一个代数结构。若 $e_1$ 是左幺元，$e_2$ 是右幺元，则 $e_1 = e_2$。
特别地，若幺元存在则唯一。
证明：
\[e_1 = e_1 * e_2 = e_2\]更仔细地：
- $e_1$ 是左幺元，$e_2 \in S$，故 $e_1 * e_2 = e_2$
- $e_2$ 是右幺元，$e_1 \in S$，故 $e_1 * e_2 = e_1$
因此 $e_1 = e_1 * e_2 = e_2$。$\blacksquare$
证明虽短，但适用范围极广：任何集合上的任何二元运算，只要有左幺元和右幺元，它们就必然相等。这也说明了为什么单位矩阵是唯一的——不需要用矩阵乘法的具体定义去验证。
注意：
- 幺元可以不存在（例如全体偶数在乘法下构成半群，但没有幺元——$1$ 不是偶数）
- 可能只有左幺元而没有右幺元（或反之）
- 但只要左幺元和右幺元都存在，它们就相等
五、群的引入
5.1 从半群到群
半群只要求结合律。群在此基础上还要求：
- 有幺元
- 每个元素都有逆元
5.2 群与非群的对比
$(\mathbb{Z}, +)$ 是群：
- 结合律：$\checkmark$
- 幺元：$0$
- 逆元：$\forall a \in \mathbb{Z}$，$-a \in \mathbb{Z}$，且 $a + (-a) = 0$
$(\mathbb{Z}, \times)$ 不是群：
- 结合律：$\checkmark$
- 幺元：$1$
- 逆元：$0$ 没有乘法逆元（$0$ 乘任何数都是 $0$，不可能等于 $1$）；$a \ne \pm 1$ 时，$\frac{1}{a} \notin \mathbb{Z}$
$(M_n(\mathbb{R}), \times)$（$n \ge 2$）不是群：
- 不可逆矩阵（$\det A = 0$）没有逆元
- 例如某一行全零的矩阵不可逆
$(\mathbb{Q} \setminus {0}, \times)$ 是群：
- 结合律：$\checkmark$
- 幺元：$1$
- 逆元：$\forall a \in \mathbb{Q} \setminus {0}$，$\frac{1}{a} \in \mathbb{Q} \setminus {0}$，且 $a \cdot \frac{1}{a} = 1$
整数在乘法下不是群，但把范围扩大到非零有理数就成了群。