半群, 群

代数 令集合 `S != O/`, `*` 为 `S` 上的二元运算, 称 `(S, *)` 为一个代数 (或广群, 或半群胚), 如果 `*` 在 `S` 上封闭, 即对任意 `a, b in S`, 有 `ab := a * b in S`. 或等价地, `S S overset d = {s_1 s_2 | s_1, s_2 in S} sube S`. 如果 `|S| = 1`, 称这个代数是平凡的. 例如, 平凡半群, 平凡群等. 如果 `|S| lt oo`, 称这个代数是有限的. 例如, 有限半群, 有限群等; 否则称它为无限的.

半群

半群
• 称代数 `(S, *)` 为一个半群 (semigroup), 如果 `*` 满足结合群, 即 `(a b)c -= a(b c)`. 一般把这种满足结合律的运算 `*` 称为乘法. 结合律看起来 "理所当然", 事实并不是这样! 比如幂运算 "^" 就不满足结合律.
• 若半群 `S` 中存在元素 `0` 满足 `0a -= 0` (`a0 -= 0`) 则称 `0` 为 `S` 的左零元 (右零元). 若 `0` 同时是左, 右零元, 则称它为零元. 含有左 (右) 零元的非平凡半群称为左 (右) 零半群, 含有零元的非平凡半群称为含零半群.
• 若半群 `S` 中存在元素 `1` 满足 `1a -= a` (`a1 -= a`) 则称 `1` 为 `S` 的左幺元 (右幺元). 若 `1` 同时是左, 右幺元, 则称它为幺元. 含有幺元的非平凡半群称为幺半群 (monoid).
  设 `a, b in S`. 若 `a b = 1`, 则称 `a` 是 `b` 的左逆元, `b` 是 `a` 的右逆元. 若 `b` 同时是 `a` 的左, 右逆元, 则称 `b` 为 `a` 的逆元. 有逆元的元素称为可逆元或单位.
• 若半群 `(S, *)` 满足交换律, 即 `ab -= ba`, 则称 `S` 为交换半群. 显然交换半群的左零元 (如果存在) 也是右零元, 左幺元 (如果存在) 也是右幺元.
• 若半群 `S` 满足左, 右消去律, 即对任意 `a, b, c in S`, `a b = a c rArr b = c`,
  `b a = c a rArr b = c`, 则称 `S` 为双消半群.
• 若半群 `S` 的每一元素都是正则的, 即 `(AA a in S)` `(EE x in S)` `a x a = a`, 则称 `S` 为正则半群.
• 若半群 `S` 满足 `(AA a in S)` `(EE x in S)` `(a x)^2 := a x a x = a x`, 则称 `S` 为反演半群. 显然正则半群都是反演半群.

在半群中,
1. 若左, 右零元 (幺元) 都存在, 则它们相等; 同一元素的左右逆元都存在时, 它们也相等;
2. 零元 (幺元, 逆元) 若存在, 必惟一; 同一元素的逆元若存在, 必惟一.

1. 设 `0` 为左零元, `0'` 为右零元, 则 `0 = 0 0' = 0'`;
   设 `1` 为左幺元, `1'` 为右幺元, 则 `1 = 1 1' = 1'`;
   设 `b, b'` 分别为 `a` 的左, 右逆元, 则 `b = b (a b') = (b a)b' = b'`.
   
2. 设 `0, 0'` 都是零元, 则由 1, 它们相等. 幺元, 逆元类似.

• 设 `(S, *)` 为一代数, 如果存在元素 `x in S`, `x^2 := x x = x`, 则称 `x` 为幂等元. 显然, 半群的左, 右零元, 左, 右幺元都是幂等元; 半群的幂等元都是正则元.
• 设 `(S, *)` 为一半群, `a in S`, 规定 `a^1 = a`, `a^n = a * a^(n-1)`, `n = 2, 3, cdots`. 易知通常的指数规则 `(AA m, n in ZZ^+) a^m a^n = a^(m+n)`, `(a^m)^n = a^(m n)` 在半群中也成立.

设 `S` 为一半群, 称 `a, b in S` 可交换, 如果 `a b = b a`. 称 `Z(S) := {a in S | (AA x in S) a x = x a}` 为 `S` 的中心 (德语: Zentrum), 即与 `S` 中任意元素都可交换的元素的集合.

群

群
1. 称半群 `G` 为一群 (group), 如果它存在幺元, 且每个元素都存在逆元, 即 `(EE e in G)` `e a -= a e -= a`,
   `(AA a in G)` `(EE a' in G)` `a' a = a a' = e`. 群中的元素就简称为群元.
2. 若群 `G` 的乘法还满足交换律, 则称它为 Abel 群 (或交换群). `G` 为 Abel 群时, 也常记作 `(G, +)`, 并把其上的运算称为加法.

1. 群是双消半群.
2. 群中的幺元是惟一的, 每个元素的逆元也是惟一的, 以后我们把 `a` 的逆元记为 `a^-1`.
3. `e` 为群的惟一幂等元.
4. `(a b)^-1 = b^-1 a^-1`.

1. 这是因为在 `a b = a c` 两边同时左乘 `a` 的逆元, 就得到 `b = c`.
2. 幺元的惟一性由半群的相关结论可知. 逆元的唯一性可由 `a'a = a_0'a = e` 两边消去 `a` 得 `a' = a_0'`; 或者 `a' = a' a a_0' = a_0'`.
3. 若 `e_0^2 = e_0`, 则由 `e_0 e_0 = e_0 e` 两边消去 `e_0` 得 `e_0 = e`.
4. 直接计算, `b^-1 a^-1 a b = b^-1 e b = b^-1 b = e`.

群的等价定义 设 `G` 为半群, `G` 中存在左幺元, 且每个元素都存在左逆元, 即 `(EE e in G)` `e a -= a`,
`(AA a in G)` `(EE a' in G)` `a' a = e`. 可以证明 `G` 为一群. 事实上, 对任意 `a in G`, 先证其左逆元 `a'` 也是它的右逆元. 取 `a'` 的左逆元 `a''`, 有 `a a' = e a a' = a'' a' a a'` `= a'' e a' = a'' a' = e`. 从而左幺元 `e` 也是右幺元: `a e = a a' a = e a = a`. 类似可以证明, 下面也是群的一个等价定义: 半群 `G` 上存在右幺元, 且每个元素都存在右逆元, 即 `(EE e in G)` `a e -= a`,
`(AA a in G)` `(EE a' in G)` `a a' = e`;

