集合论让我们用函数、关系和基数比较集合。但很多数学对象之所以有趣，不只是因为它们包含哪些元素，而是因为那些元素上还带有额外结构。
例如，只看基数时，集合 {5, dog} 和 {0,1} 都只有两个元素。但
{0,1} 可以配上模 2 的加法和乘法规则；相反，5 + dog 在未指定额外结构之前没有明确意义。
带结构的集合
许多基本例子都符合这个模式：自然数带有加法与乘法，平面带有向量加法，置换带有合成。
共同模式是：
- 先有一个集合；
- 在集合上指定某些运算、关系、函数或特殊元素；
- 写下这些额外数据要满足的公理；
- 只由公理推出定理。
这是现代数学的一个基本习惯。与其在每个例子中重复证明同一类事实，不如先定义一种结构，再证明所有具有该结构的例子都必须满足什么。
二元运算
设 X 是集合。X 上的一个 二元运算 是一个函数
∗:X×X→X.对 a,b∈X，通常写 a∗b，而不是 ∗(a,b)。
这个定义有两个重点。
第一，运算从 X 中取两个输入。第二，输出仍然必须属于 X。第二点常被称为封闭性；在这门课的写法中，它已经包含在函数类型
X×X→X 里。
常见错误
（一条公式不会自动成为每个集合上的二元运算）
减法是 Z 上的二元运算，因为 a−b∈Z 对所有 a,b∈Z 都成立。但若要求结果仍留在 N 中，减法就不是 N 上的二元运算，因为 2−5 不是自然数。
Boolean integers
定义
B={0,1}.
在这个集合上，加法规则为
0+0=0,0+1=1,1+0=1,1+1=0,
乘法规则为
0⋅0=0,0⋅1=0,1⋅0=0,1⋅1=1.
定义 7.1.2
（Boolean integers）
Boolean integers 是三元组
(B,+,⋅),其中 B={0,1}，而 + 与 ⋅ 是上面显示的两个二元运算。
同一个二元素集合可以承载不同的运算，各种运算满足的规律需要分别检查。
例题 7.1.3
（在 B 中解 x+y=0）
每个 x∈B 都能与某个元素相加而得到零：
∀x∈B, ∃y∈B (x+y=0).只需检查 x 的两个可能值。
若 x=0，取 y=0，因为 0+0=0。
若 x=1，取 y=1，因为 1+1=0。
所以在这个加法规则下，B 的每个元素都有加法逆元。
更多二元运算例子
常见例子包括：
- + 和 × 是 N 上的二元运算；
- + 和 × 是 Z 上的二元运算；
- 对任意集合 X，函数集合 XX 上的合成是二元运算。
若 f:X→X 且 g:X→X，则合成 g∘f 仍将 X 映到 X。因此合成定义了二元运算
∘:XX×XX→XX.
设 X={a,b}，其中 a=b。定义 f(a)=f(b)=a，并令 g 交换这两个元素，即 g(a)=b、g(b)=a。于是
(g∘f)(a)=(g∘f)(b)=b,(f∘g)(a)=(f∘g)(b)=a.两个合成都属于 XX，却是不同的函数。因此合成在 XX 上封闭，但不满足交换律。这里参与运算的元素是函数，不是 X 本身的元素。
幺半群
函数合成有两条不依赖具体集合 X 的规律：改变连续合成的括号位置不改变结果，与 idX 合成也不改变原函数。幺半群把这两条规律抽象为公理，使同一论证可以用于加法、乘法和函数合成。
一个 幺半群 (M,∗) 是一个集合 M，连同一个二元运算
∗:M×M→M使得：
-
对所有 a,b,c∈M，
(a∗b)∗c=a∗(b∗c)
（结合律）；
-
存在 e∈M，使得对所有 a∈M，
a∗e=e∗a=a
（单位元存在）。
结合律说明三个元素连乘时括号位置不影响结果。单位元则是一个从左边或右边合并都不改变元素的元素。
标准例子包括：
- (N,+) 是幺半群，单位元为 0；
- (N,×) 是幺半群，单位元为 1；
- (Z,+) 是幺半群，单位元为 0；
- (Z,×) 是幺半群，单位元为 1；
- 对任意集合 X，XX 在合成下是幺半群，单位元为 idX；
- (B,+) 是幺半群；
- (B,⋅) 是幺半群。
例题 7.1.6
（检查 (N,+) 是幺半群）
+ 是 N 上的二元运算。
结合律成立：
(a+b)+c=a+(b+c)对所有自然数 a,b,c 成立。
单位元是 0，因为
a+0=0+a=a.所以 (N,+) 是幺半群。
设 X 是任意集合。XX 的元素是函数 X→X。
合成满足结合律：
(h∘g)∘f=h∘(g∘f).恒等函数 idX 满足
f∘idX=f,idX∘f=f.所以 XX 在合成下是幺半群。
不是幺半群的例子
例题 7.1.8
（(Z+,+) 不是幺半群）
若 Z+ 表示正整数，则加法封闭且满足结合律。但 Z+ 里没有加法单位元。
加法单位元必须是 0，因为 a+0=a。但 0∈/Z+。所以
(Z+,+) 不是幺半群。
例题 7.1.9
（(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′,
故单位元唯一。
这个证明很短，原因是单位元律可以左右两边使用。两个候选单位元必须互相不改变对方，因而被迫相等。
群
幺半群允许运算连续进行，却不要求每个运算都可逆。在前面的二元素例子中，
f(a)=f(b)=a。不可能有函数 h 满足 h∘f=idX，因为这个等式要求同一个值 h(a) 同时等于 a 和 b。相反，交换两个元素的 g 满足
g∘g=idX，再次施行 g 就能恢复原状。
若只保留双射 X→X，这个障碍便消失了：双射的合成仍是双射，idX
是双射，每个双射也都有从 X 到自身的逆函数。这些可逆运算构成了群的一个基本模型。几何对称也具有这些性质：可以合成，有恒等对称，而且可以逆转。群公理把这些规律抽象出来，不再要求元素本身必须是函数。
一个 群 是一个集合 G，连同一个元素 e∈G 和一个二元运算
(a,b)⟼a⋅b使得：
-
对所有 a∈G，
e⋅a=a=a⋅e;
-
对所有 a,b,c∈G，
(a⋅b)⋅c=a⋅(b⋅c);
-
对每个 a∈G，存在逆元 a−1∈G，使得
a⋅a−1=e且a−1⋅a=e.
在这个标准读法下，每个群在忘记逆元公理之后都是幺半群。群更强，不是因为它有另一套结合律或单位元，而是因为每个元素都有逆元。
运算必须满足结合律，必须有双边单位元，而且每个元素都必须有逆元。任何一条失败，都不是群。
群的例子
基本例子包括：
- (Z,+)；
- (Q,+)；
- (Q+,⋅)，其中 Q+ 表示正有理数。
例题 7.1.12
（为什么 (Z,+) 是群）
单位元是 0。
对每个整数 a，逆元是 −a，因为
a+(−a)=0=(−a)+a.加法满足结合律，所以 (Z,+) 是群。
例题 7.1.13
（为什么 (Q+,⋅) 是群）
单位元是 1。
对每个正有理数 q，逆元是 1/q，它仍然是正有理数，且
q⋅q1=1=q1⋅q.乘法满足结合律，所以 (Q+,⋅) 是群。
常见错误
（(Z,×) 是幺半群，但不是群）
Z 上乘法的单位元是 1，且乘法满足结合律。但大多数整数在 Z 中没有乘法逆元。例如不存在整数 b 使得 2b=1。
逆元唯一
对每个 a∈G，逆元 a−1 是唯一的。
证明
假设 b 和 c 都是 a 的逆元。则
a∗b=e,b∗a=e,
且
a∗c=e,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.
反向的乘积也等于单位元：
(b−1∗a−1)∗(a∗b)=b−1∗(a−1∗a)∗b=b−1∗e∗b=b−1∗b=e.
所以 b−1∗a−1 是 a∗b 的双侧逆元，再由逆元唯一性得到所述公式。
顺序反转是必要的。在非交换群中，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∘f=id 的左逆推出 f 单射，f∘h=id 的右逆推出 f 满射；两者同时存在才得到逆函数。在一般幺半群中，单侧逆元不应自动视为双侧逆元，所以必须记录等式在哪一侧成立。
若幺半群中 b∗a=e=a∗c，则
b=b∗e=b∗(a∗c)=(b∗a)∗c=e∗c=c。在群中，每个元素都有唯一逆元，并且左、右消去分别通过在相应一侧乘以逆元得到。
定理 7.1.18
（幺半群中处处有右逆元就成为群）
设 M 是幺半群。若每个 a∈M 都有右逆元，取 b,c∈M 使
a∗b=e 且 b∗c=e。结合律给出
a=a∗(b∗c)=(a∗b)∗c=e∗c=c所以 b∗a=b∗c=e。每个右逆元也是左逆元，M 因而是群；另一侧的恒等式是由结合律推导出来的。
例题 7.1.19
（群 GL(2,R) 非交换）
GL(2,R) 是所有行列式非零的实 2×2 矩阵，在矩阵乘法下成群。取
A=(1011),B=(1101)两者行列式都是 1，但 AB=(2111)，而 BA=(1112)，所以 AB=BA。结合律不推出交换律；单位元是单位矩阵，每个矩阵仍有逆元。
Boolean 乘法幺半群的单位元是 1，但 0 没有逆元，因为 0b=0 永远不等于 1。因此 (B,⋅) 不是群。
同态与同构
双射可以比较两个集合的大小，却未必保持它们的运算。比较群时，映射还需要尊重乘法：先相乘再映射，应当与先分别映射再在目标群中相乘得到相同结果。这个要求使一个群中的代数计算可以传到另一个群中。
若 (G,∗)、(H,⋆) 是群，φ:G→H 是同态，当且仅当
φ(a∗b)=φ(a)⋆φ(b) 对所有 a,b∈G 成立。同态保持运算，但不一定是单射或满射。
令 u=φ(eG)。由 u=u⋆u，在左侧乘以 u−1 得
eH=u，所以 φ(eG)=eH。又有两条等式
φ(a)⋆φ(a−1)=φ(a∗a−1)=eH 与
φ(a−1)⋆φ(a)=φ(a−1∗a)=eH；因此
φ(a−1) 是 φ(a) 的双侧逆元，唯一性完成证明。
若同态同时是双射，它既不把不同元素合并，也不遗漏目标群中的元素。这种可逆的重新标记保持每个乘积，因而两群具有相同的代数结构。
同构是双射群同态。若存在同构，写作 G≅H；重新标记元素后，两群具有相同的运算结构。
对称群与 S2≅Z2
对于有限集合 X，对称群 SX 是所有双射 X→X 在合成下组成的群，也就是前面讨论的可逆自映射。若 X={1,…,n}，则记作 Sn。循环记号 (a1 a2 ⋯ ak) 将每个列出的元素映到下一个，将 ak
映到 a1，并固定所有未列出的元素。
S2 的元素是恒等置换 id 与换位 τ=(1 2)，并且
τ∘τ=id。以 Z2 表示前面定义的 Boolean 加法群 (B,+)。它的加法表与 S2 的合成表具有相同形式：把 id 改记为 0，把 τ
改记为 1，便能保持运算结果。
∘idτididτττid令 φ(id)=0、φ(τ)=1。合成表说明
φ(σ∘ρ)=φ(σ)+φ(ρ)(mod2)，而 φ 是双射，所以 S2≅Z2。
共轭：重新标记后的同一运算
对于置换，改变元素的标记也会改变运算的表示。若 k 把旧标记映到新标记，则运算 h 在新标记下表示为 k∘h∘k−1：先还原为旧标记，施行 h，再恢复新标记。把合成换成群的乘法，这个表达式在任意群中都有意义。
对群 G 及 g,h∈G，定义 g∼h 当且仅当存在 k∈G
使 g=khk−1，称为共轭关系。由 g=ege−1 得自反性。若
g=khk−1，则 h=k−1gk，故有对称性。若还有
h=ℓjℓ−1，则 g=(kℓ)j(kℓ)−1，故有传递性。因此共轭是 G 上的等价关系。它的等价类称为共轭类，这些类构成群的一个划分。
二面体群 D8
在正方形的对称群中，共轭只允许用正方形本身的对称来改变顶点标记。共轭类把沿对角线的反射与沿对边中点连线的反射区分开来，尽管两者都使正方形的定向反转。
把正方形顶点标为 1=(1,1)、2=(−1,1)、3=(−1,−1)、4=(1,−1)。令 r=(1 2 3 4) 是四分之一转动，s=(2 4) 是关于对角线
y=x 的反射。置换合成约定最右边的置换先作用。八个对称为
e,r,r2,r3,s,rs,r2s,r3s
对 (1,2,3,4) 的作用如下，因而几何描述也可以直接核对：
它们满足 r4=e、s2=e 以及反射关系 srs=r−1。因此可用
sr=r−1s 把含有 r、s 的乘积化成列出的形式。
由 srs=r−1，转动 r 与 r3 共轭。r2 在转动和反射下都保持不变，所以单独成类。反射按指数奇偶分成两族，完整的共轭类是
{e},{r2},{r,r3},{s,r2s},{rs,r3s}例如 rsr−1=r2s，r(rs)r−1=r3s，而用 s 共轭会反转转动指数。用生成元 r 或 s 共轭，都保持每个所列集合不变。每个群元素都是这些生成元的乘积，所以任何共轭都不能把元素移到另一个所列集合。上面的计算又把每个二元素集合中的两个元素连接起来，因此这些集合恰为全部共轭类。
涉及 S2 与 S3 的两个同态
定义 f:S2→S3，让 S2 的置换固定第三个元素：
f(id)=id、f((1 2))=(1 2)。合成规则没有改变，因此 f 是同态。它是单射，却不是满射：任何移动第三个元素的置换都不在其像中。保持运算并不要求覆盖整个目标群。
反向映射可直接由置换计算得到。令 c=(1 2 3)、t=(1 2)。直接合成可核对 c3=t2=e 及 tct=c−1。六个不同置换是
e,c,c2,t,ct,c2t；后三个依次为 (1 2),(1 3),(2 3)。所以每个元素唯一写成 citε，其中 i∈{0,1,2}、
ε∈{0,1}。由 tc=c−1t，
(citε)(cjtδ)=ci+(−1)εjtε+δ.
这里 c 的指数模三化简，t 的指数模二化简。定义
g(citε)=τε∈S2。乘积中 t 的指数模二相加，与 τ 的指数规则相同，因此 g(σρ)=g(σ)g(ρ)。这就是奇偶性同态；映到单位元的元素恰为 e,c,c2，通常把这个集合记作 A3。由 g(e)=id、g(t)=τ 可知它是满射；但 e,c,c2 有相同的像，所以不是单射。这两个例子分别说明，同态的定义不包含单射或满射的要求。
互动检查运算律
下面的工具可以检验小型运算表的封闭性、结合律、单位元与逆元条件。比较
Boolean 加法与乘法，可以看出哪条公理区分了群与幺半群。
图示。幺半群与群都要求结合律和单位元；群还要求每个元素都有逆元。
互动 · 比较情况情况 1 / 4
检查幺半群与群公理
选一个结构，依次检查三条运算律。Monoid 需要前两条；群需要全部三条。
结构 Z={…,−1,0,1,…}
运算：a∗b=a+b
- 结合律对所有 a,b,c，(a∗b)∗c=a∗(b∗c)
- 单位元存在 e，使所有 a 都有 e∗a=a∗e=a
- 逆元每个 a 都有某个 b 使 a∗b=b∗a=e
- 结合律(a+b)+c = a+(b+c)。
- 单位元0 是单位元。
- 逆元a 的逆元是 -a。
成立：(Z,+) 是群
这是一个群。三条运算律都成立。
要留意在无限集合上，运算律要对每个元素论证：算几个例子不能证明它，但一个反例就足以否定。只有 B 小得可以逐一检查所有情况。
快速检查
快速检查
（一条规则 ∗ 要成为集合 X 上的二元运算，必须满足什么输入与输出要求？）
解答 · 答案
它必须是一个函数 ∗:X×X→X。也就是说，它取两个 X 的元素作为输入，并输出一个仍在 X 中的元素。
快速检查
（为什么 (Z,−) 不是幺半群？）
解答 · 答案
减法不满足结合律。例如
(5−3)−1=1但
5−(3−1)=3.两者不同，所以 (Z,−) 不是幺半群。
快速检查
（为什么 (Z,×) 不是群？）
解答 · 答案
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∈B 都有 x+0=0+x=x。
结合律可由有限情况 x,y,z∈{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，并说明为什么不需要右逆。
解答 · 提示
解答 · 参考解答
由 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 函数与关系
提供了函数合成、逆函数，以及共轭类所用的等价类划分定理。代数公理中的量词则使用
1.3 量词与否定
的语言。
3.4 有理数与良定义运算
给出了另一个例子：在数学对象上指定运算，并检查定义是否依赖代表元。序关系则是另一种附加结构，可与
6.3 区间、Cantor set、稠密性与良序
对照；其中的结论不是本节群论证明的前提。