《应用近世代数》学习笔记

自学笔记，那就是自学笔记，只记一些比较主干的定理和证明，或许时不时穿插点自己的感想。

引言与预备知识

集合与映射

集合所采用的符号和先前并无太大差距，除了余集（补集）本书采用的符号为：

$$ A' = \overline{A} := U\backslash A $$

对称差采用的符号为：

A△B := (A∖B) ∪ (B∖A)

集合的部分运算性质 trivial，略去。

Theorem 1.1 (Inclusion & Exclusion Principle) 容斥原理表述为：

$$ \begin{aligned} \left|\bigcup_{i = 1}^n A_i\right| &= \sum_{k = 1}^n (-1)^{k-1}\sum_{1\leq i_1 < i_2 < \cdots < i_k\leq n}\left|\bigcap_{j = 1}^k A_{i_j}\right| \\ &= \sum_{i = 1}^n |A_i| - \sum_{1\leq i < j\leq n}|A_i\cap A_j| + \sum_{1\leq i < j < k\leq n}|A_i\cap A_j\cap A_k| - \cdots + (-1)^{n-1}\left|\bigcap_{i = 1}^n A_i\right| \end{aligned} $$

证明据对 n 的归纳法平凡，略去。

映射相关的基本定义和概念与先前一致。

Definition 1.1 若集合 A, B 间存在一个双射，则称 A, B 等势。与自然数集 ℕ⁺ 等势的无限集称为可数集，否则称为不可数集。

Theorem 1.2 已知映射 f : A → B，我们有：

• f 有左逆等价于 f 是单射
• f 有右逆等价于 f 是满射
• f 有逆等价于 f 是双射

证明从略。

二元关系

集合 A, B 上的一个二元关系 R 是笛卡尔积 A × B 的子集，a ∈ A, b ∈ B 具有关系 R 定义为 (a,b) ∈ R。

等价关系、等价类、代表元的定义从略，不难有任何集合上的等价关系与集合的划分一一对应。

Definition 1.2 已知集合 A 上的等价关系 ∼，定义 A 对 ∼ 的商集为等价类构成的集合：

$$ A/\sim := \{\overline{a} : a \in A\} $$

Definition 1.3 (Partially & Totally Ordered Set) 如果集合 S 上存在一个二元关系 ≤ 满足：

• 对任意 x ∈ S 都有 x ≤ x
• 对任意 x, y ∈ S，只要 x ≤ y 且 y ≤ x 就有 x = y
• 对任意 x, y, z ∈ S，只要 x ≤ y 且 y ≤ z 就有 x ≤ z

则称 ≤ 是 S 上的一个偏序，(S,≤) 为偏序集。

如果偏序集 (S,≤) 还满足：

• 对任意 x, y ∈ S 都有 x ≤ y 或 y ≤ x

则称 ≤ 是 S 上的一个全序，(S,≤) 为全序集。

一个偏序集总是可以用 Hasse 图表示，Hasse 图是一个无向图，其顶点集为 S，边集为 $\{(x, y) : x < y, (\not\exists u)x < u < y\}$。

Definition 1.4 在偏序集 (S,≤) 上定义：

• 若存在 a ∈ S 满足任意 x ∈ S 都有 x ≤ a，则 a 是 S 的最大元，同理定义最小元
• 若存在 a ∈ S 满足只要 x ≥ a 就有 x = a，则 a 是 S 的极大元，同理定义极小元
• 对 T ⊆ S，若存在 a ∈ S 满足任意 x ∈ T 都有 x ≤ a，则 a 是 T 的上界，同理定义下界
• 对 T ⊆ S，若存在 T 的某个上界 a，令 T 的任意上界 a′ 都有 a ≤ a′，则 a 是 T 的最小上界，同理定义最大下界

Definition 1.5 (Well Ordered Set) 如果全序集 (S,≤) 满足对任意 T ⊆ S, T ≠ ⌀ 都有 T 具有最小元，那么该全序集为良序集。

整数集 ℤ 在一般的整数序意义上不良序，例如取负整数集 ℤ⁻ ⊆ ℤ，而负整数集不具有最小元。

良序性保证了数学归纳法的有效性，或者说数学归纳法可以应用在任意良序集上：

Theorem 1.3 已知 M ⊆ ℤ⁺，若有 1 ∈ M，并且只要有 n − 1 ∈ M 就有 n ∈ M，那么 M = ℤ⁺。

【证明】利用反证法，据 ℤ⁺ 的良序性，取 N = ℤ⁺ ∖ M ≠ ⌀，N 具有最小元 a。由 1 ∈ M 得到 a ≠ 1，所以 a − 1 ∈ ℤ⁺。据 a − 1 < a 和 a 在 N 中的最小性得到 a − 1 ∈ M，因而得到 a ∈ M，矛盾。◼