1. 整数集 `ZZ` 在通常的加法下成一群, 称为整数加群;
2. 集合 `U_n = {omega in CC | omega^n = 1}`, 易知 `|U_n| = n`, 且关于复数乘法成一群, 称为 `bm n` 次单位根群.

令 `bbb F` 为一数域, 则 `GL_n(bbb F) = {bm A in bbb F^(n xx n) | |bm A| != 0}`,
`SL_n(bbb F) = {bm A in bbb F^(n xx n) | |bm A| = 1}`,
`U_n (bbb F) = {bm A in bbb F^(n xx n) | bm (A'A) = bm E}`. 关于矩阵的通常乘法都成群, 分别称为 `bbb F` 上的一般线性群 (`n` 阶非奇异矩阵的集合), 特殊线性群 (行列式为 1 矩阵的集合) 和正交群 (正交矩阵的集合).

设 `D_(2n) = {a_0, a_1, cdots, a_(n-1), b_1, b_2, cdots, b_n}` 是正 `n` 边形 (`n ge 3`) 全体对称构成的集合, 其中 `a_i` 表示绕中心逆时针旋转 `2 i pi // n` 的变换, `b_j` 表示沿对称轴 `l_j` 的反射变换. 则 `D_(2n)` 为一群, 称为二面体群.

魔方的全体变换构成 Rubik 群.

群与双消半群

设 `S` 为半群, `s in S`, 则用 `s` 左乘 `S` 的任一元素诱导出 `S` 上的左平移变换 `s_l: S to S`
`a to s a`. 类似, 用 `s` 右乘 `S` 的任一元素诱导出 `S` 上的右平移变换 `s_r`.

令 `S` 为半群, 下列各款等价:
1. `S` 为一双消半群;
2. `S` 上的两类方程 `a x = b`, `x a = b` 在 `S` 中如果有解, 则解常惟一;
3. 对任意 `a in S`, `S` 上的左, 右平移 `a_l, a_r` 常为单射.

令 `G` 为半群, 下列各款等价:
1. `G` 为一群;
2. `G` 上的两类方程 `a x = b`, `x a = b` 在 `G` 中常有解;
3. 对任意 `a in G`, `G` 上的左, 右平移 `a_l, a_r` 常为满射 (事实上, 由于群是双消半群, 可推出 `a_l, a_r` 是双射);
4. 任取 `a in G`, 分别定义 `a G := {a g | g in G}`, `G a := {g a | g in G}`, 则 `a G = G a = G` (集合意义的相等).

只证 3 `rArr` 1. 任取 `a in G`, 由 `a_r` 为一满射变换知, `(EE e in G)` `a_r(e) = a`, 即 `e a = a`. 从而对任意 `b in G`, 由 `a_l` 为一满射变换知, `(EE b_0 in G) a_l(b_0) = b`, 即 `a b_0 = b`. 所以 `e b = e a b_0 = a b_0 = b`. 这说明 `e` 为左幺元. 再令 `e` 在 `b_r` 下的原像为 `b^-1`, 有 `b^-1 b = e`, 即 `b^-1` 为 `b` 的左逆元. 由前述群的等价定义知 `G` 为一群.

有限双消半群为群.

因为有限集上的变换为一单射当且仅当它为一满射.

群与群元的阶

群上的幂运算 令 `(G, *)` 为一群, `a in G`, `n in ZZ^+`. `a^n` 的定义与半群的相同, 此外 `a^0 := e`, `quad a^-n := (a^-1)^n`. 从而通常的指数规则在群中仍成立: `(AA m, n in ZZ^+) a^m a^n = a^(m+n)`, `(a^m)^n = a^(m n)`. 当 Abel 群被记作 `(G, +)` 时, 也将 `a^n` 写成 `n a`, 将 `a^-1` 写成 `-a`. 且在 Abel 群中, 满足第三条指数规则: `(AA m in ZZ)` `(AA a, b in G)` `(a b)^m = a^m b^m`.

群 `G` 中元素 `a` 的阶 (order)定义为 `|a| = min{m in ZZ^+ | a^m = e}`; 若上式右端的集合为空, 称 `a` 的阶为无限, 记为 `|a| = oo`.
有限群 `G` 的阶定义为它的元素个数 `|G|`. 阶的另一种记号是 `"ord " a`, `"ord " G`.

若 `a, b in G`, 且存在 `g in G` 使得 `b = g a g^-1`, 则称 `a, b` (关于 `g`) 共轭.

1. `a, b` 在 `G` 中共轭, 但在 `G` 的子群中可能不共轭.
2. `a, b` 可以关于不止一个元素是共轭的, 比如 `e` 和自身共轭, 可以是 `e = g e g^-1`, 也可以是 `e = h e h^-1`.

令 `G` 为一群, `e` 是幺元, `a, b in G`, 则
1. `|e| = 1`;
2. `|a| = |a^-1|`;
3. `|a| = |b a b^-1|`, 即共轭元素的阶相等;
4. `|a b| = |b a|`.

1. 显然.
2. 记 `|a| = n`, `|a^-1| = m`, 由 `(a^-1)^n = (a^n)^-1 = e^-1 = e`, 得到 `m le n`; 另一方面, `a^m = (a^-m)^-1` `= ((a^-1)^m)^-1= e^-1 = e`, 得到 `m ge n`.
3. 这是因为 `a^n = e` 当且仅当 `(b a b^-1)^n = e`.
4. 只需说明 `a b` 与 `b a` 共轭: `b a = b (a b) b^-1`.

设 `a` 是群 `G` 中的 `n` 阶元, 则对任意 `m in ZZ`, `a^m = e iff n | m`.

