群、子群与陪集
群的定义
- 半群：设 $V = \langle S, \circ \rangle$ 是一个代数系统，若 $\circ$ 是可结合的，则称 $V$ 是一个半群。
- 独异点：设 $V = \langle S, \circ \rangle$ 是一个半群，若 $V$ 中存在单位元 $e$，则称 $V$ 是一个含幺半群，也称为独异点。
- 群：设 $V = \langle S, \circ \rangle$ 独异点，若 $V$ 中任意元素 $a$ 都有逆元，则称 $V$ 是一个群，通常将群记作 $G$。
实例：
- $\langle \mathbb{Z}^+, + \rangle$ 是半群
- $\langle \mathbb{N}, + \rangle$ 是含幺半群
- $\langle \mathbb{Z}, + \rangle$ 是群
- Klein 四元群 $G = \lbrace e, a, b, c \rbrace$，满足交换律，每个元素都是自己的逆元，$a, b, c$ 中任意两个元素的运算结果都是第三个元素。
有关群的术语与性质
-
有限群：群 $G$ 是有限集。
-
群的阶：群 $G$ 的 基数 称为 $G$ 的阶，记作 $|G|$。
-
平凡群：只有一个元素的群。（即只含单位元的群）
-
阿贝尔群：满足交换律的群，也称为交换群。
-
元素的幂：设 $a \in G, n \in \mathbb{Z}$，定义 $a^n$ 为：$a^n = \begin{cases} a^{n -1} a & n > 0 \newline e & n = 0 \newline (a^{-1})^n & n < 0 \end{cases}$
-
元素的阶：设 $a \in G$，若存在最小的正整数 $n$ 使得 $a^n = e$，则称 $n$ 为 $a$ 的阶，称 $a$ 为 $n$ 阶元，若不存在这样的 $n$，称 $a$ 为无限阶元。
- $e$ 是 $\color{cyan}1$ 阶元
幂运算的性质
- $\forall a \in G, \left(a^{-1}\right)^{-1} = a$
- $\forall a, b \in G, (ab)^{-1} = b^{-1} a^{-1}$
- $\forall a \in G, a^n a^m = a^{n + m}$
- $\forall a \in G, (a^n)^m = a^{nm}$
- $G 是交换群 \Rightarrow \forall a, b \in G, (ab)^n = a^n b^n$
阶的性质
- $\forall a \in G, a^k = e \Rightarrow |a| | k$
- $\forall a \in G, |a| = |a^{-1}|$
- $a, b \in G 且是有限阶元 \left|b^{-1} a b\right| = |a|$
消去律
$a, b, c \in G$
- $ab = ac \Rightarrow b = c$
- $ba = ca \Rightarrow b = c$
$$G = {a_1, a_2, \cdots, a_n}, a_iG = \lbrace a_i a_j \ | \ a_j \in G \rbrace = G$$
设群 $G$ 为有限群，则 $G$ 中阶大于 $2$ 的元素有偶数个。
- 若 $a^2 = e$，则 $a = a^{-1}$
- 故 $G$ 中阶大于 $2$ 的元素要成对出现。
$\forall x, b \in G$, 方程 $ax = b$ 和 $ya = b$ 在 $G$ 中存在唯一解。
无零元
若 $G$ 中存在零元 $\theta$，则有 $\forall x \in G, x \theta = \theta x = \theta \neq x$，故 $G$ 中不存在零元。
子群与群的陪集分解
子群
设 $G$ 是一个群，若 $H$ 是 $G$ 的一个非空子集，且 $H$ 对 $G$ 的运算构成一个群，则称 $H$ 是 $G$ 的一个子群，记作 $H \leq G$。 若 $H$ 是 $G$ 的子群，且 $H \neq G$，则称 $H$ 是 $G$ 的真子群，记作 $H < G$。
对任何群 $G$ 都存在子群。$G$ 和 $\lbrace e \rbrace$ 都是 $G$ 的子群，称为 $G$ 的平凡子群。
子群的判定
- 使用定义验证：
- $\forall a, b \in H, ab \in H$
- $\forall a \in H, a^{-1} \in H$
- $H \neq \varnothing, \forall a, b \in H, ab^{-1} \in H$
- $H \neq \varnothing$，且 $H$ 是有穷的，$\forall a, b \in H, ab \in H$
生成子群
设 $G$ 是一个群，$a \in G$，令 $H = \lbrace a^k \ | \ k \in \mathbb{Z} \rbrace$，则 $H$ 是 $G$ 的一个子群，称 $H$ 是由 $a$ 生成的子群，记作 $H = \langle a \rangle$。
由子集生成的子群
$B \subseteq G$ $$\langle B \rangle = \bigcap \lbrace H \ | \ B \subseteq H \land H \leq G \rbrace$$
中心
$$C = \lbrace a \in G \ | \ \forall x \in G, ax = xa \rbrace$$ 称 $C$ 为 $G$ 的中心，$C$ 是 $G$ 的一个子群。
子群的并和交
设 $G$ 是一个群，$H_1, H_2$ 是 $G$ 的两个子群，则
- $H_1 \cap H_2$ 是 $G$ 的子群
- $H_1 \cup H_2$ 当且仅当 $H_1 \subseteq H_2$ 或 $H_2 \subseteq H_1$ 时是 $G$ 的子群
子群格
$$L(G) = \lbrace H \ | \ H \leq G \rbrace$$ 则偏序集 $\langle L(G), \subseteq \rangle$ 称为 $G$ 的子群格。
子群格陪集
有 $a \in G, H \leq G$
- $Ha = \lbrace ha \ | \ h \in H \rbrace$ 称为 $H$ 的右陪集
- $aH = \lbrace ah \ | \ h \in H \rbrace$ 称为 $H$ 的左陪集
下面主要讨论右陪集。
$a$ 为 $Ha$ 或 $aH$ 的代表元素。
陪集的性质
- $H = H$
- $\forall a \in G, a \in Ha$
- $a \in Hb \Leftrightarrow ab^{-1} \in H \Leftrightarrow Ha = Hb$
定义等价关系 $R$： $$aRb \Leftrightarrow a \in Hb \Leftrightarrow ab^{-1} \in H$$ $$[a]_R = Ha$$
- $\forall a, b \in G, Ha = Hb \overline{\lor} Ha \cap Hb = \varnothing$
- $\bigcup \lbrace Ha \ | \ a \in G \rbrace = G$
- $H \approx Ha$，即 $|H| = |Ha|$
- 正规子群：若 $H$ 是 $G$ 的子群，且 $\forall a \in G, Ha = aH$，则称 $H$ 是 $G$ 的正规子群，也称 不变子群。
Lagrange 定理
设 $G$ 是一个有限群，$H$ 是 $G$ 的一个子群，有： $$|G| = |H| \cdot [G : H]$$ 其中 $[G : H]$ 称为 $G$ 对 $H$ 的指数，是 $H$ 在 $G$ 中的不同右陪集的个数。
推论
- 对有限群 $G$，$\forall a \in G, |a| \ \mathbf{\Big|} \ |G|$
- 对于阶是素数的群，其子群只有平凡子群和本身，即 $\forall a \in G, \langle a \rangle = G$
循环群与置换群
循环群与置换群
循环群
设 $G$ 是一个群，若存在 $a \in G$，使得 $G = \langle a \rangle$，则称 $G$ 是一个循环群，$a$ 称为 $G$ 的生成元。
循环群的性质
任意循环群 $G$ 都是阿贝尔群。反之不一定成立。
循环群的分类
- $n$ 阶循环群：$G = \langle a \rangle$，$|a| = |G| = n$
- 无限循环群：$G = \langle a \rangle$，$|a| = \infty$
- 若 $G = \langle a \rangle$ 是无限循环群，则 $G$ 只有两个生成元：$a$ 和 $a^{-1}$
若 $G = \langle a \rangle$ 是 $n$ 阶循环群，则 $G$ 含有且仅含有 $\varphi(n)$ 个 $n$ 阶元即生成元。 且 $a^r$ 是 生成元当且仅当 $r$ 与 $n$ 互素。
循环群的子群
设 $G = \langle a \rangle$ 是循环群
- $G$ 的子群仍是循环群
- 若 $G$ 是无限循环群，则 $G$ 的子群除了 $\lbrace e \rbrace$ 之外都是无限循环群
- 若 $G$ 是 $n$ 阶循环群，对 $n$ 的每个正因子 $d$，$G$ 都有且仅有一个 $d$ 阶子群，且 $G$ 的 $d$ 阶子群是 $\langle a^{\frac{n}{d}} \rangle$
置换群
置换
设 $S = {1, 2, \cdots, n}$，$S$ 上的一个任何双射函数 $\delta$ 称为 $S$ 上的一个n 元置换。 $n$ 元置换共有 $n!$ 个。
一个群 $G$ 中的某一行或某一列一定都是 $G$ 的元素的一个置换。
置换的乘法
与函数的复合规则相同。
轮换与对换
- 轮换：若 $\delta(i_1) = i_2, \delta(i_2) = i_3, \cdots, \delta(i_n) = i_1$，则称 $\delta$ 是一个 $n$ 元轮换。
- 对换：若 $\delta(i_1) = i_2, \delta(i_2) = i_1, \delta(i) = i$，则称 $\delta$ 是一个 $2$ 元轮换，即对换。
任意置换都可以唯一地表示成不相交的轮换乘积。
可将该置换表示进一步分解成对换的乘积，且对换分解式中对换之间可以有交，分解式也不惟一.
- 奇置换：含有奇数个对换的置换
- 偶置换：含有偶数个对换的置换
对称群
所有的 $n$ 元置换构成的集合 $S_n$ 关于置换乘法构成群，称为 $n$ 元对称群。 $n$ 元对称群的子群叫做 $n$ 元置换群。
所有的旋转变换是 $S_3$ 的子群 但是所有的翻转变换不是 $S_3$ 的子群
交错群
$n$ 元交错群 $A_n$ 是 $n$ 元对称群 $S_n$ 的一个子群，是 $S_n$ 中所有偶置换构成的集合。
Polya 定理
$N = {1, 2, \cdots, n}$ 是被着色物体的集合，$G$ 是 $N$ 上的一个置换群，$m$ 是着色数，则在 $G$ 作用下的不同的着色方案数为： $$M = \frac{1}{|G|} \sum_{g \in G} m^{c(g)}$$ 其中 $m$ 是着色数，$c(g)$ 是 $g$ 的轮换表示中的轮换个数。
Polya 定理中的置换群求解方法
-
确定对称操作的类型：
- 分析物体的对称性，确定所有可能的对称操作（例如旋转、反射等）。
- 对称操作可以分为不同的类型，如绕不同对称轴的旋转。
-
求出基本置换：
- 针对每类对称操作以及其对应的对称轴，求出所有可能的基本置换。
- 例如，立方体的旋转对称包括绕对称轴旋转90°、180°等。
-
应用 Polya 定理：
- 将求出的所有置换作为 Polya 定理中的群元素。
- 根据定理进行等价类的计数，得出问题的解。
环与域
环与域
环
设 $\langle R, +, \cdot \rangle$ 是一个代数系统，如果满足以下条件：
- $\langle R, + \rangle$ 是一个阿贝尔群
- $\langle R, \cdot \rangle$ 是一个半群
- $\cdot$ 对 $+$ 满足分配律。 则称 $\langle R, +, \cdot \rangle$ 是一个环。
通常称 $+$ 为环 $R$ 的加法，$\cdot$ 为环 $R$ 的乘法。 环中加法单位元 记作 $0$，乘法单位元记作 $1$。
对任何元素 $x$，称其加法逆元为负元，记作 $-x$。 若 $x$ 存在乘法逆元，则称之为逆元，记作 $x^{-1}$。
$nx$ 表示 $n$ 个 $x$ 相加，$x^n$ 表示 $n$ 个 $x$ 相乘。
环的实例
- 关于普通加法和乘法封闭的环
- 整数环 $\mathbb{Z}$
- 有理数环 $\mathbb{Q}$
- 实数环 $\mathbb{R}$
- 复数环 $\mathbb{C}$
- $\oplus$ 和 $\otimes$ 分别表示模 $n$ 加法和乘法的环 $\mathbb{Z}_n$
- $n$ 阶矩阵环 $M_n(\mathbb{R})$
- $P(B)$ 对称差和交的环
环的性质
设 $\langle R, +, \cdot \rangle$ 是一个环
- $\forall a \in R, 0 \cdot a = a \cdot 0 = 0$
- $\forall a, b \in R, (-a)b = a(-b) = -ab$
- $\forall a, b, c \in R, a(b - c) = ab - ac, (a - b)c = ac - bc$
- $\displaystyle\forall a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_m \in R, \sum_{i=1}^n a_i \sum_{j=1}^m b_j = \sum_{i=1}^n \sum_{j=1}^m a_i b_j$
特殊的环
- 交换环：满足乘法交换律的环
- 含幺环：存在乘法单位元的环
- 无零因子环：若 $ab = 0 \Rightarrow a = 0 \lor b = 0$ 的环
- 当且仅当满足乘法消去律时，环是无零因子环
- 整环：以上三个性质同时满足的环
- 域：设 $R$ 是整环，且 $R$ 中至少含有两个元素，每个非零元都有乘法逆元，则称 $R$ 是一个域。
格与布尔代数
格与布尔代数
设 $\langle S, \preccurlyeq \rangle$ 是一个偏序集，若 $\forall a, b \in S$，存在 上确界和下确界 ，则称 $\langle S, \preccurlyeq \rangle$ 是一个格。
保联与保交
把求 $\lbrace x, y \rbrace$ 的上确界和下确界看作 $x$ 和 $y$ 的二元运算 $\vee$ 和 $\wedge$，称为保联和保交。
通常把在偏序关系的基础上定义的格称为偏序格。
实例
正因子格
$n$ 是正整数，$S_n$ 是 $n$ 的所有正因子的集合，$S_n$ 关于整除关系 $D$ 构格，称为正因子格。
- $x \vee y = \mathrm{lcm}(x, y)$
- $x \wedge y = \gcd(x, y)$
幂集格
$\langle P(B), \subseteq \rangle$ 是一个格，称为幂集格。
- $A \vee B = A \cup B$
- $A \wedge B = A \cap B$
整数集
$\langle \mathbb{Z}, \leq \rangle$ 是一个格。
- $a \vee b = \max(a, b)$
- $a \wedge b = \min(a, b)$
子群格
子群格
是一个格。
$$L(G) = \lbrace H \ | \ H \leq G \rbrace$$
对任意的 $H_1, H_2 \in L(G)$，$H_1 \cap H_2$ 是 $G$ 的子群，$\langle H_1 \cup H_2 \rangle$ 是由 $H_1$ 和 $H_2$ 生成的子群 。（即包含 $H_1$ 和 $H_2$ 的最小子群）。
- $H \vee K = \langle H \cup K \rangle$
- $H \wedge K = H \cap K$
格的性质
对偶原理
设 $f$ 是各种元素以及符号 $=, \preccurlyeq, \succcurlyeq, \vee, \wedge$ 的命题，令 $f^*$ 是 $f$ 的对偶命题，即将 $f$ 中的 $=, \preccurlyeq, \succcurlyeq, \vee, \wedge$ 分别替换为 $\neq, \succcurlyeq, \preccurlyeq, \wedge, \vee$。
若 $f$ 是真，则 $f^*$ 也是真。
计算律
- 交换律：
- $a \vee b = b \vee a$
- $a \wedge b = b \wedge a$
- 结合律：
- $(a \vee b) \vee c = a \vee (b \vee c)$
- $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
- 幂等律：
- $a \vee a = a$
- $a \wedge a = a$
- 吸收律：
- $a \vee (a \wedge b) = a$
- $a \wedge (a \vee b) = a$
序与运算的关系
若 $L$ 是一个格，$a, b \in L$，则
- $a \preccurlyeq b \Leftrightarrow a \vee b = b \Leftrightarrow a \wedge b = a$
- $a \succcurlyeq b \Leftrightarrow a \vee b = a \Leftrightarrow a \wedge b = b$
保序：即 $$\forall a, b, c, d \in L, a \preccurlyeq b \land c \preccurlyeq d \Rightarrow a \vee c \preccurlyeq b \vee d 且 a \wedge c \preccurlyeq b \wedge d$$
一般不满足分配律。
子格
设 $\langle L, \wedge, \vee \rangle$ 是一个格，$S$ 是 $L$ 的一个非空子集，若 $S$ 关于 $\wedge$ 和 $\vee$ 构成一个格，则称 $\langle S, \wedge, \vee \rangle$ 是 $\langle L, \wedge, \vee \rangle$ 的一个子格。
分配格
设 $\langle L, \wedge, \vee \rangle$ 是一个格，若 $\forall a, b, c \in L$，满足分配律：
$$\begin{aligned} a \wedge (b \vee c) &= (a \wedge b) \vee (a \wedge c) \newline a \vee (b \wedge c) &= (a \vee b) \wedge (a \vee c) \end{aligned}$$
则称 $\langle L, \wedge, \vee \rangle$ 是一个分配格。
分配格的判定
当且仅当不含与钻石格或五边形格同构的子格。
全上界、全下界
- 若存在 $a \in L$，使得 $\forall x \in L, x \preccurlyeq a$，则称 $a$ 是 $L$ 的一个全上界。
- 若存在 $b \in L$，使得 $\forall x \in L, b \preccurlyeq x$，则称 $b$ 是 $L$ 的一个全下界。
$L$ 中的全上界与全下界即为 $L$ 的 最大元和最小元 。
一般将格 $L$ 的全上界记为 $1$，全下界记为 $0$。 若 $L$ 存在全上界或全下界，则一定是唯一的。
有界格
若 $L$ 存在全上界和全下界，则称 $L$ 是一个有界格。 一般将有界格记为 $\langle L, \wedge, \vee, 0, 1 \rangle$。 $\forall a \in L$，有 $$a \vee 0 = 0, a \vee 1 = 1, a \wedge 0 = 0, a \wedge 1 = 1$$
注意， $\vee$ 和 $\wedge$ 是对偶运算。 $0$ 是 $\wedge$ 的零元，是 $\vee$ 的单位元。 $1$ 是 $\vee$ 的零元，是 $\wedge$ 的单位元。
对于涉及到有界格的命题，如果其中含有全下界 $0$ 或全上界 $1$，在求该命题的对偶命题时，必须将 $0$ 替换成 $1$，而将 $1$ 替换成 $0$。
补元
设 $\langle L, \wedge, \vee, 0, 1 \rangle$ 是一个有界格，若 $\forall a \in L$，存在 $a’$，使得 $$a \wedge a’ = 0, a \vee a’ = 1$$ 则称 $a’$ 是 $a$ 的补元。 $a$ 和 $a’$ 互为补元。
补元是唯一的。 称任何元素都有补元的有界格为有补格。
布尔代数
如果一个格是有补分配格，则称其为布尔代数，记为 $\langle B, \wedge, \vee, ‘, 0, 1 \rangle$。
实例： 正因子格（若每个质因数都只出现一次） 、 幂集格 、 命题代数 、 子群格 。
有限布尔代数
论域 $B$ 为有限集合的布尔代数称为有限布尔代数。 设格 $0 \in L$，$L$ 是格， 若 $\exists a \in L, \forall x \in L, 0 \prec x \preccurlyeq a \Leftrightarrow x = a$ 则称 $a$ 是 $L$ 的原子。
设 $A$ 是 有限布尔代数系统 $B$ 的全体原子构成的集合，则 $B$ 同构于 $A$ 的幂集代数 $P(A)$。
推论：
- 有限布尔代数的 基数 为 $2^n$。
- 任何等势的有限布尔代数同构。