7.1-7.2 二元运算、幺半群与群

第 7 章开始转换视角。

集合论让我们用函数、关系和基数比较集合。但很多数学对象之所以有趣，不 只是因为它们包含哪些元素，而是因为那些元素上还带有额外结构。

例如，只看基数时，集合 {5, dog} 和 $\{0,1\}$ 都只有两个元素。但 $\{0,1\}$ 可以配上熟悉的加法和乘法规则；相反，5 + dog 在未指定额外结 构之前没有明确意义。

本章的目标，就是把这些额外结构说清楚。

带结构的集合

许多基本例子都符合这个模式：自然数带有加法与乘法，平面带有向量加法， 置换带有合成。

共同模式是：

1. 先有一个集合；
2. 在集合上指定某些运算、关系、函数或特殊元素；
3. 写下这些额外数据要满足的公理；
4. 只由公理推出定理。

这是现代数学的一个基本习惯。与其在每个例子中重复证明同一类事实，不如 先定义一种结构，再证明所有具有该结构的例子都必须满足什么。

二元运算

定义

二元运算

设 $X$ 是集合。$X$ 上的一个 二元运算 是一个函数

$$*:X\times X\to X.$$

对 $a,b\in X$，通常写 $a*b$，而不是 $*(a,b)$。

这个定义有两个重点。

第一，运算从 $X$ 中取两个输入。第二，输出仍然必须属于 $X$。第二点常 被称为封闭性；在这门课的写法中，它已经包含在函数类型 $X\times X\to X$ 里。

常见错误

一条公式不会自动成为每个集合上的二元运算

减法是 $Z$ 上的二元运算，因为 $a-b\in Z$ 对所有 $a,b\in Z$ 都成立。 但若要求结果仍留在 $N$ 中，减法就不是 $N$ 上的二元运算，因为 $2-5$ 不 是自然数。

Boolean integers

定义

$$B=\{0,1\}.$$

在这个集合上，加法规则为

$$0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0,$$

乘法规则为

$$0\cdot 0=0,\qquad 0\cdot 1=0,\qquad 1\cdot 0=0,\qquad 1\cdot 1=1.$$

定义

Boolean integers

Boolean integers 是三元组

$$(B,+,\cdot),$$

其中 $B=\{0,1\}$，而 $+$ 与 $\cdot$ 是上面显示的两个二元运算。

重点不在名称，而在于：即使集合很小，只要指定运算，也可以有非平凡结构。

例题

在 $B$ 中解 $x+y=0$

一个有用练习是证明

$$\forall x\in B,\ \exists y\in B\ (x+y=0).$$

只需检查 $x$ 的两个可能值。

若 $x=0$，取 $y=0$，因为 $0+0=0$。

若 $x=1$，取 $y=1$，因为 $1+1=0$。

所以在这个加法规则下，$B$ 的每个元素都有加法逆元。

更多二元运算例子

常见例子包括：

• $+$ 和 $\times$ 是 $N$ 上的二元运算；
• $+$ 和 $\times$ 是 $Z$ 上的二元运算；
• 对任意集合 $X$，函数集合 $X^X$ 上的合成是二元运算。

最后一个例子值得仔细读。若 $f:X\to X$ 且 $g:X\to X$，则

$$g\circ f:X\to X.$$

所以合成把 $X^X$ 的两个元素合并，并得到 $X^X$ 的另一个元素。

例题

合成作为二元运算

设 $X=\{a,b\}$。$X^X$ 的元素是所有从 $X$ 到自身的函数。

若 $f,g\in X^X$，则 $g\circ f$ 仍然是 $X$ 到自身的函数。因此合成定义了

$$\circ:X^X\times X^X\to X^X.$$

这里被合并的元素是函数，不是 $X$ 本身的元素。

幺半群

第 7 章首先研究的结构是 monoid。

定义

幺半群

一个 幺半群 $(M,*)$ 是一个集合 $M$，连同一个二元运算

$$*:M\times M\to M$$

使得：

• 对所有 $a,b,c\in M$，

  $$(a*b)*c=a*(b*c)$$

  （结合律）；

• 存在 $e\in M$，使得对所有 $a\in M$，

  $$a*e=e*a=a$$

  （单位元存在）。

