Binary operations and 二元运算

集合S上的二元运算\(*\)满足：

• 结合律：对所有\(a, b, c \in S\)，有\(a*(b*c) = (a*b)*c\)
• 交换律：对所有\(a, b \in S\)，有\(a*b = b*a\)
• 封闭性：集合S中任意两个元素组合后，结果仍属于S

常见二元运算：
整数集上的加法\((\mathbb{Z}, +)\) 是
自然数集上的减法\((\mathbb{N}, -)\)，它们的差\(2 – 5 = -3\)不属于\(\mathbb{N}\)。因为存在自然数对的差落在\(\mathbb{N}\)之外，减法在自然数集上不满足封闭性，所以减法不是\(\mathbb{N}\)上的二元运算

单位元 identity element

设\((S, *)\)是带有二元运算的集合，若存在元素\(e \in S\)，使得对所有\(a \in S\)，有\(a * e = e * a = a\)，则称e为\((S, *)\)的单位元
单位元在运算中起中性作用，与任意元素组合后仍保持该元素不变

并非所有带二元运算的集合都有单位元，例如正整数集对加法\((\mathbb{Z}_{>0}, +)\)就没有单位元
若二元运算存在单位元，则该单位元唯一

逆元 inverse element

设\((S, *, e)\)是带有二元运算和单位元的集合，对元素\(a\in S\)，若存在\(b \in S\)，使得\(a * b = b * a = e\)，则称b为a的逆元
逆元与原元素组合后得到单位元

加法运算中，a的逆元通常记为\(-a\)；乘法运算中，记为\(a^{-1}\)
并非所有元素都有逆元，且逆元若存在则唯一

明确了二元运算、单位元和逆元的概念后，我们来定义抽象代数的核心研究对象

monoid 幺半群

含幺半群是带有二元运算\(*\)的集合M，满足：

1. Closure 封闭性：对所有\(a, b \in G\)，有\(a * b \in G\)
2. 运算\(*\)满足Associative 结合律；对所有\(a, b, c \in G\)，有\((a * b) * c = a * (b * c)\)
3. Identity 单位元\(e \in G\)，使得对所有\(a \in G\)，有\(a * e = e * a = a\)；

含幺半群捕捉了重复组合有意义所需的最小代数结构，以下结构均为含幺半群：

• 从集合X到自身的所有函数，以函数复合为运算，恒等函数为单位元
• \((\mathbb{Z}, +)\)，单位元 0
• \((\mathbb{Z}, \cdot)\)，单位元 1
• \((M_{2×2}(\mathbb{R}), \cdot)\)，单位元\(I_2\)
• 给定字母表上的所有字符串，以连接为运算，空字符串为单位元

当含幺半群中每个元素都有逆元时，便得到更丰富的群结构

Groups 群

群是每个元素都有逆元的含幺半群\((G, *)\)

在 monoid 基础上再加：
4. Inverse 逆元：对每个\(a \in G\)，存在\(b \in G\)，使得\(a * b = b * a = e\)

以上四条为群公理（注意没有交换律，否则矩阵的很多运算都不能算作群）

1. 加法有封闭性和结合律，单位元是0，a的逆元是-a，是monoid，group
2. 加法有封闭性和结合律，单位元是0，只有0有逆元，是monoid
3. 整数乘法有封闭性和结合律，单位元为1，只有\(\pm1\)有乘法逆元\(\Rightarrow\)，是monoid
   有理数乘法有封闭性和结合律，单位元为1 ；但0没有逆元\(\Rightarrow\)，是monoid
4. 由于排除了0，所以所有a都有逆元1/a，是Group
5. 
6. 同上没有变化
7. 元素为实数的2×2 矩阵加法：有封闭性和结合律，单位元是0矩阵，每个矩阵A的逆元是-A，是Group
8. 元素为实数的2×2 矩阵乘法：由Closure和Associative，单位元是单位矩阵，但是有的矩阵不可逆（行列式为0）所以是monoid
9. 同上，限定了行列式非0的实矩阵，所以肯定对于所有矩阵都肯定有逆矩阵，是Group

3的详细过程

其他详细证明过程

5的详细过程

8的过程

The integers with binary operation ◦ given by x ◦ y = x + y + 1;