`lArr`) 显然.
`rArr`) 令 `m = q n + r`, `q in ZZ`, `0 le r lt n`. 则 `e = a^m = a^(q n + r)` `= (a^n)^q a^r = e a^r = a^r`. 由 `r lt n` 知, 只可能是 `r = 0`, 从而 `n | m`.

设 `a` 是 `n` 阶群 `G` 的元素, 则 `|a| le n`.

由群的封闭性知, 有 `n+1` 个元素 `a^0, a^1, cdots, a^n in G`. 但 `|G| = n`, 由鸽巢原理, 存在 `i gt j`, 使 `a^i = a^j`, `i, j = 0, 1, cdots, n`. 所以 `a^(i-j) = a^i a^-j = a^j a^-j = e`. 设 `|a| = m`, 则 `m | i-j gt 0`, 因此 `m le i-j le n`.

设 `a` 是群 `G` 的 `n` 阶元, 则 `|a^m| = n/((m","n))`, `quad AA m in ZZ`. 特别地,
1. 若 `|a| = s t`, `s, t in ZZ^+`, 则 `|a^s| = t`;
2. `|a^m| = n` 当且仅当 `(m, n) = 1`.
例如, `a = (1\ 2)(3\ 4\ 5\ 6\ 7)` 的阶是 `lcm(2, 5) = 10`. 既然 `|a| = 10 = 2 xx 5`, 那么 `|a^5| = 2`, 这是因为 `a` 连续作用 5 次以后, 它所含的 5-轮换被抵消了.

记 `|a^m| = k`, `(m, n) = d`. 由 `a^(m n/d) = a^(n m/d) = e` 得 `k | n/d`; 另一方面, 由 `a^(m k) = e` 知 `n | m k`, 从而 `n/d | m/d k`, 但 `(n/d, m/d) = 1`, 所以 `n/d | k`.

子群

子群 令 `(G, *)` 为一群, `H` 是 `G` 的非空子集. 如果 `H` 关于 `*` 也成一群, 则称 `H` 是 `G` 的一个子群, 记作 `H le G`.

Abel 群的子群也是 Abel 群.

设群 `H le G`, 则 `H` 的幺元就是 `G` 的幺元, `a in H` 在 `H` 中的逆元就是 `a` 在 `G` 中的逆元.

幺元的惟一性由幂等元在群中的惟一性保证. 以 `a', a^-1` 记 `a` 在 `H` 和 `G` 中的逆元, 则 `a' = a' e = a' a a^-1` `= e a^-1 = a^-1`.

判定子群的充要条件 设 `G` 为一群, `H` 是 `G` 的非空子集, 则以下几款等价:
1. `H le G`;
2. `(AA a, b in H)` `a b in H`, `a^-1 in H`;
3. `(AA a, b in H)` `a b^-1 in H`.
从而验证 `H` 是 `G` 的子群, 只需验证 `H` 对乘法的封闭性和 `H` 中逆元的存在性, 或者验证方程 `x b = a` 在 `H` 中常有解即可.

1. `rArr` 2. 显然.
2. `rArr` 3. 显然.
3. `rArr` 1. 结合律在 `H` 上成立是显然的; 取 `b = a` 知 `e in H` (幺元); 取 `a = e` 知对任意 `b in H`, `b^-1 in H` (逆元); 最后, 对任意 `a, b in H`, 有 `a b = a(b^-1)^-1 in H` (封闭性).

若 `H` 是群 `G` 的非空有限子集, 则 `H le G iff` `(AA a, b in H)` `a b in H`.

任取 `a in H`, 因 `H` 有限, `EE s gt t`, `s, t in ZZ^+`, `a^s = a^t`, 从而 `a^-1 = a^(2(s-t)-1) in H`.

回顾半群的中心的定义: `Z(G) := {a in G | (AA x in G) a x = x a}`. 若 `G` 为一群, 可以证明 `Z(G) le G`; 若 `G` 为一 Abel 群, 则 `Z(G) = G`.

子群的交, 并与乘积 设 `G` 为一群, `H, K` 是 `G` 的两个子群, 则
1. `H nn K le G`;
2. `H uu K le G` `iff H sube K or K sube H`;
3. `HK := {h k | h in H, k in K} le G` `iff H K = K H`.
此定理可类比于线性子空间的相关结论.

1. 显然 `e in H nn K`, 从而 `H nn K` 非空. `AA a, b in H nn K`, 由判定子群的充要条件, `a b^-1 in H`, `a b^-1 in K`. 即 `a b^-1 in H nn K`. 因此 `H nn K le G`.
2. `lArr`) 显然. `rArr`) 设 `H sube K` 不成立, 即 `EE h in H`, `h !in K`. 任取 `k in K`, 由 `H uu K le G` 知 `h k in H uu K`. 若 `h k in K`, 则 `h = (h k) k^-1 in K`, 矛盾; 故 `h k in H`, 于是 `k = h^-1 (h k) in H`. 所以 `K sube H`.
3. 令 `H K = K H`. `AA h k in H K`, 其中 `h in H`, `k in K`, 有 `(h k)^-1 = k^-1 h^-1 in K H = H K`. 又 `(H K)(H K) = H(K H)K = H(H K)K = (H H)(K K) = H K`, (注: 上式的 `H, K` 可以换成任意属于 `H, K` 的元素进行运算, 结果是相同的) 即 `H K` 关于乘法封闭. 于是 `H K le G`.
   反之, 令 `H K le G`. 则对任意 `x in H K`, `x^-1 in H K`. 记 `x^-1 = h k`, 其中 `h in H`, `k in K`, 有 `x = (h k)^-1 = k^-1 h^-1 in K H`. 得到 `H K in K H`. 同理 `K H sube H K`. 于是 `H K = K H`.

群同态与同构

令 `(S, *)`, `(T, @)` 为两个半群胚 (半群, 群). 称映射 `f: S to T` 为 `S` 到 `T` 的一个半群胚 (半群, 群) 同态 (映射), 如果 `f(a * b) -= f(a) @ f(b)`. 在不引起混淆的情况下, 上式也可以写为 `f(a b) -= f(a) f(b)`. 当 `f` 为一单射 (满射, 双射) 时, 称 `f` 为一单同态 (满同态, 同构) 映射. 显然同构映射的逆映射也为一同构映射.
如果存在一个从 `S` 到 `T` 的同构映射, 则称 `S`, `T` 同构, 记为 `S ~= T`.