结合律说明三个元素连乘时括号位置不影响结果。单位元则是一个从左边或右 边合并都不改变元素的元素。

标准例子包括：

• $(N,+)$ 是幺半群，单位元为 $0$；
• $(N,\times)$ 是幺半群，单位元为 $1$；
• $(Z,+)$ 是幺半群，单位元为 $0$；
• $(Z,\times)$ 是幺半群，单位元为 $1$；
• 对任意集合 $X$，$X^X$ 在合成下是幺半群，单位元为 $id_X$；
• $(B,+)$ 是幺半群；
• $(B,\cdot)$ 是幺半群。

例题

检查 $(N,+)$ 是幺半群

$+$ 是 $N$ 上的二元运算。

结合律成立：

$$(a+b)+c=a+(b+c)$$

对所有自然数 $a,b,c$ 成立。

单位元是 $0$，因为

$$a+0=0+a=a.$$

所以 $(N,+)$ 是幺半群。

例题

检查函数合成幺半群

设 $X$ 是任意集合。$X^X$ 的元素是函数 $X\to X$。

合成满足结合律：

$$(h\circ g)\circ f=h\circ(g\circ f).$$

恒等函数 $id_X$ 满足

$$f\circ id_X=f,\qquad id_X\circ f=f.$$

所以 $X^X$ 在合成下是幺半群。

不是幺半群的例子

也要看一些失败例子。

例题

$(Z^+,+)$ 不是幺半群

若 $Z^+$ 表示正整数，则加法封闭且满足结合律。但 $Z^+$ 里没有加法单位 元。

加法单位元必须是 $0$，因为 $a+0=a$。但 $0\notin Z^+$。所以 $(Z^+,+)$ 不是幺半群。

例题

$(Z,-)$ 不是幺半群

减法是 $Z$ 上的二元运算，但不满足结合律。例如

$$(5-3)-1=1,$$

而

$$5-(3-1)=3.$$

结果不同，所以结合律失败，$(Z,-)$ 不是幺半群。

常见错误

有单位元仍然不够

一个运算可能看起来有单位元，但若不满足结合律，仍然不是幺半群。结合律 和单位元是两个独立要求。

单位元唯一

定理

单位元唯一性

一个幺半群恰好只有一个单位元。

证明

假设 $e$ 和 $e'$ 都是单位元。因为 $e$ 是单位元，

$$e*e'=e'.$$

因为 $e'$ 是单位元，

$$e*e'=e.$$

所以

$$e=e*e'=e',$$

故单位元唯一。

这个证明很短，原因是单位元律可以左右两边使用。两个候选单位元必须互相 不改变对方，因而被迫相等。

群

幺半群很有用，但条件较弱。群额外要求每个元素都可以被“复原”。

定义

群

一个 群 是一个集合 $G$，连同一个元素 $e\in G$ 和一个二元运算

$$(a,b)\longmapsto a\cdot b$$

使得：

• 对所有 $a\in G$，

  $$e\cdot a=a=a\cdot e;$$

• 对所有 $a,b,c\in G$，

  $$(a\cdot b)\cdot c=a\cdot(b\cdot c);$$

• 对每个 $a\in G$，存在逆元 $a^{-1}\in G$，使得

  $$a\cdot a^{-1}=e \qquad\text{且}\qquad a^{-1}\cdot a=e.$$

群的自然动机之一是形式化对称性。对称操作应该可以合成、有一个什么都 不做的操作，并且可以反向复原。

在这个标准读法下，每个群在忘记逆元公理之后都是幺半群。群更强，不是因 为它有另一套结合律或单位元，而是因为每个元素都有逆元。

常见错误

群不是任意带二元运算的集合

运算必须满足结合律，必须有双边单位元，而且每个元素都必须有逆元。任何 一条失败，都不是群。

群的例子

基本例子包括：

• $(Z,+)$；
• $(Q,+)$；
• $(Q^+,\cdot)$，其中 $Q^+$ 表示正有理数。

例题

为什么 $(Z,+)$ 是群

单位元是 $0$。

对每个整数 $a$，逆元是 $-a$，因为

$$a+(-a)=0=(-a)+a.$$

加法满足结合律，所以 $(Z,+)$ 是群。

例题

为什么 $(Q^+,\cdot)$ 是群

单位元是 $1$。