模算术\(a \equiv b \pmod{n}\) Modular Arithmetic

设正整数\(n ≥ 2\)，若整数a与b的差\(a – b\)能被n整除，则称a与b模n同余，记为\(a \equiv b \pmod{n}\)，等价于a和b除以n余数相同
Two integers a and b are congruent modulo n, written a ≡ b(mod n)

这种同余关系将整数集划分为等价类，整数a模n的等价类（或剩余类）为\([a] = \{a + kn: k \in \mathbb{Z}\}\)，包含所有与a模n同余的整数。例如，模 6 时，2 的等价类为\([2] = \{…, -10, -4, 2, 8, 14, 20, …\}\)，包含所有除以 6 余 2 的整数

模n共有n个不同的等价类，由余数\(0, 1, 2, …, n-1\)表示，定义\(\mathbb{Z}_n = \{[0], [1], [2], …, [n-1]\}\)为这些等价类的集合。为方便起见，常简记元素为\(0, 1, …, n-1\)，默认运算为模n算术（即对等价类进行运算）

同余符号

基础定律：

负数的取余运算 a mod b（余数的绝对值小于除数且正负一致）

除数为正数时

余数必须是非负数，余数小于除数

\(-5 \mod 3\)运算的含义是 “求\(-5\)除以3的余数”
分清被除数和除数：所以被除数是 \(-5\)（被除的数），除数是 3
要满足 \(-5 = 3\times q + r\)（\(0\le r<3\)），代入得 \(-5 = 3\times(-2) + 1\)；
因此 \(-5 \bmod 3 = \boldsymbol{1}\)

除数为负数时

余数必须是负数，余数的绝对值小于除数的绝对值

更多易错例子：除数小于被除数，除数和被除数含负数，除数和被除数包括0

\((\mathbb{Z}_n, +)\)，模n加法

\(\mathbb Z_n=\{0,1,2,\dots,n-1\}\)，它表示“模 n 的同余类集合”
一般配 模 n 加法：\(a\oplus b = (a+b)\bmod n\)

运算的定义（模n加法）：在\(\mathbb{Z}_n\)上定义二元运算\(\oplus\)为：\({a \oplus b := (a + b)\ \text{mod}\ n\quad (a,b \in \mathbb{Z}_n)}\)，即先按整数加法相加，再对 n 取模
其中\((a + b)\ \text{mod}\ n\)表示把整数\(a + b\)除以n后所得的余数，其值必属于\(\{0,1,\dots,n-1\}\)

模 n 加法可以理解为“长度为 n 的循环加法”，类似于一个 n 小时制的钟表：超过 n-1 就从 0 重新开始

单位元是0，a的逆元是n-a

证明

集合\(\mathbb{Z}_n\)非空。模n加法是\(\mathbb{Z}_n\)上的二元运算，且因整数加法满足结合律，故模n加法也满足结合律。幺元为0，因为对任意\(a \in \mathbb{Z}_n\)，有\(a + 0 \mod n = 0 + a \mod n = a \mod n\)。\(\mathbb{Z}_n\)中元素a的逆元为\(n – a \mod n\)。

\((U_n, \times)\)，模n乘法

\(U_n := \{ a \in \{1,2,\dots,n-1\} \mid \gcd(a,n) = 1 \}\)，在 0,1,\dots,n-1 里，挑出那些和 n 互素的数
\(U_{10} = \{ a \in \{1,2,\dots,9\} \mid \gcd(a,10) = 1 \}\)
在 1 到 9 里和 10 互素的数是：1,3,7,9（因为 2、4、5、6、8 都和 10 有公因子 2 或 5）
所以：\(U_{10} = \{1,3,7,9\}\)

运算的定义（模 n 乘法）：在 \(U_n\) 上定义二元运算 \(\odot\) 为：
\(a \odot b := (ab)\ \text{mod}\ n\quad (a,b \in U_n)\)，即先按整数乘法相乘，再对n取模

验证这几个元素构成了群

在模 n 乘法里，对任意 \(a\in U_n\)有\(a\odot 1=(a\cdot 1)\bmod n=a,\qquad 1\odot a=a.\)

比如你刚才的例子 \(U_{10}=\{1,3,7,9\}\)：

