14.3 几个典型的代数系统

本节对应原书 PDF 第 330–345 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

上一节给出的是代数系统的一般框架。本节把注意力收到几类有广泛应用背景的具体系统上：半群、独异点与群，环与域，以及格与布尔代数。

14.3.1 半群与独异点

半群与独异点是最简单的代数系统.

定义 14.12

(1) 设 V=\langle S, \circ \rangle 是代数系统,\circ 为二元运算. 如果 \circ 运算是可结合的,则称 V 为半群.

(2) 设 V=\langle S, \circ \rangle 是半群,若 e \in S 是关于 \circ 运算的单位元,则称 V 是含幺半群,也称作独异点. 有时也将独异点 V 记作 V=\langle S, \circ, e \rangle.

解读：半群与独异点只差一条要求——有没有单位元。判断时先看结合律,再看集合里是否真的含单位元;\langle \mathbf{Z}^+, + \rangle 有结合律但没有单位元 0,所以只是半群。

例 14.13　(1) \langle \mathbf{Z}^+, + \rangle,\langle \mathbf{N}, + \rangle,\langle \mathbf{Z}, + \rangle,\langle \mathbf{Q}, + \rangle,\langle \mathbf{R}, + \rangle 都是半群,+ 是普通加法. 这些半群中除 \langle \mathbf{Z}^+, + \rangle 外都是独异点.

(2) 设 n 是大于 1 的正整数.\langle M_n(\mathbf{R}), + \rangle 和 \langle M_n(\mathbf{R}), \cdot \rangle 都是半群,也都是独异点,其中 + 和 \cdot 分别表示矩阵加法和矩阵乘法.

(3) \langle P(B), \oplus \rangle 为半群,也是独异点,其中 \oplus 为集合的对称差运算.

(4) \langle \mathbf{Z}_n, \oplus \rangle 为半群,也是独异点,其中 \mathbf{Z}_n=\{0,1,\cdots,n-1\},\oplus 为模 n 加法.

(5) \langle A^A, \circ \rangle 为半群,也是独异点,其中 \circ 为函数的复合运算.

(6) \langle \mathbf{R}^*, \cdot \rangle 为半群,其中 \mathbf{R}^* 为非零实数集合,\cdot 运算定义如下:\forall x,y \in \mathbf{R}^*,x \cdot y=y.

由于半群中的运算满足结合律,可以定义元素的幂. 在半群 \langle S, \circ \rangle 中,\forall x \in S,规定

用数学归纳法不难证明 x 的幂遵循以下运算规则

类似地,可以定义独异点 \langle S, \circ, e \rangle 中元素的幂,\forall x \in S,有

独异点的幂运算也遵从半群的幂运算规则,但其中的 m 和 n 是自然数.

半群与独异点的子代数分别称为子半群与子独异点. 根据定义可以直接得到子半群与子独异点的判定方法:

设 V=\langle S, \circ \rangle 是半群,T \subseteq S,T 非空,如果 T 对 V 中的运算 \circ 封闭,则 \langle T, \circ \rangle 是 V 的子半群.

设 V=\langle S, \circ, e \rangle 是独异点,T \subseteq S,T 非空,如果 T 对 V 中的运算 \circ 封闭,而且 e \in T,那么 \langle T, \circ, e \rangle 构成 V 的子独异点.

对于子独异点,不但要求运算封闭,而且要求单位元 e 也在子独异点中出现.

解读：子半群只要「封闭」,子独异点还多要一条「把大系统的单位元也圈进来」。少了 e 的子集即使自己另有一个单位元,也只能算子半群——这正是下面例 14.14 的考点。

例 14.14　设半群 V_1=\langle S, \cdot \rangle,独异点 V_2=\langle S, \cdot, e \rangle. 其中 \cdot 为矩阵乘法,e 为 2 阶单位矩阵,且

则 T \subseteq S,且 T 是 V_1=\langle S, \cdot \rangle 的子半群.\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} 是 T 的单位元,T 本身可以构成独异点,但不是 S 的子独异点,因为 S 的单位元是 e.

可以按照定义 14.10 构造半群与独异点的直积. 不难看出,半群的直积还是半群,独异点的直积还是独异点.

下面讨论半群与独异点的同态.

定义 14.13　(1) 设 V_1=\langle S_1, \circ \rangle,V_2=\langle S_2, * \rangle 是半群,f: S_1 \to S_2. 若对任意的 x,y \in S_1 有

则称 f 为半群 V_1 到 V_2 的同态映射,简称同态.

(2) 设 V_1=\langle S_1, \circ, e_1 \rangle,V_2=\langle S_2, *, e_2 \rangle 是独异点,f: S_1 \to S_2. 若对任意的 x,y \in S_1 有

则称 f 为独异点 V_1 到 V_2 的同态映射,简称同态.

因为半群和独异点只有一个二元运算,为了书写的简便,经常省略上述表达式中的算符 \circ 和 *,而简记为 f(xy)=f(x)f(y).

在例 14.14 中,如令

则 f 是半群 V_1=\langle S, \cdot \rangle 的自同态,但不是独异点 V_2=\langle S, \cdot, e \rangle 的自同态,因为 f(e) \neq e.

半群与独异点在有限自动机理论中有着重要的应用. 有兴趣的读者请看相关的参考书.

14.3.2 群

群是特殊的半群与独异点. 下面讨论群的定义与性质.

定义 14.14　设 \langle G, \circ \rangle 是代数系统,\circ 为二元运算. 如果 \circ 运算是可结合的,存在单位元 e \in G,并且对 G 中的任何元素 x 都有 x^{-1} \in G,则称 G 为群.

例 14.15　(1) \langle \mathbf{Z}, + \rangle,\langle \mathbf{Q}, + \rangle,\langle \mathbf{R}, + \rangle 都是群;\langle \mathbf{Z}^+, + \rangle 和 \langle \mathbf{N}, + \rangle 不是群.

(2) \langle M_n(\mathbf{R}), + \rangle 是群,而 \langle M_n(\mathbf{R}), \cdot \rangle 不是群.

(3) \langle P(B), \oplus \rangle 是群,\oplus 为对称差运算.