整数与同余方程

整数的带余除法、素因子分解这里不赘述。

Theorem 1.4 (Bezout Theorem) 对不全为零的整数 a, b，其最大公因数为 d，那么存在 p, q ∈ ℤ 令 pa + qb = d。

证明方式为证明 min {pa + qb ∈ ℤ⁺ : p, q ∈ ℤ} = d，这里略去。

我感觉本质就在 aℤ + bℤ 依然是整数的子群，而 d 是 aℤ + bℤ 的最小正元素。

Definition 1.6 (Euler Function) 对正整数 n，定义 φ(n) 为小于 n 且与 n 互素的正整数的个数。不难据容斥原理计算得到：

$$ \varphi(n) = n\prod_{p\mid n}\left(1 - \frac{1}{p}\right) $$

Theorem 1.5 一次同余方程 $ax \equiv b (\mathop{\rm mod} m), m \nmid a$ 有解的充要条件为 (a,m) ∣ b。

【证明】若方程有解 x，则存在 y ∈ ℤ 有 ax + ym = b，据 Bezout 定理得到 (a,m) ∣ b。

若 (a,m) ∣ b，分别记 a = a₁(a,m), m = m₁(a,m), b = b₁(a,m)，这里我们显然有 (a₁,m₁) = 1，从而据 Bezout 定理得到存在 r, s ∈ ℤ 有 ra₁ + sm₁ = 1，从而 ra₁b₁ + sm₁b₁ = b₁，即：

$$ ra_1b_1 \equiv b_1 (\mathop{\rm mod} m_1) $$

考虑原方程，根据下述等价推理：

$$ \begin{aligned} &ax \equiv b(\mathop{\rm mod} m) \\ \iff &a_1(a, m)x - b_1(a, m) = km_1(a, m), k \in \mathbb{Z} \\ \iff &a_1x - b_1 = km_1, k \in \mathbb{Z} \\ \iff &a_1x \equiv b_1(\mathop{\rm mod} m_1) \\ \end{aligned} $$

从而我们已经得到了原方程的一个解 x = rb₁，从而我们可以得到原方程的所有解 x = rb₁ + lm₁，这里 l ∈ ℤ。◼

Theorem 1.6 (Chinese Remainder Theorem) 同余方程组

$$ \begin{cases} x\equiv a_1(\mathop{\rm mod} m_1) \\ x\equiv a_2(\mathop{\rm mod} m_2) \\ \vdots \\ x\equiv a_n(\mathop{\rm mod} m_n) \end{cases} $$

满足 m_i 两两互素，那么其解的形式为：

$$ x \equiv \sum_{i = 1}^n a_ic_iM_i(\mathop{\rm mod} M) $$

其中 M = m₁m₂⋯m_n，并且 $M_i = \dfrac{M}{m_i}$，并且 c_i 是同余方程 $M_ix \equiv 1(\mathop{\rm mod} m_i)$ 的一个解。

【证明】首先对任意满足：

$$ x \equiv \sum_{i = 1}^n a_ic_iM_i(\mathop{\rm mod} M) $$

的 x，我们逐一验证其满足原同余方程：

$$ x = kM + \sum_{i = 1}^n a_ic_iM_i = m_p\left(kM_p + \sum_{i \neq p}a_ic_i\frac{M_i}{m_p}\right) + a_pc_pM_p \equiv a_pc_pM_p(\mathop{\rm mod} m_p) $$

据 $M_pc_p \equiv 1(\mathop{\rm mod} m_p)$ 即验证完毕。

之后证明同余方程组任意解都满足上述形式。取任意一个解 y，由于我们验证了所有满足上述形式的 x 都是方程组的解，我们任取其中一个 x，总有 $x \equiv y (\mathop{\rm mod} m_p) \iff x - y \mid m_p$。据 m_p 之间互素，不难得到 x − y ∣ M，证明完毕。◼

群

基本概念

Definition 2.1 (Group) 在集合 G 上定义了一个二元运算  ⋅  : G² → G，若满足：

• 结合律：对任意 a, b, c ∈ G，有 (ab)c = a(bc)

那么称 (G,⋅) 为一个半群。如果还满足：

• 单位元：存在 e ∈ G 使得对任意 a ∈ G 都有 ea = ae = a

那么称 (G,⋅) 为一个幺半群。如果还满足：

• 逆元：对任意 a ∈ G 都存在 a⁻¹ ∈ G 使得 aa⁻¹ = a⁻¹a = e

那么称 (G,⋅) 为一个群。如果还满足：

• 交换律：对任意 a, b ∈ G 都有 ab = ba

那么称 (G,⋅) 为一个交换群（Abel 群）。

有限群、无限群、群的阶的概念这里不表述。