群同态的复合仍为一同态映射.

`f: S to T` 为一同态映射时, `C_("Ker"f) ~= "Im"f`, 其中 `C_("Ker"f)` 是等价关系 `"Ker"f` 的一个截面. 特别当 `f` 为一满同态时, `C_("Ker"f) ~= T`, 当 `f` 为一单同态时, `S ~= "Im"f`.

令 `G` 和 `H` 为两个群, `f: G to H` 为一群同态映射, 则
1. `G` 的幺元的像是 `H` 的幺元;
2. 群元的逆元的像是其像的逆元;
3. `n` 阶元的像的阶整除 `n`; 特别 `f` 为同构映射时, `n` 阶元的像也为 `n` 阶.

1. 记 `G` 的幺元为 `e`. 由 `f(e) f(e) = f(e^2) = f(e)` 知, `f(e)` 为 `H` 的一个幂等元, 而群的幂等元只有幺元. 因此 `f(e)` 为 `H` 的幺元.
2. `AA a in G`, 由 `f(a) f(a^-1) = f(a a^-1) = f(e)` 及群元的逆元的惟一性知, `f(a^-1)` 为 `f(a)` 的逆元.
3. `AA a in G`, 记 `|a| = n`, `|f(a)| = m`, 则 `(f(a))^n = f(a^n) = f(e)`, 故 `m | n`.

群的同态像 (原像) 仍为一群. 令 `G`, `H` 为两个群, `G_1 le G`, `H_1 le H`, `f: G to H` 为一群同态映射, 则 `f(G_1) le H`, `quad f^-1(H_1) le G`. 特别有 `"Im"f le H`, `"Im"f^-1 le G`.

任取 `f(a), f(b) in f(G_1)`, 其中 `a, b in G_1`, 从而 `f(a) f(b)^-1 = f(a) f(b^-1) = f(a b^-1) in f(G_1)`. 因此 `f(G_1) le H`. 又任取 `c, d in f^-1(H_1)`, 则 `f(c), f(d) in H_1`, 从而 `f(c d^-1) = f(c) f(d^-1) = f(c) f(d)^-1 in H_1`. 所以 `c d^-1 in f^-1(H_1)`, 于是 `f^-1(H_1) le G`.

令 `G, H` 为两个群, `f: G to H` 为一群同态映射. 则
1. `f` 的像 `"Im"f = f(G)` `= {f(a) | a in G} le H`; `f` 满 `iff "Im"f = H`.
2. `f` 的核 `"Ker"f = f^-1(e_H)` `= {a in G | f(a) = e_H} le G`; `f` 单 `iff "Ker"f = {e_G}`.

直接应用 (注意 `{e_H}` 自成一平凡群). 下面设 `"Ker"f = {e_G}`, 对任意满足 `f(a) = f(b)` 的 `a, b in G`, 有 `e_H = f(a) f^-1(b) = f(a b^-1)`. 但 `"Ker"f = {e_G}`, 所以 `a b^-1 = e_G`, 即 `a = b`. 因此 `f` 是单射.

群 `G` 到自身的同态称为自同态, `G` 上全体自同态关于映射的合成构成半群 `End(G)`; `G` 到自身的同构称为自同构, `G` 上全体自同构为一群 `Aut(G)`. 注意自同态的等式 `f(a)f(b) = f(a b)` 两边的乘法是同一个群的乘法因而是同一种乘法, 因此 `f(e)f(e) = f(e*e) = f(e)`, 这推出 `f(e) = e`, 即自同态保持幺元不动. 我们在第四章进一步讨论自同构群.

循环群

由一元素生成的循环群

生成集 令 `G` 为一群, `X` 是 `G` 的非空子集, 记 `(:X:)` 为 `G` 的所有包含 `X` 的子群的交. 由于 `(:X:)` 是子群的交, 因此它也是一子群, 且是 `G` 的含 `X` 的最小子群. 称 `(:X:)` 为由 `X` 生成的子群, `X` 称为 `(:X:)` 的生成集. 特别若 `(:X:) = G`, 则称 `X` 为 `G` 的生成集. 如果 `|X| lt oo`, 则称 `G` 为一有限生成群.

以 `X^-1` 记 `X` 中全体元素的逆组成的集合, 考虑到群上运算的封闭性和逆元的存在性, 则由 `X` 生成的子群是 `X uu X^-1` 中任意有限个元素乘积的全体, 即 `(:X:) = {prod_(i=1)^n a_i | a_i in X uu X^-1, i = 1, 2, cdots, n, n in ZZ^+}`. 当 `X = {x_1, x_2, cdots, x_m}` 时, `(:X:)` 简记为 `(:x_1, x_2, cdots, x_m:)`, 特别, `(:{a}:)` 简记为 `(:a:)`. 因此 `(:a:) = {a^k | k in ZZ}`.

设群 `G = (:a:)`, 则称 `G` 是由 `a` 生成的循环群, `a` 是 `G` 的一个生成元.

设 `G` 为一群.
1. `|G| = oo` 时, `G` 的任一生成元 `a` 的阶也为无限;
2. `|G| = n` 时, `a` 是群 `G` 的生成元当且仅当 `|a| = n`.

循环群的等价条件 令 `G` 为一 `n` 阶群, 则下列几款等价:
1. `G` 为一循环群;
2. `G` 有 `n` 阶元;
3. 关于 `n` 的任意正因子 `t`, `G` 有 `t` 阶元.

显然有 1 `iff` 2, 3 `rArr` 2. 下证 1 `rArr` 3. 令 `G = (:a:)` 为一 `n` 阶循环群, 则 `|a| = n`. 关于 `n` 的任意正因子 `t`, 设 `n = s t`, `s in ZZ^+`, 则 `a^s in G`, 且 `|a^s| = t` ().