(4) \langle \mathbf{Z}_n, \oplus \rangle 是群. \mathbf{Z}_n=\{0,1,\cdots,n-1\},\oplus 为模 n 加法.

(5) 设 G=\{e,a,b,c\},G 上的运算由表 14.12 给出,称为 Klein 四元群.

表 14.12

下面介绍有关群的术语.

定义 14.15　(1) 若群 G 是有穷集,则称 G 是有限群,否则称为无限群. 群 G 的元素数称为群 G 的阶,有限群 G 的阶记作 |G|.

(2) 只含单位元的群称为平凡群.

(3) 若群 G 中的二元运算是可交换的,则称 G 为交换群或阿贝尔(Abel)群.

例如 \langle \mathbf{Z}, + \rangle 和 \langle \mathbf{R}, + \rangle 是无限群,\langle \mathbf{Z}_n, \oplus \rangle 是有限群,也是 n 阶群. Klein 四元群是 4 阶群. \langle \{0\}, + \rangle 是平凡群. 上述群都是交换群,n 阶(n \geq 2)实可逆矩阵集合关于矩阵乘法构成的群是非交换群.

定义 14.16　设 G 是群,a \in G,n \in \mathbf{Z},则 a 的 n 次幂定义如下:

与半群和独异点不同,群中元素可以定义负整数次幂. 例如在模 3 加群 \langle \mathbf{Z}_3, \oplus \rangle 中有

在整数加群 \langle \mathbf{Z}, + \rangle 中有

定义 14.17　设 G 是群,a \in G,使得等式 a^k=e 成立的最小正整数 k 称为 a 的阶,记作 |a|=k,这时称 a 为 k 阶元. 若不存在这样的正整数 k,则称 a 为无限阶元.

例如在模 6 加群 \langle \mathbf{Z}_6, \oplus \rangle 中,2 和 4 是 3 阶元,3 是 2 阶元,1 和 5 是 6 阶元,0 是 1 阶元. 在整数加群 \langle \mathbf{Z}, + \rangle 中,0 是 1 阶元,其他整数都是无限阶元. 而在 Klein 四元群中除了单位元 e 以外,其他元素都是 2 阶元.

解读：群 G 的阶 |G| 数的是元素的个数,元素的阶 |a| 数的是 a 自己回到单位元所需的步数——同一个记号 |\cdot| 装着两个不同概念,读题时看竖线里是群还是元素。

群具有下述性质.

定理 14.3　设 G 为群,则 G 中的幂运算满足:

(1) \forall a \in G,(a^{-1})^{-1}=a.

(2) \forall a,b \in G,(ab)^{-1}=b^{-1}a^{-1}.

(3) \forall a \in G,a^m a^n=a^{m+n},m,n \in \mathbf{Z}.

(4) \forall a \in G,(a^m)^n=a^{mn},n,m \in \mathbf{Z}.

(5) 若 G 为交换群,则 (ab)^n=a^n b^n.

证明　这里只证(1)和(2).

(1) (a^{-1})^{-1} 是 a^{-1} 的逆元,a 也是 a^{-1} 的逆元. 根据逆元的唯一性,等式得证.

(2) (b^{-1}a^{-1})(ab)=b^{-1}(a^{-1}a)b=b^{-1}b=e,同理 (ab)(b^{-1}a^{-1})=e,故 b^{-1}a^{-1} 是 ab 的逆元. 根据逆元的唯一性等式得证.

(3),(4),(5)的证明要使用数学归纳法,先对自然数 n 和 m 证明等式为真,然后讨论 n 或 m 为负数的情况. 注意(2)中的结果可以推广到有限多个元素的情况,即

定理 14.4　G 为群,\forall a,b \in G,方程 ax=b 和 ya=b 在 G 中有解且仅有唯一解.

证明　a^{-1}b 代入方程左边的 x 得

所以 a^{-1}b 是该方程的解. 下面证明唯一性. 假设 c 是方程 ax=b 的解,必有 ac=b,从而有

因此 a^{-1}b 是方程 ax=b 的唯一解. 同理可证 ba^{-1} 是方程 ya=b 的唯一解.

定理 14.5　G 为群,则 G 中适合消去律,即对任意 a,b,c \in G,有

(1) 若 ab=ac,则 b=c.

(2) 若 ba=ca,则 b=c.

证明留作练习.

定理 14.6　G 为群,a \in G 且 |a|=r. 设 k 是整数,则

(1) a^k=e 当且仅当 r \mid k.

(2) |a^{-1}|=|a|.

证明　(1) 充分性. 由于 r \mid k,必存在整数 m 使得 k=mr,所以有

必要性. 根据除法,存在整数 m 和 i 使得 k=mr+i,其中 0 \leq i \leq r-1. 从而有

因为 |a|=r 且 i<r,必有 i=0. 这就证明了 r \mid k.

(2) 由 (a^{-1})^r=(a^r)^{-1}=e^{-1}=e 可知 a^{-1} 的阶存在. 令 |a^{-1}|=t,根据(1)的结果有 t \mid r. a 又是 a^{-1} 的逆元,所以又有 r \mid t. 从而证明了 r=t,即 |a^{-1}|=|a|.

下面通过一些例题说明上述定理的应用.

例 14.16　设 G=\{a_1,a_2,\cdots,a_n\} 是 n 阶群,令

证明　a_i G=G.

证明　由群中运算的封闭性有 a_i G \subseteq G. 假设 a_i G \subset G,即 |a_i G|<n. 必有 a_i, a_k \in G 使得

由消去律得 a_j=a_k,与 |G|=n 矛盾.

解读：这一题的关键是「左乘 a_i 不改变元素个数」:消去律保证不同的 a_j 映到不同的位置,所以 a_i G 与 G 一样大,再由包含关系只能相等。

例 14.17　设 G 是群,a,b \in G 是有限阶元. 证明:

(1) |b^{-1}ab|=|a|.

(2) |ab|=|ba|.

证明　(1) 设 |a|=r,|b^{-1}ab|=t,则有

从而有 t \mid r. 另一方面,由

可知 r \mid t. 从而有 |b^{-1}ab|=|a|.

(2) 设 |ab|=r,|ba|=t,则有

由消去律得 (ab)^t=e,从而可知 r \mid t. 同理可证 t \mid r. 因此 |ab|=|ba|.