对每个正有理数 $q$，逆元是 $1/q$，它仍然是正有理数，且

$$q\cdot \frac1q=1=\frac1q\cdot q.$$

乘法满足结合律，所以 $(Q^+,\cdot)$ 是群。

常见错误

$(Z,\times)$ 是幺半群，但不是群

$Z$ 上乘法的单位元是 $1$，且乘法满足结合律。但大多数整数在 $Z$ 中没有 乘法逆元。例如不存在整数 $b$ 使得 $2b=1$。

逆元唯一

定理

逆元唯一性

对每个 $a\in G$，逆元 $a^\{-1\}$ 是唯一的。

证明

假设 $b$ 和 $c$ 都是 $a$ 的逆元。则

$$a*b=e,\qquad b*a=e,$$

且

$$a*c=e,\qquad c*a=e.$$

利用单位元与结合律，

$$b=b*e=b*(a*c)=(b*a)*c=e*c=c.$$

所以 $b=c$。

这个证明说明了为什么逆元记号是合理的：只要逆元存在，它就是唯一的，所 以 $a^\{-1\}$ 不会有歧义。

袜鞋性质

乘积逆元公式常被称为 socks-shoes property：要复原两个连续 操作，先复原第二个，再复原第一个。

定理

袜鞋性质

对群中元素 $a,b$，

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

证明

计算：

$$(a*b)*(b^{-1}*a^{-1}) =a*(b*b^{-1})*a^{-1} =a*e*a^{-1} =a*a^{-1} =e.$$

由逆元唯一性，$a*b$ 的逆元必为 $b^\{-1\}*a^\{-1\}$。

顺序反转是必要的。在非交换群中，$a^\{-1\}*b^\{-1\}$ 未必能复原 $a*b$。

消去律

定理

消去律

在群中：

• 若 $a*b=a*c$，则 $b=c$；
• 若 $b*a=c*a$，则 $b=c$。

左消去证明

假设

$$a*b=a*c.$$

左乘 $a^\{-1\}$：

$$a^{-1}*(a*b)=a^{-1}*(a*c).$$

由结合律，

$$(a^{-1}*a)*b=(a^{-1}*a)*c.$$

因为 $a^\{-1\}*a=e$，得到

$$e*b=e*c,$$

所以 $b=c$。

右消去的证明类似，只是改为右乘 $a^\{-1\}$。

单侧逆元与非交换性

对函数而言，$g\circ f=id$ 的左逆推出 $f$ 单射，$f\circ h=id$ 的右逆 推出 $f$ 满射；两者同时存在才得到逆函数。在一般幺半群中，单侧逆元 不应自动视为双侧逆元，所以必须记录等式在哪一侧成立。

定理

两侧等式足以识别逆元

若幺半群中 $b*a=e=a*c$，则 $b=b*e=b*(a*c)=(b*a)*c=e*c=c$。在群中，每个元素都有唯一逆元， 并且左、右消去分别通过在相应一侧乘以逆元得到。

定理

幺半群中处处有右逆元就成为群

设 $M$ 是幺半群。若每个 $a\in M$ 都有右逆元，取 $b,c\in M$ 使 $a*b=e$ 且 $b*c=e$。结合律给出

$$a=a*(b*c)=(a*b)*c=e*c=c$$

所以 $b*a=b*c=e$。每个右逆元也是左逆元，$M$ 因而是群；另一侧的恒等式 是由结合律推导出来的。

例题

群 $GL(2,R)$ 非交换

$GL(2,R)$ 是所有行列式非零的实 $2\times2$ 矩阵，在矩阵乘法下成群。取

$$A=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad B=\begin{pmatrix}1&0\\1&1\end{pmatrix}$$

两者行列式都是 $1$，但 $AB=\begin{pmatrix}2&1\\1&1\end{pmatrix}$， 而 $BA=\begin{pmatrix}1&1\\1&2\end{pmatrix}$，所以 $AB\ne BA$。 结合律不推出交换律；单位元是单位矩阵，每个矩阵仍有逆元。

常见错误

Boolean 乘法不是群

Boolean 乘法幺半群的单位元是 $1$，但 $0$ 没有逆元，因为 $0b=0$ 永远 不等于 $1$。因此 $(B,\cdot)$ 不是群。

同态与同构

