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

第 7 章开始转换视角。

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

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

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

带结构的集合

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

共同模式是：

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

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

二元运算

定义

二元运算

设 $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$ 的每个元素都有加法逆元。

幺半群

第 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$
（单位元存在）。

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

notes 列出几个例子：

$(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$ 在合成下是幺半群。

不是幺半群的例子

notes 也列出失败例子。

例题

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

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

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

例题

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

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

(5-3)-1=1,

而

5-(3-1)=3.

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

常见错误

有单位元仍然不够

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

单位元唯一

定理

单位元唯一性

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

证明

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

群

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

定义

群

一个群是一个集合 $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}$ 是唯一的。

证明

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

袜鞋性质

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

定理

袜鞋性质

对群中元素 a,b，

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

证明

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

消去律

定理

消去律

在群中：

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

证明

左消去证明

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

互动检查运算律

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

比较 monoid 与 group 的公理表

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

边读边试

检查 monoid 与 group 公理

这个检查器按 monoid 与 group 所需的精确公理比较二元运算。

这是一个群。

结合律

是

(a+b)+c = a+(b+c)。

单位元

是

0 是单位元。

逆元

是

a 的逆元是 -a。

快速检查

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

用函数类型回答。

解答

答案

快速检查

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

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

解答

答案

快速检查

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

集中看逆元。

解答

答案

快速检查

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

留意顺序。

解答

答案

练习

快速检查

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

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

解答

引导解答

快速检查

证明幺半群的单位元唯一。

使用两个可能的单位元 e 与 e'。

解答

引导解答

快速检查

证明群中的左消去律：若 $ab=ac$ ，则 $b=c$ 。

使用 a 的逆元。

解答

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

MATH1090：集合论

带结构的集合

二元运算

二元运算

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

Boolean integers

Boolean integers

在 BBB 中解 x+y=0x+y=0x+y=0

更多二元运算例子

合成作为二元运算

幺半群

幺半群

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

检查函数合成幺半群

不是幺半群的例子

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

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

有单位元仍然不够

单位元唯一

单位元唯一性

证明

群

群

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

群的例子

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

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

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

逆元唯一

逆元唯一性

证明

袜鞋性质

袜鞋性质

证明

消去律

消去律

左消去证明

互动检查运算律

检查 monoid 与 group 公理

快速检查

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

答案

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

答案

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

答案

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

答案

练习

直接证明 (B,+)(B,+)(B,+) 是幺半群，其中 +++ 是 notes 中的 Boolean 加法。

引导解答

证明幺半群的单位元唯一。

引导解答

证明群中的左消去律：若 a∗b=a∗ca*b=a*ca∗b=a∗c，则 b=cb=cb=c。

引导解答

相关笔记

先备知识

本单元重点词汇

本系列更多笔记

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

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

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

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

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

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

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

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

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

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

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

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

证明群中的左消去律：若 $ab=ac$ ，则 $b=c$ 。