下面考虑群的子代数系统,可以证明下面定义的子群就是群的子代数.

定义 14.18　设 G 是群,H 是 G 的非空子集,如果 H 关于 G 中的运算构成群,则称 H 是 G 的子群,记作 H \leq G. 若 H 是 G 的子群,且 H \subset G,则称 H 是 G 的真子群,记作 H<G.

例如,n\mathbf{Z}(n 是自然数)是整数加群 \langle \mathbf{Z}, + \rangle 的子群. 当 n \neq 1 时,n\mathbf{Z} 是 \mathbf{Z} 的真子群. 任何群 G 都存在子群. G 和 \{e\} 都是 G 的子群,称为 G 的平凡子群.

下面给出子群的两个主要的判定定理.

定理 14.7(判定定理一)　设 G 为群,H 是 G 的非空子集,则 H 是 G 的子群当且仅当

(1) \forall a,b \in H 有 ab \in H.

(2) \forall a \in H 有 a^{-1} \in H.

证明　必要性是显然的. 为证明充分性,只需证明 e \in H. 因为 H 非空,存在 a \in H. 由条件(2)知 a^{-1} \in H,根据条件(1)有 aa^{-1} \in H,即 e \in H.

定理 14.8(判定定理二)　设 G 为群,H 是 G 的非空子集. H 是 G 的子群当且仅当 \forall a,b \in H 有 ab^{-1} \in H.

证明　必要性是显然的. 这里只证充分性. 因为 H 非空,必存在 a \in H. 根据给定条件得 aa^{-1} \in H,即 e \in H. 任取 a \in H,由 e,a \in H 得 ea^{-1} \in H,即 a^{-1} \in H. 任取 a,b \in H,知 b^{-1} \in H. 再利用给定条件得 a(b^{-1})^{-1} \in H,即 ab \in H. 综合上述,可知 H 是 G 的子群.

解读：判定定理二把定理一的两条合成一条 ab^{-1}\in H。验算时它更省事:一次同时用到逆元和封闭性,不用先单独证逆元封闭。

根据这些判定定理可以证明一些重要的子群,如生成子群、群的中心等.

例 14.18　设 G 为群,a \in G,令 H=\{a^k \mid k \in \mathbf{Z}\},可以证明 H 是 G 的子群,称为由 a 生成的子群,记作 \langle a \rangle.

证明　首先由 a \in \langle a \rangle 知道 \langle a \rangle \neq \varnothing. 任取 a^m, a^l \in \langle a \rangle,有

根据判定定理二可知 \langle a \rangle \leq G.

考虑整数加群,由 2 生成的子群是 \langle 2 \rangle=\{2k \mid k \in \mathbf{Z}\}=2\mathbf{Z}. 在群 \langle \mathbf{Z}_6, \oplus \rangle 中,由 2 生成的子群是 \langle 2 \rangle=\{0,2,4\},Klein 四元群 G=\{e,a,b,c\} 的所有由单个元素生成的子群是

例 14.19　设 G 为群,令

可以证明 C 是 G 的子群,称为 G 的中心.

证明　由于 e \in C,C 是 G 的非空子集. 任取 a,b \in C,只需证明 ab^{-1} 与 G 中所有的元素都可交换. \forall x \in G,有

由判定定理二可知 C \leq G.

对于阿贝尔群 G,因为 G 中所有的元素互相都可交换,G 的中心就等于 G. 但是对某些非交换群 G,它的中心是 \{e\}.

可以用一种图示的方法——子群格给出有限群的子群的结构. 设 G 为群,令

则偏序集 \langle L(G), \subseteq \rangle 称为 G 的子群格. 例如 Klein 四元群的子群格如图 14.2 所示.

图 14.2

根据代数系统同态与同构的定义可以直接得到群同态和同构的定义.

定义 14.19　设 G_1,G_2 是群,f: G_1 \to G_2,若 \forall a,b \in G_1 都有

则称 f 是群 G_1 到 G_2 的同态映射,简称同态.

下面介绍一些典型的群同态映射.

例 14.20　(1) G_1=\langle \mathbf{Z}, + \rangle 是整数加群,G_2=\langle \mathbf{Z}_n, \oplus \rangle 是模 n 的整数加群. 令

则 f 是 G_1 到 G_2 的满同态. \forall x,y \in \mathbf{Z} 有

(2) 设 G=\langle \mathbf{Z}_n, \oplus \rangle 是模 n 整数加群,可以证明恰有 n 个 G 的自同态,即

(3) 设 G_1,G_2 是群,e_2 是 G_2 的单位元. 令

则 f 是 G_1 到 G_2 的同态,称为零同态. 因为 \forall a,b \in G_1 有

(4) G 为群,a \in G. 令

则 f 是 G 的自同构,称为 G 的内自同构. 关于 f 为自同构的证明留作练习.

群的同态映射也具有 14.2 节所说的性质. 下面给出这些性质的应用实例.

例 14.21　设 G_1=\langle \mathbf{Q}, + \rangle 是有理数加群,G_2=\langle \mathbf{Q}^*, \cdot \rangle 是非零有理数乘法群. 证明不存在 G_2 到 G_1 的同构.

证明　假设 f 是 G_2 到 G_1 的同构,那么有 f: G_2 \to G_1,f(1)=0,于是有

从而得 f(-1)=0,这与 f 的单射性矛盾.

解读：同态保持单位元和逆元,却保不住「x^2=1 的解有几个」。\mathbf{Q}^* 里 1 和 -1 都满足 x^2=1,而 \mathbf{Q} 里只有 0,这条差异直接把同构挡死。

在结束这一小节之前,特别要提到两类重要的群——循环群与置换群.

定义 14.20　设 G 是群,若存在 a \in G 使得 G=\{a^k \mid k \in \mathbf{Z}\},则称 G 是循环群,记作 G=\langle a \rangle,称 a 为 G 的生成元.

对于循环群 G=\langle a \rangle,根据生成元 a 的阶可以将它们分成两类:n 阶循环群和无限循环群. 若 a 是 n 阶元,则

那么 |G|=n,称 G 为 n 阶循环群. 若 a 是无限阶元,则

这时称 G 为无限循环群.