• \(3\odot 1=3\)
• \(9\odot 1=9\)

所以单位元是 1（模 n 意义下的 1）

找到每个元素的逆元

• \(1^{-1}=1\)
• \(3^{-1}=7\)（因为 \(3\cdot7\equiv1\pmod{10}\)）
• \(7^{-1}=3\)
• \(9^{-1}=9\)

• 对所有整数\(n \geq 2\)，\(U_n\)（与模n乘法运算）构成群
• 集合\(\mathbb{Z}_n^*\)与模n乘法运算构成群，当且仅当n为素数

Properties of groups 群的性质

• 设G为群，\(a, b, c \in G\)。若\(ba = ca\)（或\(ab = ac\)），则\(b = c\)
• 设\(a, b \in G\)，则\((ab)^{-1} = b^{-1}a^{-1}\)
  • (ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1} = aea^{-1} = aa^{-1}=e
  • (b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}eb = b^{-1}b=e
  • 只有当群就是“非零实数在乘法下”这种情况时，才可以把 \(x^{-1}\)记成\(\frac1x\)
• 设\(g \in G\)，\(m, n \in \mathbb{Z}\)，则\(g^m g^n = g^{m+n}\)。

阿贝尔群 Abelian group

若群\((G, *)\)的二元运算\(*\)满足交换律，即对所有\(a, b \in G\)有\(a*b = b*a\)，则称\((G, *)\)为阿贝尔群

群的阶 order

G的阶（order）为其元素个数，记为\(|G|\)或\(O(G)\)

群的凯莱表 Cayley table/ Composition table

把群中任意两个元素的运算结果按“行元素 ∘ 列元素”填成的乘法表，用来完整展示该群的运算结构

群的凯莱表性质：

1. 每行每列中每个元素恰好出现一次(拉丁方性质)
2. 单位元对应的行和列与表头元素一致；（就是说e和什么运算结果就是什么）
3. 阿贝尔群的凯莱表关于主对角线对称（因\(g * h = h * g\)）

例题：

• 封闭性：确保运算结果不会超出集合范围
• 单位元：确保集合里存在 “运算中的中性元素”
• 逆元：确保每个元素都有对应的 “逆元素”（两者运算后得到单位元）
• 结合律：确保运算满足 “顺序不影响结果（指括号的结合顺序）

群同态和群同构 homomorphism & isomorphism

• homo-：侧重 “同类、同质”，强调本质或种类上的相同
  如 homogeneous（同质的）、homo sexual 同性恋的
• iso-：侧重 “对等、等量、同构”，强调数量、结构、位置等维度的相等，
  如 isotope（同位素，位置相同）、isosceles（等腰的，边长相等）

群的研究不仅限于单个群，还包括群之间的关系

(1) 设\((G, \circ)\)和\((H, *)\)是群，若函数\(\psi: G \to H\)满足对所有\(a, b \in G\)有\(\psi(a \circ b) = \psi(a) * \psi(b)\)，则称\(\psi\)为群同态（homomorphism）

当同态是双射时，它在群之间建立了极强的关系

(2) 若同态\(\psi\)是双射（单射+ 满射），则称\(\psi\)为群同构（isomorphism），记为\(G \cong H\)，此时称群G与H同构（isomorphic）

同构的群代数上不可区分，结构完全相同，仅元素标记不同。从群论角度看，同构的群被视为 “相同”
设\(\psi: G \to H\)是群同构，则：

1. \(\psi(e_G) = e_H\) （G的单位元映射到H的单位元）
2. 对任意整数\(n \in \mathbb{Z}\)和\(a \in G\)，有\(\psi(a^n) = (\psi(a))^n\)；
3. 对任意\(a, b \in G\)，\(\psi(a)\psi(b) = \psi(b)\psi(a)\)当且仅当\(ab = ba\)；
4. G是阿贝尔群当且仅当H是阿贝尔群；
5. 定义\(\psi^{-1}: H \to G\)为\(\psi^{-1}(b) = a\)（其中\(b = \psi(a)\)），则\(\psi^{-1}\)是H到G的同构；
6. 若G是有限群，则H也是有限群且\(o(G) = o(H)\)
7. isomorphisms preserve element orders 同构会保持元素的阶（关键定理） – 用来证伪两个群同构