定义

群同态

若 $(G,*)$、$(H,\star)$ 是群，$\varphi:G\to H$ 是同态，当且仅当 $\varphi(a*b)=\varphi(a)\star\varphi(b)$ 对所有 $a,b$ 成立。

定理

同态保持单位元和逆元

令 $u=\varphi(e_G)$。由 $u=u\star u$，在左侧乘以 $u^\{-1\}$ 得 $e_H=u$，所以 $\varphi(e_G)=e_H$。又有两条等式 $\varphi(a)\star\varphi(a^{-1})=\varphi(a*a^{-1})=e_H$ 与 $\varphi(a^{-1})\star\varphi(a)=\varphi(a^{-1}*a)=e_H$；因此 $\varphi(a^{-1})$ 是 $\varphi(a)$ 的双侧逆元，唯一性完成证明。

定义

同构

同构是双射群同态。若存在同构，写作 $G\cong H$；重新标记元素后，两群 具有相同的运算结构。

对称群与 $S_2\cong Z_2$

$S_2$ 的元素是恒等置换 $id$ 与换位 $\tau=(1\ 2)$，并且 $\tau\circ\tau=id$。

例题

$S_2$ 的合成表

$$\begin{array}{c|cc} \circ&id&\tau\\\hline id&id&\tau\\ \tau&\tau&id \end{array}$$

令 $\varphi(id)=0$、$\varphi(\tau)=1$。合成表说明 $\varphi(\sigma\circ\rho)=\varphi(\sigma)+\varphi(\rho)\pmod2$， 而 $\varphi$ 是双射，所以 $S_2\cong Z_2$。

对群 $G$ 及 $g,h\in G$，定义 $g\sim h$ 当且仅当存在 $k\in G$ 使 $g=khk^\{-1\}$，称为共轭关系。由 $g=ege^\{-1\}$ 得自反性。若 $g=khk^\{-1\}$，则 $h=k^\{-1\}gk$，故有对称性。若还有 $h=\ell j\ell^{-1}$，则 $g=(k\ell)j(k\ell)^{-1}$，故有传递性。 因此共轭是 $G$ 上的等价关系。

二面体群 $D_8$

把正方形顶点标为 $1=(1,1)$、$2=(-1,1)$、$3=(-1,-1)$、$4=(1,-1)$。 令 $r=(1\ 2\ 3\ 4)$ 是四分之一转动，$s=(2\ 4)$ 是关于对角线 $y=x$ 的反射。置换合成约定最右边的置换先作用。八个对称为

$$e, r, r^2, r^3, s, rs, r^2s, r^3s$$

对 $(1,2,3,4)$ 的作用如下，因而几何描述也可以直接核对：

它们满足 $r^4=e$、$s^2=e$ 以及反射关系 $srs=r^\{-1\}$。因此可用 $sr=r^\{-1\}s$ 把含有 $r$、$s$ 的乘积化成列出的形式。

例题

$D_8$ 的共轭类

由 $srs=r^\{-1\}$，转动 $r$ 与 $r^3$ 共轭。$r^2$ 在转动和反射下都保持不变， 所以单独成类。反射按指数奇偶分成两族，完整的共轭类是

$$\{e\},\qquad \{r^2\},\qquad \{r,r^3\},\qquad \{s,r^2s\},\qquad \{rs,r^3s\}$$

例如 $rsr^\{-1\}=r^2s$，$r(rs)r^\{-1\}=r^3s$，而用 $s$ 共轭会反转转动指数。 用生成元 $r$ 或 $s$ 共轭，都保持每个所列集合不变。每个群元素都是这些 生成元的乘积，所以任何共轭都不能把元素移到另一个所列集合。上面的计算又把 每个二元素集合中的两个元素连接起来，因此这些集合恰为全部共轭类。

涉及 $S_2$ 与 $S_3$ 的两个同态

定义 $f:S_2\to S_3$，让 $S_2$ 的置换固定第三个元素： $f(id)=id$、$f((1\ 2))=(1\ 2)$。合成规则没有改变，因此 $f$ 是同态。