如何找到循环群的所有生成元和子群呢? 下面的定理给出了系统的方法.

定理 14.9　设 G=\langle a \rangle 是循环群.

(1) 若 G 是无限循环群,则 G 只有两个生成元,即 a 和 a^{-1}.

(2) 若 G 是 n 阶循环群,则 G 含有 \phi(n) 个生成元. 这里的 \phi(n) 是欧拉函数(见 9.1 节),对于任何小于 n 且与 n 互素的自然数 r,a^r 是 G 的生成元.

定理 14.10　设 G=\langle a \rangle 是循环群,那么

(1) G 的子群仍是循环群.

(2) 若 G=\langle a \rangle 是无限循环群,则 G 的子群除 \{e\} 以外都是无限循环群. 对于任何自然数 r,\langle a^r \rangle 都是 G 的一个子群,且对于不同的 r,所得到的子群 \langle a^r \rangle 也不同.

(3) 若 G=\langle a \rangle 是 n 阶循环群,则对 n 的每个正因子 d,G 恰好含有一个 d 阶子群,就是 \langle a^{\frac{n}{d}} \rangle.

省去上述两个定理的证明,这里仅给出一些应用实例.

例 14.22　(1) 设 G=\{e,a,\cdots,a^{11}\} 是 12 阶循环群,则 \phi(12)=4. 小于 12 且与 12 互素的自然数是 1,5,7,11,由定理 14.9 可知 a,a^5,a^7 和 a^{11} 是 G 的生成元. 12 的正因子是 1,2,3,4,6,12,根据定理 14.10,G 有 6 个子群,即:\langle a^1 \rangle,\langle a^2 \rangle,\langle a^3 \rangle,\langle a^4 \rangle,\langle a^6 \rangle,\langle e \rangle.

(2) 设 G=\langle \mathbf{Z}_{15}, \oplus \rangle 是模 15 的整数加群,则 \phi(15)=8. 小于 15 且与 15 互素的数是 1,2,4,7,8,11,13,14. 根据定理 14.9,G 的生成元是 1,2,4,7,8,11,13 和 14. 15 有 4 个正因子:1,3,5,15,因此有 4 个子群,即:\langle 1 \rangle,\langle 3 \rangle,\langle 5 \rangle,\langle 0 \rangle.

(3) 设 G=\langle \mathbf{Z}, + \rangle,那么 G 只有两个生成元:1 和 -1. G 的子群有无数多个,即对于任何自然数 n,\langle n \rangle=n\mathbf{Z}=\{nk \mid k \in \mathbf{Z}\} 都是 G 的子群.

解读：找生成元就是数「与 n 互素且小于 n 的数」,找子群就是数「n 的正因子」——两个计数分别对应定理 14.9 与定理 14.10。

置换群在具有对称结构的离散系统中有着重要的应用. 下面考虑置换群. 首先给出 n 元置换的定义.

定义 14.21　设 S=\{1,2,\cdots,n\},S 上的任何双射函数 \sigma: S \to S 称为 S 上的 n 元置换. 一般将 n 元置换 \sigma 记为

例如,S=\{1,2,3,4,5\},则

都是 5 元置换.

定义 14.22　设 \sigma,\tau 是 n 元置换,\sigma 和 \tau 的复合 \sigma \circ \tau 也是 n 元置换,称为 \sigma 与 \tau 的乘积,记作 \sigma\tau.

例如,

如果在两个 n 元置换 \sigma 和 \tau 的作用下只有部分元素发生了改变,同时其他元素保持不变,并且在 \sigma 和 \tau 的作用下发生改变的元素彼此不同,那么可以证明这两个置换复合的结果与置换的次序无关,即 \sigma\tau=\tau\sigma.

n 元置换可以采用轮换的乘积来表示. 一般来说,这是一种更为简洁的表示方法.

定义 14.23　设 \sigma 是 S=\{1,2,\cdots,n\} 上的 n 元置换. 若

且保持 S 中的其他元素不变,则称 \sigma 为 S 上的 k 阶轮换,记作 (i_1 i_2 \cdots i_k). 若 k=2,称 \sigma 为 S 上的对换.

任何 n 元置换可以分解为不相交的轮换之积. 下面叙述一种分解方法.

设 S=\{1,2,\cdots,n\},对于任何 S 上的 n 元置换 \sigma 一定存在着一个有限序列 i_1,i_2,\cdots,i_k,k \geq 1(可以取 i_1=1),使得

令 \sigma_1=(i_1 i_2 \cdots i_k). 它是从 \sigma 中分解出来的第一个轮换. 根据复合定义可将 \sigma 写作 \sigma_1 \sigma',其中 \sigma' 作用于 S-\{i_1,i_2,\cdots,i_k\} 上的元素. 继续对 \sigma' 进行类似的分解. 由于 S 中只有 n 个元素,经过有限步以后,必得到 \sigma 的轮换分解式 \sigma=\sigma_1 \sigma_2 \cdots \sigma_t. 例如,S=\{1,2,\cdots,8\},

从 \sigma 中分解出来的第一个轮换是 (1\ 5\ 2\ 3\ 6);第二个轮换是 (4);第三个轮换是 (7\ 8). \sigma 的轮换表示式是 \sigma=(1\ 5\ 2\ 3\ 6)(4)(7\ 8)=(1\ 5\ 2\ 3\ 6)(7\ 8). 为了使表达式更为简洁,在具有 2 个以上轮换的表达式中,往往可以省略其中的 1 轮换. 因此 \sigma 可以写作 (1\ 5\ 2\ 3\ 6)(7\ 8).

容易看到,分解出来的轮换之间没有公共元素,因此分解结果只与轮换表示有关,而与轮换的顺序无关. 可以证明这种分解结果是唯一的. 这里的唯一性指的是:如果

是 \sigma 的两个轮换表示式,则有

除了表达成轮换以外,任何 n 元置换还可以表示成对换的乘积. 为此,只需证明任何轮换都可以表示成对换乘积就足够了. 这可以由下述 k 阶轮换表示式来证明.

例如,

