近世代数预备知识

集合

集合

集合是具有一定属性的事务组成的整体

属于

如果 $a$ 是集合 $A$ 的元素，那么称 $a$ 属于 $A$。记为 $a \in A$。对于任意的一个元素 $x$，一定有 $x \in A$ 或 $x \notin A$。

子集与真子集

如果一个集合 $A$ 每一个元素都属于另一个集合 $B$，那么称 $A$ 是 $B$ 的子集，记为 $A \subseteq B$。而如果 $B$ 中至少存在一个元素不属于 $A$，那么称 $A$ 是 $B$ 的真子集，记为 $A \subset B$。

相等

如果 $A$ 和 $B$ 是两个集合，$A=B$ 读作 $A$ 等于 $B$，表示他们是由相同的元素构成的集合。也即 $A$ 中的每一个元素都属于 $B$，$B$ 中的每一个元素也都属于 $A$

单纯的子集，可能包含相等的可能性。如果需要证明 $A=B$，只需要证明 $A \subseteq B$ 且 $B \subseteq A$

常用的集合如下：

幂集

集合 $S$ 的幂集指由 $S$ 的全体子集组成的集合，记为 $2^S$。

集合 $A=\{1,2,3\}$ 的幂集为 $2^A=\{\empty,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

全集与补集

全集 $I$ 通常指研究的元素总体。其他研究范围内的集合都应该属于全集，$A \subseteq I$。而其中部署于集合 $A$ 的部分，称为集合 $A$ 在全集 $I$ 中的补集 $\overline{A}$

$\overline{\overline{A}}=A$

集合的运算

并运算

所有属于 $A$ 或属于 $B$ 构成的集合称为集合的并集，记为 $A \bigcup B$。也即 $A \bigcup B=\{x|x\in A \text{ 或 } x \in B \}$

并运算有如下性质：

1. $A \bigcup A = A$
2. $A \bigcup \empty = =A$
3. $A \subseteq B \Leftrightarrow A \bigcup B = B$
4. $A \bigcup \overline{A} = I$

多个集合的并，可记为 $W = A_1 \bigcup A_2 \bigcup \cdots \bigcup A_n = \bigcup^n_{n=1}{A_i}$

交运算

由 $A$ 和 $B$ 共同元素构成的集合，称为 $A$ 和 $B$ 的交集，记为 $A \bigcap B$。也即 $A \bigcap B = \{x|x\in A \text{ 且 } x \in B\}$

交运算有如下性质：

1. $A \bigcap A = A$
2. $A \bigcap \empty = \empty$
3. $A \subseteq B \Leftrightarrow A \bigcap B = A$
4. $A \bigcap \overline{A} = \empty$

差运算

$A-B$ 称为 $A$ 和 $B$ 的差集，定义为 $A-B=\{x|x \in A \text{ 且 } x \notin B\}$

运算定理

对于任意的集合 $A$、$B$、$C$，$*$ 表示 $\bigcup$ 或 $\bigcap$，则有

1. $A*A=A$ (等幂律)
2. $A*B=B*A$ (交换律)
3. $A*(B*C)=(A*B)*C$ (结合律)
4. $A \bigcup \empty = A$
5. $A \bigcup I = I$
6. $A \bigcap \empty = \empty$
7. $A \bigcap I = A$
8. $A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)$ (分配律)
9. $A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)$ (分配律)
10. $A \bigcap (A \bigcup B) = A$ (吸收律)
11. $A \bigcup (A \bigcap B) = A$ (吸收律)

笛卡尔积

设 $A_1,A_2,\cdots,A_n$ 是 $n$ 个集合，则他们的笛卡尔积为 $A_1 \times A_2 \times \cdots \times A_n = \{(a_1,a_2,\cdots,a_n)|a_i \in A_i\}$
也即从各个集合按顺序取出元素构成的元素组作为新元素组成的集合

如 $A=\{1,2,3\}$ 和 $B=\{4,5\}$ 的笛卡尔积有：
$A \times B = \{(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)\}$
$B \times A = \{(4,1),(4,2),(4,3),(5,1),(5,2),(5,3)\}$

集合元素计数

集合中元素的数量，称为集合的元素计数。使用 $|A|$ 或 $\#A$ 表示集合 $A$ 的元素个数

摩根律

$\overline{A_1 \bigcup A_2 \bigcup \cdots \bigcup A_n} = \overline{A_1} \bigcap \overline{A_2} \bigcap \cdots \bigcap \overline{A_n}$

$\overline{A_1 \bigcap A_2 \bigcap \cdots \bigcap A_n} = \overline{A_1} \bigcup \overline{A_2} \bigcup \cdots \bigcup \overline{A_n}$

容斥原理

$|A \bigcup B| = |A| + |B| - |A \bigcap B|$