循环群的结构 令 `G = (:a:)` 为一循环群. 则
1. 当 `|a| = oo` 时, `G = {cdots, a^-3, a^-2, a^-1, e, a^1, a^2, a^3, cdots}`;
2. 当 `|a| = n` 时, `G = {e, a^1, a^2, cdots, a^(n-1)}`.

令 `(G, *)` 为一循环群, 则
1. 当 `|G| = oo` 时, `(G, *) ~= (ZZ, +)` (整数加群);
2. 当 `|G| = n` 时, `(G, *) ~= (U_n, *)` (`n` 次单位根群).
因此, 无限阶循环群是 "直线形" 的, 有限阶循环群是 "圆形" 的. 今后处理循环群时, 也可以类比为整数加群/`n` 次单位根群来处理.

1. 作 `varphi: a^m in G to m in ZZ`, 则 `varphi` 为双射, 且关于任意 `k, l in ZZ`, `varphi(a^k a^l) = varphi(a^(k+l)) = k + l = varphi(k) + varphi(l)`, 因此 `varphi` 为同构.
2. 作 `psi: a^m in G to epsi^m = "e"^((2pi m)/n"i") in U_n`, 则 `psi` 为双射, 且关于任意 `k, l in {0, 1, cdots, n-1}`, `psi(a^k a^l) = psi(a^(k+l)) = epsi^(k+l)` `= epsi^k + epsi^l = psi(a^k) psi(a^l)`, 因此 `psi` 为同构.

生成元的数目 令 `G = (:a:)` 为一循环群, 则
1. 当 `|G| = oo` 时, `G` 只有两个生成元 `a^(+-1)`;
2. 当 `|G| = n` 时, `G` 有 `varphi(n)` 个生成元. 其中 Euler 函数 `varphi(n)` 是小于等于 `n` 的正整数中与 `n` 互素的数的个数, 如 `varphi(1) = 1`.

1. 显然 `a^(+-1)` 是 `G` 的生成元. 若 `a^k` 也是生成元, `k in ZZ\\{0, +-1}`, 则存在 `m in ZZ\\{0}`, 使得 `(a^k)^m = a`. 两边同乘 `a^-1` 得 `a^(k m-1) = e`. 但 `k m -1 != 0`, 因此 `|a| lt oo`, 矛盾.
2. 只需证明 `n ge 2` 的情形. 关于任意 `a^k in G`, `0 lt k le n`, `a^k` 为 `G` 的一个生成元 `iff |a^k| = n` `iff (k, n) = 1` ().

循环群的子群

循环群的子群必为循环群. 下面给出构造性证明.

设 `G = (:a:)`, `H le G`. `|H| = 1` 的情形是平凡的. 若 `|H| ge 2`, 可取最小的正整数 `t` 使得 `a^t in H`, 则 `(:a^t:) sube H`.
反之 `AA a^k in H`, 设 `k = qt + r`, `q in ZZ`, `0 le r lt t`, 则 `a^r = a^(k-q t) = a^k a^(-q t) in H`. 由 `t` 的取法知 `r = 0`. 因此 `a^k = a^(q t) in (:a^t:)`. 即 `H sube (:a^t:)`.

关于循环群 `G = (:a:)` 的子群, 我们有:
1. 当 `|G| = oo` 时, 除平凡群是 `G` 的惟一有限子群外, `G` 有无限多个无限循环子群;
2. 当 `|G| = n` 时, 设 `n = s t`, `s, t in ZZ^+`, 则 `G` 存在惟一的 `t` 阶子群 `(:a^s:)`. 即 `n` 的每个正整数因子都与 `G` 的子群一一对应.

1. 由知, `G` 的子群都是循环群, 因此 `G` 的全部互不相同的子群为 `(:e:), (:a:), (:a^2:), cdots` 除第一个为有限群, 其它都是无限循环群.
2. 存在性: 由 `a` 是 `G` 的生成元知, `|a| = n = s t`, 因此 `|a^s| = t`. 从而 `(:a^s:)` 是 `G` 的一个 `t` 阶子群.
   惟一性: 令 `H` 也是 `G` 的一个 `t` 阶子群, 则 `H` 为循环群, 记 `H = (:a^m:)`, 则 `|a^m| = t`. 联系, `t = n/((n","m))`, 所以 `(n, m) = s`. 这推出 `s | m`, 即 `(:a^m:) sube (:a^s:)`. 又 `|(:a^m:)| = |(:a^s:)| = t`, 有 `(:a^m:) = (:a^s:)`.

Abel 群与循环群

设 `G` 为一群, `a, b in G`, 且 `a, b` 间的乘法可交换. `|a| = m`, `|b| = n`, `(m, n) = 1`, 则 `|a b| = m n`.

记 `|a b| = k`. 首先由 `(a b)^(m n) = a^(m n)b^(m n) = e e = e` 有 `k | m n`. 其次由 `b^(m k) = a^(m k) b^(m k) = (a b)^(m k) = e` 知, `n | m k`, 而 `(m, n) = 1`, 所以 `n | k`. 同理 `m | k`, 再次由 `(m, n) = 1` 得 `m n | k`.

令 `G` 为一 `n` 阶 Abel 群, `a` 为 `G` 中的最大阶元, 则对任意 `b in G`, `|b|` 整除 `|a|`.

记 `|a| = m`, `|b| = l`, 且 `l = prod_(i=1)^r p_i^(l_i)`, `quad m = prod_(i=1)^r p_i^(m_i)`. 其中 `p_i` 为两两不同的素数, `l_i`, `m_i` 是非负整数, `i = 1, 2, cdots, r`, `r in ZZ^+`. 若 `l !| m`, 则存在 `1 le k le r`, 使得 `l_k gt m_k ge 0`. 令 `l = s t`, `t = p_k^(l_k)`, `m = u v`, `v = p_k^(m_k)`. 则 `|a^v| = u`, `|b^s| = t`, `(u, t) = 1`. 当然 `a^v` 与 `b^s` 的乘法可交换, 从而 `|a^v b^s| = u t gt m`, 与 `m` 是元素的最大阶矛盾. 因此 `l | m`.