不难看出,用对换来表示 n 元置换,表示方法一般来说不是唯一的. 如 3 元置换 (1\ 2\ 3) 可以表示为 (1\ 2)(1\ 3),也可以表示为 (2\ 3)(2\ 1). 尽管表示方法不相同,但是可以证明表示式中含有对换个数的奇偶性是不变的. 如果一个 n 元置换在它的对换表示式含有偶数个对换,则称为偶置换,否则称为奇置换. 使用一一对应的思想可以知道奇置换和偶置换的个数都是 n!/2.

解读：轮换分解是「唯一的」,而对换分解不唯一,唯一保留下来的是对换个数的奇偶性——偶置换/奇置换的定义正是建立在这条不变量上。

考虑所有的 n 元置换构成的集合 S_n. 显然 S_n 关于置换的乘法是封闭的,置换的乘法满足结合律,恒等置换(1)是 S_n 中的单位元,对于任何 n 元置换 \sigma \in S_n,逆置换 \sigma^{-1} 是 \sigma 的逆元. 这就证明了 S_n 关于置换的乘法构成一个群,称为 n 元对称群. n 元对称群的子群称为 n 元置换群.

例 14.23　设 S=\{1,2,3\},则 3 元对称群

S_3 的运算表如表 14.13 所示.

表 14.13

14.3.3 环与域

环是具有两个二元运算的代数系统,通常将这两个运算分别记作“+”和“\cdot”,这两个运算分别具有群运算与半群运算的特征. 域是特殊的环.

定义 14.24　设 \langle R, +, \cdot \rangle 是代数系统,+ 和 \cdot 是二元运算. 如果满足以下条件:

(1) \langle R, + \rangle 构成交换群.

(2) \langle R, \cdot \rangle 构成半群.

(3) \cdot 运算关于 + 运算适合分配律.

则称 \langle R, +, \cdot \rangle 是一个环.

为了叙述的方便,通常称 + 运算为环中的加法,\cdot 运算为环中的乘法. 环中加法单位元记作 0,乘法单位元(如果存在)记作 1. 对任何元素 x,称 x 的加法逆元为负元,记作 -x. 若 x 存在乘法逆元的话,则称之为逆元,记作 x^{-1}. 因此在环中写 x-y 意味着 x+(-y).

解读：环的乘法只要求半群,连交换律和单位元都不要求——所以 n 阶实矩阵环 M_n(\mathbf{R}) 是环却不是整环,差别全在乘法这一侧。

例 14.24　(1) 整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环,分别称为整数环 \mathbf{Z},有理数环 \mathbf{Q},实数环 \mathbf{R} 和复数环 \mathbf{C}.

(2) n(n \geq 2)阶实矩阵集合 M_n(\mathbf{R}) 关于矩阵的加法和乘法构成环,称为 n 阶实矩阵环.

(3) 设 \mathbf{Z}_n=\{0,1,\cdots,n-1\},\oplus 和 \otimes 分别表示模 n 的加法和乘法,则 \langle \mathbf{Z}_n, \oplus, \otimes \rangle 构成环,称为模 n 的整数环.

省去证明,我们通过定理 14.11 叙述了环的运算性质.

定理 14.11　设 \langle R, +, \cdot \rangle 是环,则

(1) \forall a \in R,a0=0a=0.

(2) \forall a,b \in R,(-a)b=a(-b)=-ab.

(3) \forall a,b,c \in R,a(b-c)=ab-ac,(b-c)a=ba-ca.

(4) \forall a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m \in R(n,m \geq 2).

从上述定理可以看出,环中加法的单位元恰好是乘法的零元. 在环中进行计算,除了乘法不能使用交换律以外,其他都与普通数的运算相同. 这里给出一个环中运算的例子.

例 14.25　在环中计算 (a+b)^3,(a-b)^2.

解　(a+b)^3=(a+b)(a+b)(a+b)

=(a^2+ba+ab+b^2)(a+b)

=a^3+ba^2+aba+b^2 a+a^2 b+bab+ab^2+b^3

(a-b)^2=(a-b)(a-b)=a^2-ba-ab+b^2

环的子代数就是子环.

定义 14.25　设 R 是环,S 是 R 的非空子集. 若 S 关于环 R 的加法和乘法也构成一个环,则称 S 为 R 的子环. 若 S 是 R 的子环,且 S \subset R,则称 S 是 R 的真子环.

例如整数环 \mathbf{Z},有理数环 \mathbf{Q} 都是实数环 \mathbf{R} 的真子环. \{0\} 和 \mathbf{R} 也是实数环 \mathbf{R} 的子环,称为平凡子环.

根据子半群与子群的判定定理可以得到关于子环的判定定理.

定理 14.12(子环判定定理)　设 R 是环,S 是 R 的非空子集,若

(1) \forall a,b \in S,a-b \in S.

(2) \forall a,b \in S,ab \in S.

则 S 是 R 的子环.

例 14.26　(1) 整数环 \langle \mathbf{Z}, +, \cdot \rangle,对于任意给定的自然数 n,n\mathbf{Z}=\{nz \mid z \in \mathbf{Z}\} 是 \mathbf{Z} 的非空子集,根据判定定理,容易验证 n\mathbf{Z} 是整数环的子环.

(2) 考虑模 6 整数环 \langle \mathbf{Z}_6, \oplus, \otimes \rangle,\{0\},\{0,3\},\{0,2,4\},\mathbf{Z}_6 是它的子环. 其中 \{0\} 和 \mathbf{Z}_6 是平凡的,其余的都是非平凡的真子环.

可以将代数系统的同态概念引入环,从而得到环同态的概念.

定义 14.26　设 R_1 和 R_2 是环,f: R_1 \to R_2,若对于任意的 x,y \in R_1 有

成立,则称 f 是环 R_1 到 R_2 的同态映射,简称环同态.

例 14.27　设 R_1=\langle \mathbf{Z}, +, \cdot \rangle 是整数环,R_2=\langle \mathbf{Z}_n, \oplus, \otimes \rangle 是模 n 的整数环. 令 f: \mathbf{Z} \to \mathbf{Z}_n,f(x)=x \bmod n,则 \forall x,y \in \mathbf{Z} 有

f 是 R_1 到 R_2 的同态,是满同态.

环中的乘法只要求满足结合律,如果对环中乘法加以更多的限制,将得到一些特殊的环.