关于半群，我们有下述性质：

Theorem 2.1 在半群 (G,⋅) 内定义左右单位元 $e_{\rm L}, e_{\rm R}$。如果一个半群同时具有左右单位元，则 G 的左右单位元相等，均为 G 的单位元且单位元唯一。

仅需考虑乘积 $e_{\rm L}e_{\rm R}$ 即可证明单位元相等。单位元唯一性则根据反证法，假定有两个单位元 e_1, 2，考虑乘积 e₁e₂ 即可。◼

Theorem 2.2 在幺半群 (G,⋅) 内对 a ∈ G 定义左右逆 $a_{\rm L}^{-1}, a_{\rm R}^{-1}$。如果一个幺半群的某元素同时具有左右逆，则其左右逆相等，均为其逆元且逆元唯一。

左右逆相等根据下述计算保证：

$$ a_{\rm L}^{-1} = a_{\rm L}^{-1}e = a_{\rm L}^{-1}(aa_{\rm R}^{-1}) = (a_{\rm L}^{-1}a)a_{\rm R}^{-1} = ea_{\rm R}^{-1} = a_{\rm R}^{-1} $$

逆元的唯一性根据下述计算保证，假定 a 有两个逆元 a_1, 2⁻¹：

a₁⁻¹ = a₁⁻¹e = a₁⁻¹(aa₂⁻¹) = (a₁⁻¹a)a₂⁻¹ = ea₂⁻¹ = a₂⁻¹

◼

上述定理保证的事情大概可以描述为，一个非含幺的半群，单位元不能“左右开弓”，否则必可得到唯一单位元，一个非群的幺半群，逆元不能“左右开弓”，否则必可得到唯一逆元。当然和非含幺的半群一旦“左右开弓”就能升格为幺半群不一样，非群的幺半群内逆元“左右开弓”仅限于具体的元素，要升格为群还是需要所有的元素都具有逆。

之后我们需要指出半群升格为群的一些条件：

Theorem 2.3 半群 (G,⋅) 满足下述两个条件时即为群：

• 左单位元：存在 $e_{\rm L} \in G$，对任意 a ∈ G 都有 $e_{\rm L}a = a$
• 对左单位元的左逆元：对任意 a ∈ G 都存在 $a_{\rm LL}^{-1} \in G$ 使得 $a_{\rm LL}^{-1}a = e_{\rm L}$

首先证明对左单位元的左逆元也是对左单位元的右逆元。取 $a_{\rm LL}^{-1}$ 的左逆 $(a_{\rm LL}^{-1})_{\rm LL}^{-1}$，那么：

$$ aa_{\rm LL}^{-1} = e_{\rm L}aa_{\rm LL}^{-1} = (a_{\rm LL}^{-1})_{\rm LL}^{-1}(a_{\rm LL}^{-1}a)a_{\rm LL}^{-1} = (a_{\rm LL}^{-1})_{\rm LL}^{-1}(e_{\rm L}a_{\rm LL}^{-1}) = e_{\rm L} $$

则现在将任意 a ∈ G 对 $e_{\rm L}$ 的逆记作 $a_{\rm BL}^{-1}$。

下面只需要说明左单位元也是右单位元，则不难得到该半群是群。考虑下述运算：

$$ ae_{\rm L} = a(a_{\rm BL}^{-1}a) = (aa_{\rm BL}^{-1})a = e_{\rm L}a = a $$

据此证明完毕。◼

这个定理说明了半群升格为群并不需要单位元和逆左右同时满足，只需要满足一侧即可。

在此基础上我们可以得到更通用的半群升格为群的条件：

Theorem 2.4 半群 (G,⋅) 满足对 a, b ∈ G，方程 ax = b, xa = b 都有解时为群。

首先证明左单位元存在。任取一 g，取 xg = g 的解 $e_{\rm L}$。之后任取 a，取 gx = a 的解 b，则：

$$ e_{\rm L}a = e_{\rm L}(gb) = (e_{\rm L}g)b = gb = a $$

左逆元根据 $xa = e_{\rm L}$ 总有解保证。◼

Theorem 2.4 有限半群 (G,⋅) 满足左右消去律时为群：

$$ \begin{cases} xa = ya \Rightarrow x = y \\ ax = ay \Rightarrow x = y \\ \end{cases} $$

取集合 aG = {ax : x ∈ G}，显然 aG ⊆ G。由于 ax = ay ⇔ x = y，说明 |aG| = |G|，得到 aG = G。这说明 ax = b 总有解。同理 xa = b 总有解，证明完毕。◼

记几个重要的群：

• GL_n(F) 是数域 F 上所有 n 阶可逆线性变换对变换复合构成的群
• S_A 是所有可逆的 f : A → A 对映射复合构成的群，称为 A 上的对称群

子群