有限 Abel 群何时为循环群 显然循环群都是 Abel 群. 反之, `n` 阶 Abel 群 `G` 为循环群的充要条件是对任意正整数 `m`, `x^m = e` 在 `G` 中最多有 `m` 个解.

必要性. 令 `G` 是循环群, 对任意 `m in ZZ^+`, 记方程 `x^m = e` 的解集为 `S_m = {x in G | x^m = e}`. 任取 `a, b in S_m`, 可以验证 `a b^-1 in S_m`, 故 `S_m le G`. 而循环群的子群必为循环群, 所以可设 `S_m = (:c:)`, `c in S_m`. 而 `c^m = e`, 故 `|S_m| = |c| le m`.
充分性. 只需证 `G` 中存在 `n` 阶元. 令 `a` 为 `G` 中最大阶元, `|a| = k`, 则 `k le n`. 由, 对任意 `b in G`, 有 `|b|` 整除 `k`, 于是 `b^k = e`, 即方程 `x^k = e` 在 `G` 中至少有 `n` 个解, 由条件知 `n le k`. 于是 `n = k`, 即 `G = (:a:)`.

对称群, 置换群

设集合 `A != O/`, 记集合 `A` 上全体可逆变换的集合为 `S_A`. 容易证明 `S_A` 关于通常的变换合成为一群, 称为集合 `A` 上的对称群. `S_A` 的子群称为集合 `A` 上的置换群.
若 `A` 为有限群, `|A| = n`, 则 `A` 可以等同于 `{1, 2, cdots, n}`, `S_A` 记为 `S_n`, 称为 `n` 次对称群, 其子群称为 `n` 次置换群. `S_n` 中的元素称为 `n` 次置换, 常记为 `sigma = (1, 2, cdots, n; i_1, i_2, cdots, i_n)`. 其中 `i_j = sigma(j)`, `j = 1, 2, cdots, n`. 显然 `i_1 i_2 cdots i_n` 为 `1 2 cdots n` 的一个排列, 因此 `|S_n| = n!`.

Cayley 定理: 任一抽象群都同构于某集合上的一个置换群 令 `G` 为一群, 以 `a_l` 记元素 `a in G` 诱导的左平移变换, 则映射 `eta: G to S_G`
`a to a_l` 为一单同态, 因此 `G ~= "Im"eta le S_G`. 这里 `"Im"eta` 是 `S_G` 的子群, 由定义它是置换群.

显然该映射是良定义的. 下证它是单射. `AA a, b in G`, 若 `eta(a) = eta(b)`, 则 `a_l = b_l`, 从而关于任意 `x in G`, `a_l(x) = b_l(x)`, 即 `a x = b x`. 特别取 `x = e`, 有 `a = b`. 因此 `eta` 是单射.
又, `AA x in G`, `(a b)_l(x) = (a b) x = a (b x)` `= a_l(b_l(x)) = (a_l b_l)(x)`. 从而 `(a b)_l = a_l b_l`, 即 `eta(a b) = eta(a) eta(b)`, 即 `eta` 为一同态.

在 `eta` 的映射下, 抽象群元素 `a` 被对应到集合 `G` 上的一个具体的置换 `a_l`, 从而将群的计算化为具体置换的计算. 这个对应称为群的 Cayley 左正则表示. Cayley 定理表明了置换的重要性: 掌握了置换群, 也就从同构意义上掌握了任意一个群.

`k`-轮换

`k`-轮换 令 `sigma in S_n`, `1 le k le n`, `i_1, i_2, cdots, i_k` 是 `1, 2, cdots, n` 中 `k` 个两两不同的数, 若 `sigma(i_1) = i_2`, `sigma(i_2) = i_3`, `cdots`, `sigma(i_(k-1)) = i_k`, `sigma(i_k) = i_1`, 而其它数在 `sigma` 下不变, 则称 `sigma` 为一`k`-轮换, 记为 `sigma = (i_1 i_2 cdots i_k)`. 特别 `k = 2` 时, 称 `sigma` 为一对换. 无公共数字的轮换称为不相交的. 恒等置换 `(1, 2, cdots, n; 1, 2, cdots, n)` 通常简记为 `(1)`.

1. `(i_1 i_2 cdots i_k)^-1 = (i_k cdots i_2 i_1)`;
2. `(i_1 i_2 cdots i_k) = (i_1 i_k)(i_1 i_(k-1))cdots(i_1 i_2)`, 从而任一轮换可以分解为对换的乘积;
3. 不相交轮换的乘积是可交换的;
4. `k`-轮换的阶为 `k`.
5. `(i_1 i_2 cdots i_m) (j_1 j_2 cdots j_n)` 的阶为 `m, n` 的最小公倍数. (对吗?)

只证 4. 令 `sigma = (i_1 i_2 cdots i_k)`, 显然 `sigma^k = (1)`; 另一方面, 对任意 `1 le m lt k`, 有 `sigma^m(i_1) = i_(m+1) != i_1`, 即 `sigma^m != (1)`. 于是 `|sigma| = k`.

置换的奇偶性

置换的奇偶性 令 `sigma in S_n`. 则
1. `sigma` 可表示为若干不相交轮换的乘积, 且在不计排列顺序的意义上, 表示方式惟一;
2. `sigma` 可表示为若干对换的乘积, 且不同分解式中的对换个数的奇偶性相同. 称分解式中对换个数为奇数的置换为奇置换, 否则为偶置换.