定义 14.27　设 \langle R, +, \cdot \rangle 是环,

(1) 若环中乘法 \cdot 适合交换律,则称 R 是交换环.

(2) 若环中乘法 \cdot 存在单位元,则称 R 是含幺环.

(3) 若 \forall a,b \in R,ab=0 \Rightarrow a=0 \vee b=0,则称 R 是无零因子环.

(4) 若 R 既是交换环、含幺环,也是无零因子环,则称 R 是整环.

先解释一下零因子的概念. 作为数的乘法,如果 ab=0,那么一定有 a=0 或者 b=0. 但是,作为一般的环的乘法不一定满足这条性质. 有时候两个不为 0 的元素乘起来却等于 0. 例如在模 6 整数环中,有 3 \otimes 2=0,而 3 和 2 都不是乘法的零元. 这时称 3 为左零因子,2 为右零因子. 这种含有左零因子和右零因子的环就不是无零因子环.

解读：交换环、含幺环、无零因子环是三条互相独立的附加条件,整环要三条同时满足。2\mathbf{Z} 满足前两条中的交换律但缺单位元 1,所以是无零因子环却不是整环。

例 14.28　(1) 整数环 \mathbf{Z}、有理数环 \mathbf{Q}、实数环 \mathbf{R}、复数环 \mathbf{C} 都是交换环、含幺环、无零因子环和整环.

(2) 令 2\mathbf{Z}=\{2z \mid z \in \mathbf{Z}\},则 \langle 2\mathbf{Z}, +, \cdot \rangle 构成交换环和无零因子环. 但不是含幺环和整环.

(3) 设 n \in \mathbf{Z},n \geq 2,则 n 阶实矩阵的集合 M_n(\mathbf{R}) 关于矩阵加法和乘法构成环,它是含幺环,但不是交换环和无零因子环,也不是整环.

(4) \langle \mathbf{Z}_n, \oplus, \otimes \rangle 构成环,它是交换环、含幺环,但不是无零因子环和整环. 可以证明对于一般的 n,\mathbf{Z}_n 是整环当且仅当 n 是素数.

定义 14.28　设 R 是整环,且 R 中至少含有两个元素. 若 \forall a \in R^*,其中 R^*=R-\{0\},都有 a^{-1} \in R,则称 R 是域.

例如,有理数集 \mathbf{Q}、实数集 \mathbf{R}、复数集 \mathbf{C} 关于普通的加法和乘法都构成域,分别称为有理数域、实数域和复数域. 整数环 \mathbf{Z} 是整环,而不是域. 对于模 n 的整数环 \mathbf{Z}_n,若 n 是素数,那么 \mathbf{Z}_n 是域. 域具有良好的性质,在编码系统、信息加密等领域都有着重要的应用.

例 14.29　判断下列集合和给定运算是否构成环、整环和域. 如果不构成,说明理由.

(1) A=\{a+bi \mid a,b \in \mathbf{Q}\},其中 i^2=-1,运算为复数加法和乘法.

(2) A=\{2z+1 \mid z \in \mathbf{Z}\},运算为实数加法和乘法.

(3) A=\{2z \mid z \in \mathbf{Z}\},运算为实数加法和乘法.

(4) A=\{x \mid x \geq 0 \wedge x \in \mathbf{Z}\},运算为实数加法和乘法.

(5) A=\{a+b\sqrt[3]{5} \mid a,b \in \mathbf{Q}\},运算为实数加法和乘法.

解　(1) 是环,是整环,也是域.

(2) 不是环,因为关于加法不封闭.

(3) 是环,不是整环和域,因为乘法没有单位元.

(4) 不是环,因为正整数关于加法的负元不存在,A 关于加法不构成群.

(5) 不是环,因为关于乘法不封闭.

14.3.4 格与布尔代数

格是具有两个二元运算的代数系统,这两个运算呈现了与环不同的性质,大家熟悉的逻辑代数、集合代数等都是格的特例.

定义 14.29　设 \langle S, \preccurlyeq \rangle 是偏序集,如果 \forall x,y \in S,\{x,y\} 都有最小上界和最大下界,则称 S 关于偏序 \preccurlyeq 构成一个格.

由于最小上界和最大下界的唯一性,可以把求 \{x,y\} 的最小上界和最大下界看成 x 与 y 的二元运算 \vee 和 \wedge,即 x \vee y 和 x \wedge y 分别表示 x 与 y 的最小上界和最大下界.

需要说明的是,本章中出现的 \vee 和 \wedge 符号只代表格中的运算,而不再有其他的含义.

解读：格的定义只要求每一对元素都有最小上界和最大下界,并不要求整个集合有全下界或全上界——图 14.4(c) 就是缺少某一对的上界而下界齐全的例子。

例 14.30　设 n 是正整数,S_n 是 n 的正因子的集合. D 为整除关系,则偏序集 \langle S_n, D \rangle 构成格. \forall x,y \in S_n,x \vee y 是 \operatorname{lcm}(x,y),即 x 与 y 的最小公倍数;x \wedge y 是 \gcd(x,y),即 x 与 y 的最大公约数. 图 14.3 给出了格 \langle S_8, D \rangle,\langle S_6, D \rangle 和 \langle S_{30}, D \rangle.

图 14.3

例 14.31　判断下列偏序集是否构成格,并说明理由.

(1) \langle P(B), \subseteq \rangle,其中 P(B) 是集合 B 的幂集.

(2) \langle \mathbf{Z}, \leq \rangle,其中 \mathbf{Z} 是整数集,\leq 为小于或等于关系.

(3) 偏序集的哈斯图分别给在图 14.4.

图 14.4

解　(1)是格. \forall x,y \in P(B),x \vee y 就是 x \cup y,x \wedge y 就是 x \cap y. 称 \langle P(B), \subseteq \rangle 为 B 的幂集格.

(2) 是格. \forall x,y \in \mathbf{Z},x \vee y=\max(x,y),x \wedge y=\min(x,y).

(3) 都不是格. 因为图 14.4(a)的 \{a,b\} 没有最大下界. 图 14.4(b)中的 \{b,d\} 没有最小上界. 图 14.4(c)的 \{b,c\} 没有最小上界.

下面讨论格的一些主要性质. 首先介绍对偶原理.