同态用相似符号表示，当两个代数系统同构也就意味着性质完全相同，故用全等符号表述

设\(G = (\mathbb{Z}_4, +) = (\{0, 1, 2, 3\}, +)\)，\(H = (\{1, i, -1, -i\}, \cdot)\)（i为虚数单位，满足\(i^2 = -1\)），定义\(\psi: G \to H\)为\(\psi(0) = 1\)，\(\psi(1) = i\)，\(\psi(2) = -1\)，\(\psi(3) = -i\)

验证同态：

• \(\psi(1 + 1) = \psi(2) = -1 = i \cdot i = \psi(1) \cdot \psi(1)\)；
• \(\psi(1 + 2) = \psi(3) = -i = i \cdot (-1) = \psi(1) \cdot \psi(2)\)；
• \(\psi(1 + 3) = \psi(0) = 1 = i \cdot (-i) = \psi(1) \cdot \psi(3)\)；
• \(\psi(2 + 2) = \psi(0) = 1 = (-1) \cdot (-1) = \psi(2) \cdot \psi(2)\)；
• \(\psi(2 + 3) = \psi(1) = i = (-1) \cdot (-i) = \psi(2) \cdot \psi(3)\)；
• \(\psi(3 + 3) = \psi(2) = -1 = (-i) \cdot (-i) = \psi(3) \cdot \psi(3)\)

\(\psi\)是双射（两集合均含 4 个元素且\(\psi\)单射），故为同构，即\(\mathbb{Z}_4 \cong \{1, i, -1, -i\}\)。该同构表明，4 阶循环加法群与 4 次单位根乘法群结构相同

B站习题

Subgroups 子群

定义：设G为群，若非空子集\(H \subseteq G\)满足\((H, *)\)构成群（其中\(*\)是G的二元运算），则称H为G的子群（subgroup），记为\(H \leq G\)。

需明确验证（子集也能单独成群）

• 封闭：\(x,y \in H \Rightarrow x * y \in H\)
• 结合律：从G继承（不用单独证）
• 单位元在H：\(e \in H\)
• 逆元仍在H：\(x \in H \Rightarrow x^{-1} \in H\)

等价证明：A non-empty subset H of a group G is a subgroup of G if for all x, y ∈ H, x ∗ y ∈ H and x −1 ∈ H.
进一步等价为
若\( H \neq \varnothing \)，并且对任意\( a,b \in H \)，都有\( ab^{-1} \in H \)，则\( H \leq G \)
加法群里对应的是：对任意\( a,b \in H \)，有\( a – b \in H \)

群G的中心 centre Z(G)

\(Z(G) = \{ a \in G \mid \text{对所有 } g \in G,\ a * g = g * a \}\)
群中与所有元素都可交换(运算顺序不影响结果)的元素构成的集合
且这个集合也是原群的子群\(Z(G) \leq G\)

判断方法：如果a对应的行列，值完全一样，那么对所有x：\(ax = xa\)，说明\(a \in Z(G)\)
第三行和第三列都是 3 4 1 2 8 7 5 6，第一行和第一列都是1 2 3 4 5 6 7 8

中心化子 centraliser \(C_G(g)\)

群G中元素g的中心化子（centraliser）：\(C_G(g) = \{h \in G \mid g*h = h*g\} \leq G\)
中心化子 C_G(g) 是“能和指定元素 g 交换的所有元素
中心 Z(G) 是“能和群里所有元素都交换的元素”（即所有中心化子的交集）

循环群cyclic group 生成元generator 群元素的阶\(o(g)\)或\(|g|\)

循环群：
在\((G, *)\)群中，若存在一个元素\(a \in G\)，使得对\(\forall x \in G\)，都存在\(i \in \mathbb{Z}\)，满足
\(x = a^i\)，则称\(\lt G,* \gt\)为循环群，记为\(G = \lt a \gt\)
生成元：
称a为该循环群的一个生成元
群元素的阶：

因此在不同的群运算下有不同的含义，比如加法运算的群：

加法群 (G,+)中元素阶的定义