反向映射可直接由置换计算得到。令 $c=(1\ 2\ 3)$、$t=(1\ 2)$。 直接合成可核对 $c^3=t^2=e$ 及 $tct=c^\{-1\}$。六个不同置换是 $e,c,c^2,t,ct,c^2t$；后三个依次为 $(1\ 2),(1\ 3),(2\ 3)$。 所以每个元素唯一写成 $c^i t^\varepsilon$，其中 $i\in\{0,1,2\}$、 $\varepsilon\in\{0,1\}$。由 $tc=c^\{-1\}t$，

$$(c^i t^\varepsilon)(c^j t^\delta) =c^{i+(-1)^\varepsilon j}t^{\varepsilon+\delta}.$$

这里 $c$ 的指数模三化简，$t$ 的指数模二化简。定义 $g(c^i t^\varepsilon)=\tau^\varepsilon\in S_2$。乘积中 $t$ 的指数模二相加， 与 $\tau$ 的指数规则相同，因此 $g(\sigma\rho)=g(\sigma)g(\rho)$。 这就是奇偶性同态；映到单位元的元素恰为 $e,c,c^2$，通常把这个集合记作 $A_3$。

互动检查运算律

下面的 checker 是定义的辅助工具：可用来测试小型运算表的封闭性、结合 律、单位元与逆元行为。真正的数学内容仍然是上面的公理。

图示。monoid 与 group 的分别不是名称，而是除结合律外，单位元与逆元公理是否成立。

快速检查

思考检查

一条规则 $*$ 要成为集合 $X$ 上的二元运算，必须满足什么输入与输出要求？

用函数类型回答。

解答 · 答案

它必须是一个函数 $*:X\times X\to X$。也就是说，它取两个 $X$ 的元素作 为输入，并输出一个仍在 $X$ 中的元素。

思考检查

为什么 $(Z,-)$ 不是幺半群？

指出失败的公理，并给一个具体计算。

解答 · 答案

减法不满足结合律。例如

$$(5-3)-1=1$$

但

$$5-(3-1)=3.$$

两者不同，所以 $(Z,-)$ 不是幺半群。

思考检查

为什么 $(Z,\times)$ 不是群？

集中看逆元。

解答 · 答案

$Z$ 上乘法满足结合律并有单位元 $1$，但不是每个整数都有乘法逆元。例如 不存在整数 $b$ 使 $2b=1$。

思考检查

在群中，$a*b$ 的逆元是什么？

留意顺序。

解答 · 答案

逆元是

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

顺序会反转。

练习

练习 1

直接证明 $(B,+)$ 是幺半群，其中 $+$ 是上面定义的 Boolean 加法。

解答 · 提示

检查结合律并指出单位元。

解答 · 引导解答

单位元是 $0$，因为 $0+0=0$、$0+1=1$、$1+0=1$，所以对两个 $x\in B$ 都有 $x+0=0+x=x$。

结合律可由有限情况 $x,y,z\in\{0,1\}$ 直接检查。Boolean 加法就是模 $2$ 加法，所以 $(x+y)+z$ 与 $x+(y+z)$ 都记录 $x,y,z$ 中 $1$ 的个数奇偶性， 因此相等。

练习 2

集合 X 上的二元运算有左单位元 e 和右单位元 f。证明 e=f，且这个共同元素是双侧单位元。需要结合律吗？

解答 · 提示

分别使用左右单位元的性质计算 e*f。

解答 · 参考解答

因为 e 是左单位元，$e*f=f$；因为 f 是右单位元，$e*f=e$，所以 $e=f$。这个共同元素同时具有左右单位元性质。论证没有使用结合律：只计算一个乘积，没有改变括号。

练习 3

设 a 是幺半群中的元素，且有左逆 h，即 $h*a=e$。证明 $a*b=a*c$ 蕴含 $b=c$，并说明为什么不需要右逆。

解答 · 提示

在等式两边左乘 h，保持因子的次序。

解答 · 参考解答

由 $a*b=a*c$，两边左乘 h，再用结合律得 $(h*a)*b=(h*a)*c$。因为 $h*a=e$，这化为 $e*b=e*c$，所以 $b=c$。这里只使用 $h*a=e$，没有使用关于 $a*h$ 的等式。

相关笔记

可先读 2.2 函数与关系 和 6.4-6.7 区间、Cantor 集、稠密性与良序。 这一节也会用到 1.2 量词与否定 以及 3.4 有理数与良定义运算 中的证明习惯。