定义 14.30　设 f 是含有格中元素以及符号 =,\preccurlyeq,\succcurlyeq,\vee 和 \wedge 的命题. 令 f^* 是将 f 中的 \preccurlyeq 替换成 \succcurlyeq、\succcurlyeq 替换成 \preccurlyeq、\vee 替换成 \wedge、\wedge 替换成 \vee 所得到的命题. 称 f^* 为 f 的对偶命题.

例如在格中令 f 是 (a \vee b) \wedge c \preccurlyeq c,f^* 是 (a \wedge b) \vee c \succcurlyeq c. 那么 f 与 f^* 互为对偶命题.

格的对偶原理　设 f 是含有格中元素以及符号 =,\preccurlyeq,\succcurlyeq,\vee 和 \wedge 的命题. 若 f 对一切格为真,则 f 的对偶命题 f^* 也对一切格为真.

例如,对一切格 L 命题“\forall a,b \in L,a \wedge b \preccurlyeq a”都成立. 根据对偶原理,对一切格 L,命题“\forall a,b \in L,a \vee b \succcurlyeq a”也为真.

下面考虑格的运算性质.

定理 14.13　设 \langle L, \preccurlyeq \rangle 是格,则运算 \vee 和 \wedge 适合交换律、结合律、幂等律和吸收律,即

(1) \forall a,b \in L 有 a \vee b=b \vee a 和 a \wedge b=b \wedge a.

(2) \forall a,b,c \in L 有 (a \vee b) \vee c=a \vee (b \vee c) 和 (a \wedge b) \wedge c=a \wedge (b \wedge c).

(3) \forall a \in L 有 a \vee a=a 和 a \wedge a=a.

(4) \forall a,b \in L 有 a \vee (a \wedge b)=a 和 a \wedge (a \vee b)=a.

证明　只证(1)和(2),(3)和(4)留作练习.

(1) a \vee b 是 \{a,b\} 的最小上界,b \vee a 是 \{b,a\} 的最小上界. 由于 \{a,b\}=\{b,a\},所以 a \vee b=b \vee a. 由对偶原理,a \wedge b=b \wedge a 得证.

(2) 这两个等式互为对偶式,只证明其中一个即可. 由最小上界定义有下述不等式:

由式(14.2)和式(14.3)有

由式(14.1)和式(14.4)有 (a \vee b) \vee c \succcurlyeq a \vee (b \vee c) 成立. 同理可证 (a \vee b) \vee c \preccurlyeq a \vee (b \vee c) 成立. 利用这两个不等式,根据偏序的反对称性得 (a \vee b) \vee c=a \vee (b \vee c).

以上定理说明格中运算满足 4 条算律. 需要注意的是,分配律在格中不一定成立,只能成立分配不等式,即 \forall a,b,c \in L 有 (a \wedge b) \vee (a \wedge c) \preccurlyeq a \wedge (b \vee c).

前面定义群和环等代数系统的方法是:先给定集合和运算,然后规定运算的性质. 能不能用这样的方法来定义格呢? 下面的定理说明可以用这种方法定义格,而且这样定义的格与用偏序集方法定义的格是等价的. 由于证明比较复杂,限于篇幅,这里略去证明,仅叙述定理的内容.

定理 14.14　设 \langle S, *, \circ \rangle 是具有两个二元运算的代数系统,若对于 * 和 \circ 运算适合交换律、结合律、吸收律,则可以适当定义 S 中的偏序 \preccurlyeq,使得 \langle S, \preccurlyeq \rangle 构成格,且 \forall a,b \in S 有

根据上述定理,可以给出格的另一定义.

定义 14.31　设 \langle S, *, \circ \rangle 是代数系统,* 和 \circ 是二元运算,如果 * 和 \circ 运算满足交换律、结合律和吸收律,则 \langle S, *, \circ \rangle 构成格.

根据定理 14.14,格的上述定义与格的偏序集定义是等价的,且 * 和 \circ 运算分别对应于求最大下界与最小上界的运算. 因此,在给出格的代数定义时,通常将这两个运算记作 \wedge 和 \vee.

下面考虑格的子代数.

定义 14.32　设 \langle L, \wedge, \vee \rangle 是格,S 是 L 的非空子集,若 S 关于 L 中的运算 \wedge 和 \vee 仍构成格,则称 S 是 L 的子格.

解读：格的偏序定义与代数定义等价,关键在定理 14.14——交换律、结合律、吸收律三条一给,偏序就能反推出来,所以两种定义可以自由切换使用。

例 14.32　设格 L 如图 14.5 所示. 令 S_1=\{a,e,f,g\},S_2=\{a,b,e,g\},则 S_1 不是 L 的子格,S_2 是 L 的子格. 因为对于 e,f \in S_1,e \wedge f=c \notin S_1.

图 14.5

与环同态类似也可以定义格的同态.

定义 14.33　设 L_1 和 L_2 是格,f: L_1 \to L_2,若 \forall a,b \in L_1 有

成立,则称 f 为格 L_1 到 L_2 的同态映射,简称格同态.

下面考虑一些特殊的格:分配格、有补格与布尔格.

定义 14.34　设 \langle L, \wedge, \vee \rangle 是格,若 \forall a,b,c \in L,有

则称 L 为分配格.

可以证明,上述定义中的两个等式互为充分必要条件,在证明 L 为分配格时,只需证明其中的一个等式即可.

例 14.33　指出图 14.6 中哪些格是分配格? 如果不是分配格,请说明理由.

图 14.6

解　L_1 和 L_2 是分配格,L_3 和 L_4 不是分配格. 在 L_3 中有

在 L_4 中有

称 L_3 为钻石格,L_4 为五角格. 这两个 5 元格在分配格的判别中有着重要的意义.

不加证明,仅通过下面两个定理给出判别分配格的充分必要条件.

定理 14.15　设 L 是格,则 L 是分配格当且仅当 L 不含有与钻石格或五角格同构的子格.

定理 14.16　格 L 是分配格当且仅当 \forall a,b,c \in L 有 a \wedge b=a \wedge c 且 a \vee b=a \vee c \Rightarrow b=c.

例 14.34　判别图 14.7 中的格是否为分配格.

图 14.7