1. 对 `n` 进行归纳证明. `n = 1` 时, 显然 `sigma = (1)`. 假设对任意小于 `n` 的正整数, `sigma` 都能分解为若干不相交轮换的乘积, 则在 `n` 的情形, 任取 `i_1 in {1, 2, cdots, n}`, 记 `i_2 = sigma(i_1)`. 接下来对 `l = 1, 2, cdots, n`, 依次处理如下: 若 `i_(l+1) != i_1`, 则定义 `i_(l+2) = sigma(i_(l+1))`; 否则就得到 `l`-轮换 `(i_1 i_2 cdots i_l)`. 容易说明 `i_1, i_2, cdots, i_l` 两两不同. 这是因为由定义, `i_1 != i_j`, `j = 1, 2, cdots, l`. 再由 `sigma` 是双射从而是单射, 就得到: 对任意 `i_j, i_k`, `1 lt j lt k le l`, 有 `i_j != i_k`. 从而我们将 `sigma` 分解成一个 `l`-轮换与一个 `n-l` 次置换的不相交的乘积, 由归纳假设后者可以分解为若干不相交轮换的乘积, 从而 `sigma` 可以分解为若干不相交轮换的乘积. (惟一性?)
2. 先将 `sigma` 分解为若干轮换的乘积, 再将轮换分解为对换的乘积即可. 下证惟一性, 设 `sigma = (1, 2, cdots, n; i_1, i_2, cdots, i_n)` `= sigma_1 sigma_2 cdots sigma_s (1)` `= tau_1 tau_2 cdots tau_t (1)`, 由于对换改变排列的奇偶性, 从而 `s, t` 的奇偶性都与排列 `i_1 i_2 cdots i_n` 的奇偶性相同, 所以 `s, t` 的奇偶性相同.

1. `k`-轮换的奇偶性与 `k` 的奇偶性相反, 因为它能分解成 `k-1` 个对换.
2. 逆置换与原置换的奇偶性相同.

`S_n` 中全体偶置换构成的集合记为 `A_n`. 则
1. `A_n le S_n`, 称 `A_n` 为 `n` 次交代群 (或交错群).
2. 对 `n ge 2`, `S_n` 中的奇置换和偶置换一样多, 于是 `|A_n| = n! // 2`.

1. 任取 `sigma, tau in A_n`, 则 `sigma tau^-1` 也能分解成偶数个对换的乘积, 因此是偶置换.
2. 记 `B = S_n \\ A_n` 为 `S_n` 中的全体奇置换. 作映射 `f: A_n to B` 和 `g: B to A_n` 如下 `f: sigma to (1 n) sigma`
   `g: tau to (1 n) tau` (`f` 在偶置换 `sigma` 的基础上再对换 `1, n`, 而 `g` 在奇置换 `tau` 的基础上再对换 `1, n`). 则 `g @ f = 1_(A_n)`, `f @ g = 1_B`. 故 `f` 为一双射. 从而 `S_n` 中的奇置换与偶置换一样多.

令 `H le S_n`, 则要么 `H` 中不含奇置换, 要么奇置换与偶置换一样多.

不妨设有奇置换 `sigma_1 in H`. 类似地作映射 `f: sigma in H nn A_n to sigma_1 sigma in H \\ A_n`
`g: tau in H \\ A_n to sigma_1^-1 tau in H nn A_n` 来证明.

对 `m le n`, `S_m` 可以看作 `S_n` 的子群, 因为 任意 `m` 次置换可以看作一个将 `m+1, cdots, n` 映射到自身的 `n` 次置换. 同理 `A_m` 可以看作 `A_n` 的子群.

1. `S_1 = {(1)}` 为平凡群;
2. `S_2 = {(1), (12)}` 为循环群;
3. 对 `n ge 3`, `S_n` 不是 Abel 群; 因为 Abel 群的子群都是 Abel 群, 我们只需举例说明 `S_3` 不是 Abel 群: 如 `(12)(123) = (23) != (13) = (123)(12)`.
4. `A_1 = A_2 = {(1)}` 为平凡群;
5. `A_3 = {(1), (123), (132)}` 为循环群.
6. 对 `n ge 4`, `A_n` 不是 Abel 群; 只需验证 `A_4` 不是 Abel 群: `(12)(34)(123) != (123)(12)(34)`.

轮换型号 将 `n` 阶置换 `sigma` 表为不相交轮换的乘积, 这些轮换中 `k`-轮换的个数记为 `l_k(sigma)`, `k = 1, 2, cdots, n`. 由于它们互不相交, 有 `n = sum_(k=1)^n l_k(sigma) * k`. 因此, `n` 阶置换所有可能的型号个数等于分拆数 `p_n`.

一般置换的阶 若置换 `sigma` 被分解为不相交的轮换, 则 `sigma` 的阶等于这些轮换的阶的最小公倍数. 由于 `k`-轮换的阶是 `k`, 我们便得到一般置换的阶的计算方法.

直观上 `sigma^n` 相当于将这些不相交轮换独立地轮转, 当所有轮换恰好复位时, 有 `sigma^n = e`. 我们来严格证明之.
??

Cauchy 公式 对称群 `S_n` 中型号为 `(l_1, l_2, cdots, l_n)` 的置换个数为 `n! // prod_(k=1)^n l_k! k^(l_k)`.

首先把 `{1, 2, cdots, n}` 分成 `l_1` 个 1-子集, `l_2` 个 2-子集, ..., `l_n` 个 `n`-子集, 方法数为 (多项系数): `c := n! // prod_(k=1)^n l_k! (k!)^(l_k)`. 然后, 由于每个 `k`-子集可产生 `(k-1)!` 个不同的轮换, 所以型号为 `(l_1, l_2, cdots, l_n)` 的置换个数为 `c * prod_(k=1)^n {:(k-1)!:}^(l_k)`, 即得结论.

`S_n` 与 `A_n` 的结构

`r`-轮换的共轭仍为 `r`-轮换 令 `pi` 为一 `n` 阶置换, `(i_1 i_2 cdots i_r)` 为一 `r` 轮换, `r le n`, 则 `pi (i_1 i_2 cdots i_r) pi^-1` `= (pi(i_1) pi(i_2) cdots pi(i_r))`.