使用容斥原理可以较为方便地计算元素个数

对于容斥原理，其推广出完整公式为：
$\begin{aligned}|A_1 \bigcup A_2 \bigcup \cdots \bigcup A_n| = &\quad \sum^n_{i=1}{|A_i|} \\&- \sum^n_{i=1}\sum_{j>i}{|A_i \bigcap A_j|} \\&+ \sum^n_{i=1}\sum_{j>i}\sum_{k>j}{|A_i \bigcap A_j \bigcap A_k|} \\&- \cdots \\&+ (-1)^{n-1}|A_i \bigcap A_j \bigcap \cdots \bigcap A_n|\end{aligned}$

结合 $|\overline{A}|=N-|A|$ 即可简化某些情况下的元素个数计算

容斥原理在使用时，存在两种不同的情况：

1. 求 $|A \bigcup B| = ?$，与结论顺着设
2. 求 $|\overline{A} \bigcap \overline{B}| = ?$，与结论返着设

如：求 a,b,c,d,e,f 六个字母的全排列，要求不能出现 ace 和 df 的排列有多少。
从题目可见要求为 不能出现，以及 ace 和 df
也即，同时满足两种条件，对应的应该为交集形式，也即第二种，应该返着设（设出现的情况）。
因此，应该设 $A$ 为 ace 作为一体出现的集合，$B$ 为 df 作为一体出现的集合

二元关系

对于集合 $A$ 和 $B$，$A \times B$ 的子集 $R$ 称为 $A$ 和 $B$ 的一个二元关系。对于 $a \in A, b \in B, (a,b) \in R$，称为 $a$、$b$ 具有关系 $R$，记作 $aRb$（如果 $a$ 和 $b$ 没有关系，则记为 $aR'b$）

可以将其视为运算 $R$ 的查表法，将所有 $A$、$B$ 存在关系的情况进行枚举

等价关系

如果二元关系满足如下关系，则称为等价关系，记为 $\sim$

• 反身性: $\forall a \in A, aRa$
• 对称性: $aRb \Rightarrow bRa$
• 传递性: $aRb,bRc \Rightarrow aRc$

针对这三种关系，应该更多去理解不满足的情况。
如小于关系，实际上是指 $R = \{(x,y)|x \lt y\}$。在这种集合中 $(a,a) \notin R$，同时对于 $(a,b) \in R$ 则必然 $(b,a) \notin R$。因而其不满足反身性与对称性。

而假设有这样的集合，同时上同一门课的人称为同学，而由于每一个人会选多门课，拥有多个同学。但同学和同学之间，可能并不会选同一门课，也即“同学的同学不一定是你的同学”，这也即不存在传递性。

任何两个元素都可以有很多关系，但等价关系则表明元素之间拥有更多的限制，有着更多的相似点。

要证明等价关系只需要分别证明满足三点约束即可，如下面一道题：

等价类

利用等价关系可以对集合进行分类。如果将集合 $A$ 分成若干个 $A$ 的子集，使得 $A$ 的每一个元素都属于且只属于一个类，则这些类的全体称为 $A$ 的一个分类。

类中的任意一个元素都可以作为这个类的代表

如整数集的根据模 $4$ 剩余关系，可以将所有整数分为 $4$ 类。

等价类

如果分类中所有的元素都存在等价关系 $[a] = \{x|x \in A,x \sim a\}$，则称其为等价类

模 $n$ 剩余类

根据模 $n$ 同余关系 $a \equiv b \mod n$ 进行分类

对于 $n$ 个元，他们除以 $n$ 余数分别为 $0,1,\cdots,n-1$，这些类分别记为 $[0],[1],\cdots,[n-1]$

等价类存在如下定理：

1. 若 $a,b \in A$，$a \sim b$，则 $[a]=[b]$
2. $\forall a,b \in A, a \nsim b$，则 $[a] \bigcap [b] = \empty$
3. $A$ 可以写成所有不同等价类的并，即 $A=[a_1] \bigcup [a_2] \cdots \bigcup [a_n]$

映射

$\forall x \in A$，如果通过法则 $f$，存在一个唯一的 $y \in D$，则称 $f$ 是 $A$ 到 $D$ 的一个映射，记为 $f: A \rightarrow D$。$x \rightarrow y = f(x)$。其中，$x$ 称为原像，$y$ 称为像

$A$ 的每一个元在 $D$ 中都应该有唯一对应的像：

1. 集合 $A_1,A_2,\cdots,A_n,D$ 可以相同
2. $A_1,A_2,\cdots,A_n$ 的次序不能调换
3. 映射一定要替每一个元规定一个像
4. 一个元只能由一个唯一的像
5. 所有的像都必须是 $D$ 的元