解　L_1 不是分配格,因为它含有与钻石格同构的子格. L_2 和 L_3 不是分配格,因为它们含有与五角格同构的子格.

如果使用定理 14.16,那么在 L_1 中有 d \wedge b=d \wedge c 且 d \vee b=d \vee c,但是 b \neq c. 而在 L_2 中,有 c \wedge e=c \wedge b 且 c \vee e=c \vee b,但是 e \neq b. 在 L_3 中,有 d \wedge c=d \wedge g 且 d \vee c=d \vee g,但是 c \neq g.

解读：判别分配格有两条路:一是看图里是否藏着钻石格或五角格子格,二是找一对 b\neq c 却与同一个 a 有相同的交与并——例 14.34 两种做法都演示了一遍。

定义 14.35　设 L 是格,若存在 a \in L 使得 \forall x \in L 有 a \preccurlyeq x,则称 a 为 L 的全下界;若存在 b \in L 使得 \forall x \in L 有 x \preccurlyeq b,则称 b 为 L 的全上界.

格 L 若存在全下界或全上界,一定是唯一的. 一般将格 L 的全下界记为 0,全上界记为 1.

定义 14.36　设 L 是格,若 L 存在全下界和全上界,则称 L 为有界格,有界格 L 记为 \langle L, \wedge, \vee, 0, 1 \rangle.

不难看出,有限格 L=\{a_1,a_2,\cdots,a_n\} 是有界格,其中 a_1 \wedge a_2 \wedge \cdots \wedge a_n 是 L 的全下界,a_1 \vee a_2 \vee \cdots \vee a_n 是 L 的全上界.

定义 14.37　设 \langle L, \wedge, \vee, 0, 1 \rangle 是有界格,a \in L,若存在 b \in L 使得

成立,则称 b 是 a 的补元.

例 14.35　考虑图 14.6 中的 4 个格. 针对不同的元素,求出所有的补元.

解　L_1 中 a 与 c 互为补元,其中 a 为全下界,c 为全上界,b 没有补元. L_2 中 a 与 d 互为补元,其中 a 为全下界,d 为全上界,b 与 c 也互为补元. L_3 中 a 与 e 互为补元,其中 a 为全下界,e 为全上界,b 的补元是 c 和 d,c 的补元是 b 和 d,d 的补元是 b 和 c. b,c,d 每个元素都有两个补元. L_4 中的 a 与 e 互为补元,其中 a 为全下界,e 为全上界,b 的补元是 c 和 d,c 的补元是 b,d 的补元是 b.

关于补元有以下定理.

定理 14.17　设 \langle L, \wedge, \vee, 0, 1 \rangle 是有界分配格. 若 L 中元素 a 存在补元,则存在唯一的补元.

证明　假设 b,c 是 a 的补元,由于 c 是补元则有 a \vee c=1 和 a \wedge c=0. 又知 b 是 a 的补元,故有 a \vee b=1,a \wedge b=0. 从而得到 a \vee c=a \vee b,a \wedge c=a \wedge b,由于 L 是分配格,根据定理 14.16 有 b=c.

定义 14.38　设 \langle L, \wedge, \vee, 0, 1 \rangle 是有界格,若 L 中所有元素都有补元存在,则称 L 为有补格.

例如,图 14.6 中的 L_2,L_3 和 L_4 是有补格,L_1 不是有补格.

定义 14.39　如果一个格是有补分配格,则称它为布尔格或布尔代数.

在布尔代数中,每个元素存在补元,并且补元是唯一的. 因此可以把求补元的运算看作是布尔代数中的一元运算. 通常将布尔代数标记为 \langle B, \wedge, \vee, ', 0, 1 \rangle,其中 ' 为求补运算.

定理 14.18　设 \langle B, \wedge, \vee, ', 0, 1 \rangle 是布尔代数,则

(1) \forall a \in B,(a')'=a.

(2) \forall a,b \in B,(a \wedge b)'=a' \vee b',(a \vee b)'=a' \wedge b'(德摩根律).

证明　(1) (a')' 是 a' 的补元. a 也是 a' 的补元. 由补元的唯一性得 (a')'=a.

(2) 对任意 a,b \in B 有

所以 a' \vee b' 是 a \wedge b 的补元,根据补元的唯一性有 (a \wedge b)'=a' \vee b'. 同理可证 (a \vee b)'=a' \wedge b'.

德摩根律可以推广到有限个元素,即 (a_1 \wedge a_2 \wedge \cdots \wedge a_n)'=a_1' \vee a_2' \vee \cdots \vee a_n'.

也可以通过规定代数系统的性质来定义布尔代数.

定义 14.40　设 \langle B, *, \circ \rangle 是代数系统,* 和 \circ 是二元运算. 若 * 和 \circ 运算满足:

(1) 交换律,即 \forall a,b \in B 有

(2) 分配律,即 \forall a,b,c \in B 有

(3) 同一律,即存在 0,1 \in B,使得 \forall a \in B 有

(4) 补元律,即 \forall a \in B,存在 a' \in B 使得

则称 \langle B, *, \circ \rangle 是一个布尔代数.

可以证明,布尔代数的两种定义是等价的.

下面考虑布尔代数之间的同态与同构问题.

定义 14.41　设 \langle B_1, \wedge, \vee, ', 0_1, 1_1 \rangle 和 \langle B_2, \cap, \cup, -, \theta, E \rangle 是两个布尔代数. 这里的 \cap,\cup,- 泛指布尔代数 B_2 中的求最大下界,最小上界和补元的运算.\theta 和 E 分别是 B_2 的全下界和全上界. f: B_1 \to B_2. 如果对于任意的 a,b \in B_1 有

成立,则称 f 是布尔代数 B_1 到 B_2 的同态映射.

有关布尔代数同构的一个重要结果涉及有限布尔代数的结构. 可以证明任何有限布尔代数都与某个幂集格同构. 因此,任何有限布尔代数的元素个数都是 2^n,其中 n 是某个自然数. 图 14.8 给出了 1 元,2 元,4 元和 8 元的布尔代数.

图 14.8

解读：布尔代数的两条定义路径与格一致——一条从偏序（有补分配格）出发,一条从运算性质（交换、分配、同一、补元）出发,定理保证二者等价。