循环子群：
群G中的任意元素g的整数幂组成的子集\(<g>=\left\{g^{n} \mid n \in \mathbb{Z}\right\}\)是G的子群
此子群称为由g生成的循环子群，g称为该循环子群的生成元
循环群可看做循环子群的一种特殊情况，即当\(G = \lt a \gt\)是一个循环群时，\(G = \{a^n \mid n \in \mathbb{Z}\}\)

设g是阶为n的循环群G的生成元，则\(g^{k}\)是G的生成元当且仅当\(\gcd(k, n)=1\)（即k与n互质）

判断元素是否为群的生成元：\(k \in \mathbb{Z}_{n}\)是\(\mathbb{Z}_{n}\)的生成元当且仅当\(\gcd(k, n)=1\)

求有限循环群的步骤

循环群的性质

从循环子群的角度解释，若存在\(g \in G\)，使得\(<g>=G\)，则称群G为循环群

加法群 cyclic（循环）：存在某个元素g，使得群中任意元素都可写成ng（\(n\in\mathbb{Z}\)），即\(G=\langle g\rangle=\{ng:n\in\mathbb{Z}\}\)。
乘法群 cyclic（循环）：存在某个元素g，使得群中任意元素都可写成\(g^n\)（\(n\in\mathbb{Z}\)），即\(G=\langle g\rangle=\{g^n:n\in\mathbb{Z}\}\)。

没什么用的定理

定理 4：设G是群，\(g \in G\)：

• 若g的阶为无限，则g的所有幂次互不相同，即对\(n \neq m\)，有\(g^{n} \neq g^{m}\)；
• 若g的阶为\(o(g)=n\)，则\(<g>=\{e, g, \cdots, g^{n-1}\}\)

由阶的定义，对\(k=1, \cdots, n-1\)，有\(g^{k} \neq e_{G}\)，由此可得两个重要结论：
(1) 元素\(\{e_{G}, g, \cdots, g^{n-1}\}\)互不相同，且\(<g>=o(g)\)；
(2) \(g^{k}=e_{G}\)当且仅当\(o(g) \mid k\)（即\(o(g)\)整除k）

定理 5：设G是由g生成的循环群：

• 若g的阶为无限，则\(G \cong \mathbb{Z}\)；
• 若g的阶为\(o(g)=n\)，则\(G \cong \mathbb{Z}_{n}\)。

循环群的每个子群都是循环群；若G是阶为n的循环群，g是其生成元

• 则G的任意子群的阶都整除n；若\(d>0\)是n的真因子，则G恰有一个阶为\(n/d\)的子群，且该子群由\(g^{n/d}\)生成
• 推论：设\(d>0\)是n的真因子，则\(<n/d>\)是\(\mathbb{Z}_{n}\)中唯一的d阶子群，且\(\mathbb{Z}_{n}\)的所有子群都具有该形式

• 定理：设G是n阶循环群，若\(d>1\)且\(d \mid n\)，则G中阶为d的元素个数为\(\phi(d)\)（欧拉函数）

置换群 Permutation groups.

定义：集合A的置换是一个双射函数\(\pi: A \to A\)，记\(\pi(x)\)为\([x]\pi\)

我们仅考虑集合\(\{1,\cdots,m\}\)的置换。置换就是把 n 个不同元素一一对应地排成一列：第一个有 n 种选法、第二个有 n-1 种……相乘得到总数 n!，所以有限集A（含n个元素）的置换共有\(n!\)个

例 ：定义\(\{1,2,3,4\}\)的置换\(\pi\)：
\([1]\pi=2,\ [2]\pi=3,\ [3]\pi=1,\ [4]\pi=4\)

集合\(\{a_{1},\cdots,a_{n}\}\)的置换\(\pi\)可表示为\(2 \times n\)矩阵：上行为A的元素，下行为其在\(\pi\)下的像：
\(\pi=\left(\begin{array}{ccc} a_{1} & \cdots & a_{n} \\ {[a_{1}]\pi} & \cdots & {[a_{n}]\pi}\end{array}\right)\)

求两个置换的复合

求单位置换（对应前后关系不变）

求逆置换

Product of transpositions 对换的乘积

任意一个长度为 k 的轮换，都可以分解成 k−1 个以 a1​ 为公共元素的对换的乘积。

循环 cycle

在置换 \pi 的作用下，一串元素按顺序“一个指向下一个”，最后又回到起点，形成一个圈
是把一个置换用“沿着映射走一圈”的方式写出来的一种表示法