如果需要证明两个映射相同，只需要证明：
$\phi_1: A \rightarrow D$
$\phi_2: A \rightarrow D$
$\forall a \in A, \phi_1(a) = \phi_2(a)$
则 $\phi_1 = \phi_2$

满射

$f: A \rightarrow B, \forall b \in B, \exist a \in A,f(a)=b$，则称映射 $f$ 是一个 $A$ 到 $B$ 的满射

在满射中，$B$ 中的每一个像都有对应的原像（所有像都被映射）

单射

$a \ne b \Rightarrow f(a) \ne f(b)$，则称映射 $f$ 是一个 $A$ 到 $B$ 的一个单射

在单射中，不同原像的像一定不同（所有像都被单一的原像映射）

双射（一一映射）

满射 + 单射

对于 $|A| = n, |B| = m$，有：

• 映射 $f$ 有 $m^n$ 个
• 单射 $f$ 有 $m(m-1)\cdots(m-n+1)$ 个（$n \le m$）
• 双射 $f$ 有 $m!$ 个（$n = m$）
• 满射 $f$ 有 $m^n-\begin{pmatrix}m\\1\end{pmatrix}(m-1)^n+\begin{pmatrix}m\\2\end{pmatrix}(m-2)^n-\cdots+(-1)^{m-1}\begin{pmatrix}m\\m-1\end{pmatrix}$ 个（$n \le m$）

代数运算

$A \times B \rightarrow D$ 的映射称为 $A \times B$ 到 $D$ 的代数运算。
$\circ: (a,b) \rightarrow d = \circ(a,b)$
也可将其写成 $a \circ b$

可以采用运算表来表示代数运算的运算关系

对于 $A \times A \rightarrow A, (|A|=n)$ 有 $n^{n^2}$ 种二元运算

如果 $\circ$ 和 $\overline{\circ}$ 分别是 $A$ 和 $\overline{A}$ 的代数运算，如果 $\forall a,b \in A$，只要 $a \rightarrow \overline{a}, b \rightarrow \overline{b}$，有 $a \circ b \rightarrow \overline{a} \circ \overline{b}$，则 $\phi$ 是 $A$ 到 $\overline{A}$ 的同态映射

若 $\circ$ 和 $\overline{\circ}$ 有一个 $A$ 到 $\overline{A}$ 满射的同态映射，则 $A$ 和 $\overline{A}$ 同态。

$S$ 和 $T$ 同态，则 $S$ 和 $T$ 满射
$S$ 和 $T$ 的同态映射 $f$ 是 $S \rightarrow T$ 的单射，$f$ 为 $S \rightarrow T$ 的单一同态
$S$ 和 $T$ 的同态映射 $f$ 是 $S \rightarrow T$ 的满射，$f$ 为 $S \rightarrow T$ 的满同态，记为 $S \sim T$
$S$ 和 $T$ 的同态映射 $f$ 是 $S \rightarrow T$ 的双射，$f$ 为 $S \rightarrow T$ 的同构映射，记为 $S \cong T$

同构映射表示两个代数系统拥有相同的结构，本质上相同

运算律

代数运算拥有如下运算律：

• 结合律: $(a \circ b) \circ c = a \circ (b \circ c)$
• 交换律: $a \circ b = b \circ c$
• 分配律: $(a \otimes b) \oplus (a \otimes c) = a \otimes (b \otimes c)$

代数系统 $(S,\circ)$ 和 $(T,*)$，设 $f$ 是 $S \rightarrow T$ 的满同态：

1. 若 $\circ$ 满足结合律，则 $*$ 也满足
2. 若 $\circ$ 满足交换律，则 $*$ 也满足
3. 若 $\circ$ 满足（左右）分配律，则 $*$ 也满足

同构

$\phi$ 是 $A$ 到 $\overline{A}$ 的一一映射，$\circ$ 和 $\overline{\circ}$ 分别是 $A$ 和 $\overline{A}$ 代数运算，如果 $\forall a,b \in A$，只要 $a \rightarrow \overline{a}, b \rightarrow \overline{b}$，则有 $a \circ b \rightarrow \overline{a} \overline{\circ} \overline{b}$。那么，$\phi$ 是 $A$ 与 $\overline{A}$ 的同构映射

如果 $A \rightarrow A$ 存在同构映射，那么称其为自同构: $\phi(x \circ y) = \phi(x) \circ \phi(y)$

同态和同构的代数系统拥有保持运算的特性，即在一个系统进行运算，可以在另一个系统也有等效的效果。最直接的应用为同态加密，用户拥有数据，服务端拥有某种运算。用户将加密后的数据发送到服务端，由服务端进行运算，并将运算后的数据发回用户，并由用户解密。在整个过程中，用户的明文未泄露，服务端的运算也未泄露，但仍然对原文执行了确定的运算