只需证对任意 `i in {1, 2, cdots, n}`, `i` 在两个置换下的像相等. 若 `i in {pi(i_1), pi(i_2), cdots, pi(i_r)}`, 则不妨令 `i = pi(i_1)`. 从而 `pi(i_1 i_2 cdots i_r) pi^-1(i)` `= pi(i_1 i_2 cdots i_r) pi^-1 pi(i_1)` `= pi(i_1 i_2 cdots i_r) (i_1)` `= pi(i_2)` `= (pi(i_1) pi(i_2) cdots pi(i_r)) pi(i_1)` `= (pi(i_1) pi(i_2) cdots pi(i_r)) (i)`. 若 `i !in {pi(i_1, pi(i_2), cdots, pi(i_r)}`, 则 `pi^-1(i) !in {i_1, i_2, cdots, i_r}`. 从而 `pi(i_1 i_2 cdots i_r) pi^-1(i)` `= pi pi^-1(i) = i` `= (pi(i_1) pi(i_2) cdots pi(i_r))(i)`. 所以两个置换相等.

两个 `n` 阶置换具有相同型号当且仅当它们在 `S_n` 中相互共轭. 换言之, 相同型号的元素即为 `S_n` 中的一个共轭类. 共轭类的大小可以用 Cauchy 公式计算.

在共轭变换下, 每个 `k`-轮换仍变为 `k`-轮换, 故置换的型号不变. 反之若两个置换具有相同型号, 我们考察它们对应的轮换 `sigma = (i_1, i_2, cdots, i_k)` 和 `tau = (j_1, j_2, cdots, j_k)`. 只要取置换 `pi in S_n`, 使得 `pi(i_1) = j_1`, `cdots, pi(i_k) = j_k`, 就有 `pi sigma pi^-1 = tau`. 因为各个轮换不相交, 很容易将 `pi` 的定义扩展到 `{1, 2, cdots, n}` 上. 这些关于 `pi` 共轭的轮换相乘以后, 整个置换也是关于 `pi` 共轭的.

这里的结论不适用于 `S_n` 的子群. 因为当 `S_n` 中存在 `g` 使得 `a = g b g^-1` 时, 并不保证 `g` 一定在子群中.

置换群中 `k` 阶元的个数 以 `S_3` 为例, 列出 3 的所有分拆, 每个分拆对应一种轮换型号, 即一个共轭类: 3 = 1 + 1 + 1 = 1 + 2. 三个共轭类中元素的阶分别为 `lcm(1, 1, 1) = 1`, `quad lcm(1, 2) = 2`, `quad lcm(3) = 3`. 结合 Cauchy 公式知, `S_3` 有 1 个 1 阶元, 3 个 2 阶元, 2 个 3 阶元.

`S_n` 的生成元
1. 全体对换. 上面已经证明.
2. `(12), (13), cdots, (1 n)`. 这是因为 `(i j) = (1 i)(1 j)(1 i)` (利用引理, 计算时只要把中间一项的 `1` 换成 `i` 即可).
3. `(12), (23), cdots, (n-1, n)`. 这是因为 `i lt j` 时, `(i j) = (i, i+1) (i+1, j) (i, i+1)`. 利用归纳法, 最终 `(i, j)` 能化为形如 `(k, k+1)` 的对换的乘积.
4. `sigma_1, pi`. 其中 `sigma_k = (k, k+1)`, `pi = (123 cdots n)`. 这是因为 `pi sigma_1 pi^-1 = sigma_2`.

`A_n` 的生成元
1. 全体 `3`-轮换. 证明在后面.
2. `(123)(124)(12n)`. 这是因为 `(i j k) = (1 i j)(1 i k)(1 i j)^-1`, `(1 i j) = (1 2 j)^-1(1 2 i)(1 2 j)`.
3. `(123), (234), (n-2,n-1,n)`. 这是因为 `(1 2 i) = (i-1,i,i+1) (1,2,i-1) (i-1,i,i+1)^-1`. 利用归纳法, 最终 `(1 2 i)` 能化为形如 `(k-1,k,k+1)` 的对换的乘积.
4. `(123), (123 cdots n), if n " is odd"`;
   `(123), (23 cdots n), if n " is even"`.

`n ge 3` 时, 偶置换群 `A_n` 由所有 `3`-轮换生成. (`n = 1, 2` 时, 显然 `A_n` 为平凡群)

任取 `sigma in A_n`, 只需证 `sigma` 可以分解为 `3`-轮换的乘积. 若 `sigma = (1)`, 则 `sigma = (123)^3`. 若 `sigma != (1)`, 则 `sigma` 至少是两个不同对换的乘积, 即 `sigma` 可以分解为形如 `(a b)(a c)` 或 `(a b)(c d)` 的置换之积, 其中 `a, b, c, d in {1, 2, cdots, n}` 且两两不同. 又 `(a b)(a c) = (a c b)`,
`(a b)(c d) = (a b)(b c)(b c)(c d) = (b c a)(c d b)`, 因此 `sigma` 可分解为 `3`-轮换的乘积.

对 `n != 2`, `S_n` 的中心是平凡群 `{(1)}`. 对 `n != 3`, `A_n` 的中心也是平凡群. `S_2, A_3` 是循环群, 中心分别是它们自己.

1. 令 `pi in Z(S_3)`, 则 `pi` 与 `(12), (13)` 都可换. 于是 `(pi(1) pi(2)) = pi (12) pi^-1 = (12) pi pi^-1 = (12)`. 这推出 `pi in (:(12):)`. 同理 `pi in (:(13):)`, 故 `pi = (1)`. `S_3` 是 `S_(n ge 3)` 的子群, 所以 `S_(n ge 3)` 也只有平凡的中心.
2. 若 `pi in Z(A_4)`, 则它与 `(123), (124)` 都可换. 我们得到 `(pi(1) pi(2) pi(3)) = pi(123)pi^-1 = (123)`, 这指出 `pi in (:(123):)`. 同理 `pi in (:(124):)`, 因此 `pi = (1)`.
   注: 由第四章的内容, `A_5` 及以上的交代群是单群, 只有平凡的正规子群, 故只有平凡的中心.

正多面体的对称性群 此概念是二面体群的扩展. 在空间中, 所有使一个正多面体与自身重合的刚体运动构成这个正多面体的对称性群.
1. 立方体和正八面体的对称性群是 `S_4`, 相当于其 4 条对角线的任意置换;
2. 正四面体的对称性群是 `A_4`, 通过将正四面体内接于一个正方体可以看出这一点;
3. 正十二面体和正二十面体的对称性群是 `A_5` (足球烯).