• 不相交循环（disjoint cycles）：指两个循环没有共同的元素。例如 (1 2) 和 (3 4)，它们没有共享任何数字，就是不相交的
• 非不相交循环（non-disjoint cycles）：指两个循环有至少一个共同的元素。例如 (1 2) 和 (1 3)，它们共享了元素 1，就是非不相交的

规则：

• 单点循环\((a)\)通常省略不写
• 若置换的循环分解中未出现元素x，则\([x]\pi=x\)（即x自身构成一个循环）

易错：

定理 12：集合\(A=\{a_{1},a_{2},\cdots,a_{n}\}\)的每个置换都可表示为不相交循环的复合

定理 13：不相交循环\(\alpha=(a_{1},\cdots,a_{m})\)和\(\beta=(b_{1},\cdots,b_{n})\)可交换（即\(\alpha\beta=\beta\alpha\)）

对称群 Sn

定义 ：对\(n \geq 1\)，集合\(\{1,\cdots,n\}\)的所有置换在复合运算下构成群，记为\(S_{n}\)，称为对称群
对称群是特殊的置换群，它是最大的置换群

定理 15：对\(n \geq 1\)，\(|S_{n}|=n!\)（对称群\(S_{n}\)的阶为n的阶乘）

求逆置换，置换的阶

用不相交循环表示的置换的阶，等于每个循环长度的最小公倍数

Cosets 陪集

左陪集和右陪集 left/right coset:
设G是一个群，H是G的子群，a∈G。包含a的H的左陪集定义为： 在加法群((ℤₙ,ℤ))里：aH = a+H = {a+h | h∈H} 在乘法群（U₂₀）里：aH = {ah | h∈H} 包含a的H的右陪集定义为： Ha = {ha | h∈H}

把它想成“给 H 全体成员统一加一个前缀 a”

引理 1：设 H≤G（H 是 G 的子群），a, b∈G，则：

1. a∈aH；
2. aH=H 当且仅当 a∈H；
3. 要么 aH=bH，要么 aH∩bH=∅；
4. aH=bH 当且仅当 a⁻¹b∈H；
5. 若 H 是有限集，则 | aH|=|H|；
6. aH=Ha 当且仅当 aHa⁻¹=H。

Lagrange’s Theorem 拉格朗日定理

设 G 是有限群，\(H \subset G\) 是子群，则 H 的阶整除 G 的阶（记为 \(|H| \mid |G|\)），且 H 在 G 中的不同陪集个数为 \(|G| / |H|\)

例子：

例题：

用 拉格朗日定理：子群阶 |H| 必须 整除 群阶 |G|。

所以“所有可能子群阶数”就是该数的所有正因子。注意：这只是“可能的”，拉格朗日定理给出了子群阶数的必要条件，不保证每个因子都一定存在对应子群。

例题：

推论：

设 G 是有限群，则对所有 \(a \in G\)，\(o(a) \mid |G|\)，且 \(a^{|G|} = e_G\)。

任何素数阶群都是循环群

欧拉定理

Fermat’s little theorem 费马小定理：设 p 是素数，\(a \in \mathbb{Z}\) 满足 素数p不整除整数，则 \(a^{p-1} \equiv 1 \pmod{p}\)。也可写为\[ a^{p-1} \mod p = 1 \]

Euler’s theorem 欧拉定理：设 \(a, n\) 是整数，\(n \geq 2\) 且 \(\gcd(a, n) = 1\)，则 \(a^{\phi(n)} \equiv 1 \pmod{n}\)
ϕ(n) 是欧拉函数，表示 “1 到n−1中与n互质的整数个数”；

例题

证明H是G的子群

• 证明H是G的一部分
• a*b 属于H
• a^-1属于H

\(\mathrm{GL}_2(\mathbb R)\): 一般线性群（general linear group）：所有可逆的 2\times2 实矩阵的集合
\(\mathrm{Mat}_2(\mathbb R)\): 所有 2\times 2 实矩阵的集合（matrix space）

证明两个群不同构不需要按照定义

在群论里，\(a^{-1}\) 的意思是 a 的逆元，不一定是数的 \(\frac{1}{a}\)。