<离散数学> DM4 代数结构

DM4 代数结构

DM4.1 代数系统的构成

代数系统的构成：构成成分（载体、运算）和 构成公理（运算性质）

#n 元运算

设 $A$ 为集合，函数 $f:A× A→ A$ 称为 $A$ 上的二元运算。也能表示为 $f(⟨ a_1,a_2⟩)=a_3$

对于 n 元运算 $f:A^n→ A$：

• 若 $n=0$ 则为 0 元运算，$f:→ A$
• 若 $n=1$ 则为 1 元运算，$f:A→ A$

若 $\operatorname{dom}f=A^n$ 且 $\operatorname{ran}f⊆ A$ 则称 $A$ 在运算 $f$ 下封闭。

运算的算符记号可以是：$∘,\,*,\,∙,\,◻,\,\diamond,\,△$ 等

表达式的表示方法：

• 解析表达式：$∘(x_1,x_2,\ldots,x_n)=y\quad x_1∘ x_2=y\quad △ x =y$ 等
• 运算表：有穷集上的一元、二元计算可用运算表。

#二元运算的算律

对于二元运算，算律有：

• 交换律：$∀ a,b∈ A,\quad a∘ b = b∘ a$

• 结合律：$∀ a,b,c∈ A,\quad (a∘ b)∘ c=a∘(b∘ c)$

• 幂等律：$∀ a∈ A,\quad a∘ a = a$

• 消去律：$∀ a,b,c∈ A,\quad a∘ b=a∘ c∧ a≠{\mathcal 0}⇒ b=c,\quad b∘ a=c∘ a∧ a≠{\mathcal 0}⇒ b=c$

• 分配律（涉及两个不同二元运算）：

  $∀ a,b,c∈ A,\quad a∘(b*c)=(a∘ b)*(a∘ c),\quad a*(b∘ c)=(a* b)∘(a* c)$

• 吸收律（涉及两个不同二元运算）：

  设 $∘,*$ 可交换，则 $∀ a,b∈ A,\quad a∘(a*b)=a,\quad a*(a∘ b)=a$

其中 结合律、幂等律、分配律 能拓展到有限项。

#二元运算的特异元素

二元运算中可能存在以下特异元素：

• 单位元（幺元）$e$：$∀ a∈ A,\quad e∘ a=a∘ e=a$

• 零元 ${\mathcal 0}$：$∀ a∈ A,\quad {\mathcal 0}∘ a=a∘{\mathcal 0}={\mathcal 0}$

• 幂等元 $a$：$a∈ A,\quad a∘ a=a$

• 可逆元 $x$、逆元 $y$：$x∈ A,\exist y∈ A,\quad x∘ y=e$

  在可结合运算中，可逆元 $x$ 对应的逆元 $y$ 是唯一的

存在特异元素也能作为算律。如：同一律（存在单位元）、零律（存在零元）

单位元与零元有唯一性：若存在单位元/零元，则存在唯一的单位元/零元

另若 $\mid A\mid >1$，则必有 $e≠\mathcal 0$

DM4.2 代数系统

代数系统的几种记法：

• $V=⟨ A,Ω,K⟩$

  $A$ 是非空载体

  $Ω$ 是运算集，有 $Ω={∪_{j=1}^∞\\}Ω_j,\quadΩ_j=\{o_j\mid o_j\,是\,A\,上的\,j\,元运算\}$

  $K$ 是代数常数集（0 元运算）且 $∅⊆ K⊆ A$

• $V=⟨ A,Ω⟩$

  此时是将 $K$ 视为 $Ω$ 中的 0 元运算，故 $Ω={∪_{j=0}^∞\\}Ω_j,\quadΩ_j=\{o_j\mid o_j\,是\,A\,上的\,j\,元运算\}$

• $V=⟨ A,o_1,o_2,\ldots,o_r⟩$

  运算数量有限的场合也能这样记

所有构成成分（运算个数、对应运算的元数）相同的代数系统称为 同类型的

同类型且公理相同的代数系统称为 同种的

#子代数

设有代数系统 $V=⟨ A,o_1,o_2,\ldots,o_r⟩$，集合 $B⊆ A,\,B≠∅$

若 $B$ 对 $V$ 中所有运算（含 0 元运算）封闭，则称 $V'=⟨ B,o_1,o_2,\ldots,o_r⟩$ 为 $V$ 的 子代数

若还有 $B\subset A$ 则 $V'$ 是 $V$ 的 真子代数

此外，若 $V$ 的代数常数集合为 $K$ 对 $V$ 中所有运算封闭，则 $⟨ K,o_1,o_2,\ldots,o_r⟩$ 是 $V$ 的 平凡子代数

要指出的是，$V$ 亦是其自身的平凡子代数（也是最大的子代数）

若公理是二元运算的性质，则子代数必定与原代数 同种。

#积代数

设有同类型代数系统 $V_1=⟨ A,o_{11},o_{12},\ldots,o_{1r}⟩$ 和 $V_2=⟨ A,o_{21},o_{22},\ldots,o_{2r}⟩$，其中 $o_{1i}$ 与 $o_{2i}$ 是 $k_i$ 元运算。

则 $V_1$ 与 $V_2$ 的 积代数：$V_1× V_2=⟨ A× B,o_1,o_2,\ldots,o_r⟩$

其中 $o_i$ 是 $k_i$ 元运算，且对于任意的 $⟨ x_1,y_1⟩,⟨ x_2,y_2⟩,\ldots,⟨ x_{k_i},y_{k_i}⟩∈ A× B$ 有

$\quad o_i(⟨ x_1,y_1⟩,⟨ x_2,y_2⟩,\ldots,⟨ x_{k_i},y_{k_i}⟩)=⟨ o_{1i}(x_1,x_2,\ldots,x_{k_i}),o_{2i}(y_1,y_2,\ldots,y_{k_i})⟩$

积代数有以下性质：

• 若 $o_{1i}$ 与 $o_{2i}$ 分别在 $V_1$ 与 $V_2$ 中可 交换/结合/幂等，则 $o_i$ 在积代数中也可交换/结合/幂等
• 若 $o_{1i}$ 对 $o_{1j}$、$o_{2i}$ 对 $o_{2j}$ 在 $V_1$ 与 $V_2$ 中分别适用 分配律，则 $o_i$ 对 $o_j$ 在积代数中也适用分配律
• 若 $o_{1i}$ 与 $o_{1j}$、$o_{2i}$ 与 $o_{2j}$ 在 $V_1$ 与 $V_2$ 中分别适用 吸收律，则 $o_i$ 与 $o_j$ 在积代数中也适用吸收律
• 积代数必定与因子代数 同类型。若系统公理不含消去律则同种，否则不保证同种。
• 积代数能推广到有限多个同类型的代数系统
• 直积分解是研究代数结构的有效手段

#同态、同构

设有同类型代数系统 $V_1=⟨ A,o_{11},o_{12},\ldots,o_{1r}⟩$ 和 $V_2=⟨ B,o_{21},o_{22},\ldots,o_{2r}⟩$，其中 $o_{1i}$ 与 $o_{2i}$ 是 $k_i$ 元运算

若函数 $f:A→ B$ 对于所有运算 $o_{1i},\,o_{2i}$ 满足：

$\quad ∀ x_1,x_2,\ldots,x_{k_i}∈ A$ 都有 $f(o_{1i}(x_1,x_2,\ldots,x_{k_i}))=o_{2i}(f(x_1),f(x_1),\ldots,f(x_{j_i}))$

则称 $f$ 是函数系统 $V_1$ 到 $V_2$ 的 同态映射，简称 同态。同态运算必须保持零元运算在内的所有运算。

简言之，对于二元运算有 $f(x∘ y)=f(x)∘' f(y)$；一元运算有 $f(Δ x)=Δ' f(x)$；零元运算有 $f(k)=k'$

同态可以按照映射性质分类：

• 满足单射的同态称为 单同态
• 满足漫射的同态称为 满同态。记为 $V_1∼ V_2$
• 既是单同态也是满同态的，称为 同构，记为 $V_1≅ V_2$

此外，载体是 $A→ A$ 形式的，称为 自同态

同态有以下性质：

• 同态的合成仍是同态：若 $f:V_1→ V_2$ 同态，$g:V_2→ V_3$ 同态，则 $g∘ f:V_1→ V_3$ 同态

• 同态像是映射到的代数系统的子代数

• 满同态映射（在同态像中）保持原系统的很多性质。

  如：交换律、结合律、幂等律、分配律、吸收律、单位元、零元、逆元

  但，消去律不一定保持

#同余关系、同余类、商集

设有代数系统 $V=⟨ A,o_1,o_2,\ldots,o_r⟩$，其中 $o_i$ 是 $k_i$ 元运算，关系 $∼$ 是 $A$ 上等价关系。

任取 $2k_i$ 个元数 $a_1,a_2,\ldots,a_{k_i},b_1,b_2,\ldots,b_{k_i}$

若对于所有 $j=1,2,\ldots,k_i$ 有 $a_j∼ b_j$，就有 $o_i(a_1,a_2,\ldots,a_{k_i})∼ o_i(b_1,b_2,\ldots,b_{k_i})$。这样就称等价关系 $∼$ 对于运算 $o_i$ 具有 置换性质。

若等价关系 $∼$ 对 $V$ 中所有运算都具有置换性质，则称 $∼$ 是 $V$ 上的 同余关系，$A$ 中相关等价类称为 同余类

$A$ 关于等价关系 $∼$ 的所有同余类的集合称为 商集

• 由同态映射能导出同余关系

  若函数 $f:A→ B$ 为同类型代数系统 $V_1$ 到 $V_2$ 的同态映射，则：

  由 $f$ 导出的等价关系为 $V_1$ 上的同余关系

  每个同态能导出一个同余关系。相同的同态像能导出相同的同余关系。

#商代数

设有代数系统 $V=⟨ A,o_1,o_2,\ldots,o_r⟩$，其中 $o_i$ 是 $k_i$ 元运算。关系 $R$ 是 $V$ 上的同余关系。

则 $V$ 关于 $R$ 的商代数记为：$V/R=⟨ A/R,\overline{o_1},\overline{o_2},\ldots,,\overline{o_r}⟩$。

其中 $A/R$ 是关于同余关系的商集。运算 $\overline{o_i}$ 定义为：$\overline{o_i}([a_1],[a_2],\ldots,[a_{k_i}])=[o_i(a_1,a_2,\ldots,a_{k_i})]$

• 对于商代数，应保证其 良定义，即运算结果与运算元素的表示无关。

  也就是说，对于任意 $k_i$ 元运算 $o_i$，都要有：

  $\quad\overline{o_i}([a_1],[a_2],\ldots,[a_{k_i}])$
  $=[o_i(a_1,a_2,\ldots,a_{k_i})]$
  $=[o_i(b_1,b_2,\ldots,b_{k_i})]$
  $=\overline{o_i}([b_1],[b_2],\ldots,[b_{k_i}])$

商代数有以下性质：

• 商代数 $V/R$ 保持 $V$ 的以下性质：

  交换律、结合律、幂等律、分配律、吸收律。

  消去律不一定能保持。

• 商代数 $V/R$ 保持 $V$ 的特异元素：

  $[e]$ 是商代数的 单位元、$[{\mathcal 0}]$ 是商代数的 零元、$[a^{-1}]=[a]^{-1}$ 是其 逆元/可逆元

• 商代数是原代数的同态像。

  设有代数系统 $V=⟨ A,o_1,o_2,\ldots,o_r⟩$，其中 $o_i$ 是 $k_i$ 元运算。关系 $R$ 是 $V$ 上的同余关系。

  则 自然映射 $g:A→ A/R,\,g(a)=[a],\,∀ a∈ A$ 是 $V$ 到 $V/R$ 的同态映射。

• 同态基本定理：代数系统的同态像与商代数同构。任何同态像都同构于一个商代数。

  代数系统 $V_1=⟨ A,o_{1},o_{2},\ldots,o_{r}⟩$ 和 $V_2=⟨ B,o_{1}',o_{2}',\ldots,o_{r}'⟩$ 同类型，其中 $o_{1i}$ 与 $o_{2i}$ 是 $k_i$ 元运算。$f:A→ B$ 是 $V_1$ 到 $V_2$ 的同态映射，$R$ 是 $f$ 导出的 $V_1$ 上的同余关系。

  则有 $V_1/R ≅⟨ f(A),o_1',o_2',\ldots,o_r'⟩$

DM4.3 群、半群、置换群

#半群、独异点

代数系统 $V=⟨ S,∘⟩$，其中 $S$ 在二元运算下 $∘$ 封闭即构成 广群。

此外，$∘$ 满足 结合律，则构成 半群。

此外，半群中含单位元 $e$ 则构成 独异点（含幺半群）。独异点可表示为 $V=⟨ S,∘,e⟩$

由于仅有一个二元运算，所以 $a∘ b$ 可以简写为 $ab$

若有集合 $B⊆ S$ 非空，且 $B$ 对 $V$ 中运算封闭，则 $⟨ B,∘⟩$ 为 子半群。子半群有如下性质：

• 若干子半群的 非空 交集仍是子半群。

• 若干子独异点的交集仍为子独异点。（子独异点的交集必然非空，因为有 $e∈ S$）

• 若有集合 $B⊆ S$，则子半群 $⟨ B⟩={⋂\\}\{A\mid A\,是\,S\,的子半群,B⊆ A\}$ 即由子集合 $B$ 生成的子半群

  换言之，$⟨ B⟩={∪_{n∈ Z^+}\\}B^n,\,B^n=\{b_1∘ b_2∘ \ldots∘ b_n\mid b_i∈ B,\,i=1,2,\ldots,n\}$

• 有集合 ${∑}$ 表示有穷字母表，$∑^+$ 为非空字的集合，$∑^*$ 为字的集合。

  则每个字可唯一分解为 $∑$ 中元素之积，$∑^+$ 上的运算满足结合律。

  故 $V=⟨ ∑^+,∘⟩$ 构成半群，称之为 $∑$ 上的 自由半群。$∑$ 为该自由半群的 生成元集

  如果包含空串则 $V=⟨ ∑^*,∘⟩$ 构成 自由独异点

半群有如下性质：

• 半群的直积仍是半群，独异点的直积仍是独异点

• 能定义半群（独异点）中的幂运算：$a^1=a,\quad a^n∘ a^m=a^{n+m}$（独异点有 $a^0=e$）

• 任何半群都能通过 增加单位元 $e$ 并定义与 $e$ 的运算 而扩张为独异点。

• 半群同态定理

  若有半群 $V=\{S,*\}$，则 $V'=\{S^S,∘\}$ 也是半群，且存在 $V$ 到 $V'$ 的同态映射。

  其中 $S^S=\{f\mid f:S→ S\}$，$∘$ 为合成。

• 独异点表示定理

  对于独异点 $V=⟨ S,*,e⟩$，必存在 $T⊆ S$ 使得 $V$ 与 $⟨ T,∘,I_S⟩$ 同构

#群

在独异点 $V=⟨ S,∘,e⟩$ 中，加入一元运算逆元 ${}^{-1}$ 即构成 群 $V=⟨ S,∘,{}^{-1},e⟩$

即，在群中，$S$ 在 $∘$ 上封闭，$∘$ 满足结合律，有单位元 $\exist e∈ S$，且存在逆元运算 $∀ x∈ S, x^{-1}∈ S$

群有如下性质：

• 群的等价定义

  $⟨ G,∘⟩$ 中，$∘$ 可结合，并存在 右单位元 $e$（只需 $a∘ e=a$）

  若每个元素对于 $e$ 存在 右逆元 $a^{-1}$（只需 $a∘ a^{-1}=e$），则 $G$ 是群。此时能证明 右单位元/右逆 即 单位元/逆元。

  仅满足 左单位元+左逆元 时仍成立。

• 群方程有唯一解

  对于已知数 $a,b∈ S$，未知数 $x,y∈ S$ 在方程 $a∘ x=b$ 或 $y∘ a=b$ 有且仅有唯一解

  该解即 $x=a^{-1}∘ b$（$y=b∘ a^{-1}$）

  由该定理引申出群的 另一个等价定义：若 $G$ 是半群，且对任意 $∀ a,b∈ G$，$ax=b$ 与 $ya=b$ 在 $G$ 中有解，则 $G$ 是群。

• 群都满足消去律

  由该定理引申出群的 另一个等价定义：若 $G$ 是不含零元的有限半群，且 $G$ 中消去律成立，则 $G$ 是群。

• 有限群的运算表的每行/列都是群中元素的置换（载体中每个元素在每行/列恰出现一次）

  即：$∀ a∈ G$ 有 $aG=G$ 和 $Ga=G$

  但运算表的行列都构成置换的，不一定是群。

群的相关术语：

• 平凡群：只含单位元的群 $⟨\{e\},∘,{^{-1}},e⟩$，可简记为 $\{e\}$

• 交换群：也称 Abel 群（阿贝尔群）。满足 $∀ a,b∈ G,\,a∘ b=b∘ a$

• 有限群、无限群：群的基数为有限或无限

• Klein 四元群：其运算表如下

  	e	a	b	c
  e	e	a	b	c
  a	a	e	c	b
  b	b	c	e	a
  c	c	b	a	e

  Klein 四元群是最小的循环群。

• 群的阶：群的基数。有限群的阶记为 $\mid G\mid$

• 幂运算：$a^n=\begin{cases}e&n=0\\a^{n-1}∘ a&n>0\\(a^{-1})^m&m=-n,n<0\end{cases}$

  幂运算有如下规则：$(a^{-1})^{-1}=a,\,(ab)^{-1}=b^{-1}a^{-1},\,a^na^m=a^{n+m},\,(a^n)^m=a^{nm}$

  此外，对于 Abel 群还有 $(ab)^n=a^nb^n$

  以及，推广到有限多元素之积时有 $(a_1a_2\ldots a_n)^{-1}=a^n_{-1}\ldots a^2_{-1}a^1_{-1}$

• 元素 $a$ 的阶：使 $a^k=e$ 成立的最小正整数 $k$，记为 $\mid a\mid$。无限群中，元素的阶可能不存在。

  有限群的元素都是有限阶，且都是群的阶的因子。但元素都是有限阶的群，不一定是有限群。

  此外，必定有 $a^k=e⇔ k\operatorname{mod} {\mid a\mid }=0$，以及 $\mid a\mid =\mid a^{-1}\mid$

  有限群的元素阶都是 群阶 的因子，可见 质数阶 群的元素阶是 1 或群阶，也就是说质数阶群是循环群。

#子群

设 $G$ 为群，$H$ 为 $G$ 的非空子集。若 $H$ 关于 $G$ 中的运算构成群，则 $H$ 是 $G$ 的 子群，记为 $H≤ G$

若 $H$ 为 $G$ 的真子集，称 $H$ 是 $G$ 的 真子群，记作 $H< G$。可见，子群 $H$ 就是 $G$ 的子代数。

群有消去律，由此可证 $H$ 的零元 $e'=e$

设 $G$ 为群，$H$ 为 $G$ 的非空子集。则判定子群的 判定定理 有：

• $H≤ G⇔∀ a,b∈ H(ab∈ H∧ b^{-1}∈ H)$
• $H≤ G⇔∀ a,b∈ H(ab^{-1}∈ H)$
• $H$ 有限，则：$H≤ G⇔∀ a,b∈ H(ab∈ H)$

一部分重要的子群：

• $a$ 生成子群：$⟨ a⟩=\{a^k\mid k∈ Z\},\,a∈ G$

• $B$ 生成子群：$⟨ B⟩={⋂\\}\{H\mid H≤ G,\, B⊆ H\},\,B⊆ G$

  即 $⟨ B⟩=\{b_1^{e_1}∘ b_2^{e_2}∘ \ldots∘ b_n^{e_n}\mid b_i∈ B,\,e_i=\pm 1,\,i=1,2,\ldots,n,\,n∈ Z^+\}$

• 中心：$C=\{a\mid a∈ G,\,∀ x∈ G(a∘ x=x∘ a)\}$，即所有可交换元素的集合。

  必有 $\{e\}⊆ C⊆ G$。可见 $C=G$ 时即 Abel 群。

• $a$ 的正规化子：$N(a)=\{x\mid x∈ G,\,x∘ a=a∘ x\},\,a∈ G$，即所有与 $a$ 可交换的元素的集合

  可见，$a$ 的正规化子也是 $G$ 的子群。

• $H$ 的正规化子：$N(H)=\{x\mid x∈ G,\,xHx^{-1}=H\},\,H≤ G$

  其中 $xHx^{-1}=\{xhx^{-1}\mid h∈ H\}=\{xex^{-1},xh_1x^{-1},\ldots,xh_ix^{-1}\},\,H=\{e,h_1,h_2,\ldots,h_i\}$

• 共轭子群：$xHx^{-1}=\{xhx^{-1}\mid h∈ H\}$，其中 $H≤ G,\,x∈ G$

  虽然定有 $\mid xHx^{-1}\mid =\mid H\mid$，但两者不一定相等

• 子群的交、并：若 $H,K≤ G$，则

  $H⋂ K≤ G$

  $H∪ K≤ G⇔ H⊆ K∨ K⊆ H$

• 子群格：若 $G$ 为群，$S=\{H\mid H≤ G\}$，则偏序集 $⟨ S,⊆⟩$ 构成 格（偏序集中任何二元子集都有最小上界和最大下界），称为 $G$ 的 子群格。

#循环群

群 $G=⟨ a⟩=\{a^k\mid k∈ Z\},\,a∈ G$，则称 $G$ 为 循环群。其中 $a$ 为 $G$ 的生成元。

若生成元的阶无限，则称 $G$ 是无限循环群。若生成元是 $n$ 阶元，则 $G$ 为 $n$ 阶循环群。

循环群 $G=⟨ a⟩$ 的生成元有以下情况：

• 若 $G$ 是无限循环群，则生成元为 $a$ 和 $a^{-1}$

• 若 $G$ 是 $n$ 阶循环群，且 $n=1$，则 $G=⟨ e⟩$ 的生成元是 $e$

• 若 $G$ 是 $n$ 阶循环群，且 $n>1$，则有 $\phi(n)$ 个生成元（$\phi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数的个数）

  即：$a^r\,是\,G\,的生成元⇔\operatorname{gcd}(n,r)=1$

有如下 定理：

• 若 $G=⟨ a⟩$ 是循环群，则其子群也是循环群。

• 若 $G=⟨ a⟩$ 是无限循环群，则其子群除 $\{e\}$ 外都是无限循环群。

• 若 $G=⟨ a⟩$ 是 $n$ 阶循环群，则其子群的阶数为 $n$ 的因子。

  对于 $n$ 的每个正因子 $d$，在 $G$ 中有且仅有一个 $d$ 阶子群。

#变换群、置换群

$f:A→ A$ 为 $A$ 上的变换。若其双射，则称为 $A$ 上的 一一变换。

定义 $A$ 上的 一一变换群：由 $E(A)=\{f\mid f:A→ A\,为双射\}$ 为基数，关于函数合成运算而构成的群

若有 $G⊆ E(A)$ 为群，则称这样的子群为 $A$ 上的 变换群。

若有穷集 $A$ 有 $\mid A\mid =n$，则 $A$ 上的一一变换称为 $A$ 上的 n 元置换

n 元置换的表示方法有：

• 置换的表示法

  若令 $A=\{1,2,\ldots,n\}$，则置换 $σ=\begin{pmatrix}1&2&\ldots&n\\σ(1)&σ(2)&\ldots&σ(n)\end{pmatrix}$

• n 元置换的轮换表示

  任何置换都能表达成 不交的 轮换 之积，且表法唯一

  若有 $σ(i_1)=i_2、\,σ(i_2)=i_3、\ldots、σ(i_{n-1})=i_n、\,σ(i)=i_1$，则构成轮换

  该不交轮换可表示为 $\tau=(i_1,i_2,\ldots,i_n)$

  置换可表示为不交轮换之积，即 $σ=\tau_1\tau_2\ldots\tau_n$

  写成该表达式时，那些一阶的轮换可以省略。如 $(124)(36)(5)(7)=(124)(36)$

  轮换指数

  n 元置换的 轮换指数 是该轮换中，对应阶轮换的个数的表示。

  其表示为 $1^{C_1(σ)}2^{C_2(σ)}\ldots n^{C_n(σ)}$，其中 $C_k(σ)$ 表示 $k$ 轮换的个数。

  如轮换 $(157)(48)(2)(3)(6)$ 的指数为 $1^32^13^1$

  可见，不同指数的个数是方程 $x_1+2x_2+\ldots+nx_n=n$ 的非负整数解的个数。

• n 元置换的对换表示

  所有轮换可被表示成 对换（2 阶轮换）之积

  轮换转化为对换的方法：$\tau=(i_1,i_2,\ldots,i_n)=(i_1i_2)(i_1i_3)\ldots(i_1i_n)$

  将轮换表示中的轮换转化为对换积，就形成了对换表示。对换间可以相交。

  n 元置换的对换表示不唯一，但分解的对换数量的奇偶性（等于置换中逆序的个数）不变。

  奇置换/偶置换：表成奇数/偶数个对换之积。

  奇置换与偶置换间存在一一对应，因此各有 $\dfrac{n!}{2}$ 个。可见恒等置换是偶置换。

置换的乘法 即函数的合成。

例如有 8 元置换 $σ=(132)(5648)(7),\,\tau=(18246573)$，则 $σ\tau=(15728)(3)(4)(6)$。

这其中有 $σ\tau(1)=σ(\tau(1))=σ(8)=5$，以及 $σ\tau(3)=σ(\tau(3))=σ(1)=3$ 等等。

置换的逆 是置换的反函数。

比如置换 $σ=(132)(5648)$，则 $σ^{-1}=(8465)(231)$

若 $S_n$ 为 $A=\{1,2,\ldots,n\}$ 上的所有置换的集合，则 $S_n$ 关于置换乘法构成群，称为 n 元对称群

其子群称为 n 元置换群。n 元对称群中所有偶置换构成的子群称为 n 元交代群。

置换的阶 是其不交轮换分解式中，各轮换阶的最小公倍数。

有 Cayley 定理：每个群都与一个变换群同构。推论：每个有限群都与一置换群同构。

置换的逆序序列 $(b_1,b_2,\ldots,b_n)$，其中 $b_i$ 代表 $i$ 后面比 $i$ 小的数的个数，有 $0≤ b_i< i$。

置换与其逆序序列一一对应。

DM4.4 群的分解

#陪集

若 $G$ 为群，$H≤ G,\,a∈ G$，则 右陪集 $Ha=\{ha\mid h∈ H,a∈ G\}$。其中 $a$ 称为该陪集的 代表元素

有如下性质：

• $He=H$

• $a∈ Ha$

• $Ha$ 与 $H$ 等势（存在双射），即 $Ha\approx H$

• $a∈ Hb⇔ Ha=Hb⇔ ab^{-1}∈ H$

• 在 $G$ 上定义二元关系 $R$，$aRb⇒ ab^{-1}∈ H$，则 $R$ 为等价关系，且 $[a]_R=Ha$

• $a,b∈ G$，定有 $Ha⋂ Hb=∅$ 或 $Ha=Hb$。此外，${∪\\}Ha=G$

• 指数：$H$ 的左陪集和右陪集数量相等。陪集的总数称为 $H$ 在 $G$ 中的 指数，记为 $[G:H]$

• 拉格朗日定理：$\mid G\mid =\mid H\mid [G:H]$

  推论：群的元素的阶定是群阶的因子。也因此，素数阶的群一定是循环群。

#共轭

若 $G$ 为群，$G$ 上二元关系 $R$ 有 $aRb⇔ \exist x(x∈ G,\,a=xbx^{-1})$，则 $R$ 为 $G$ 上的 共轭关系。

共轭关系是 $G$ 上等价关系，其等价类为 共轭类。与 $a$ 共轭的等价类记为 $\overline {a}$

共轭类有如下性质：

• 群的中心元素的共轭类仅包含该元素自身：$a∈ C⇔ \overline{a}=\{a\}$

• $\mid \overline{a}\mid =\mid G:N(a)\mid$，其中 $N(a)$ 是与 $a$ 的可交换元素子群，即 $N(a)=\{x\mid x∈ G,\, xa=ax\}$

• 共轭类中置换的轮换结构相同

• 群的分类方程：$\mid G\mid =\mid C\mid +[G:N(a_1)]+[G:N(a_2)]+\ldots+[G:N(a_k)]$

  其中 $G$ 为群，$C$ 为中心，$G$ 中含 2 元素以上的共轭类为 $k$ 个

#正规子群

若 $H≤ G$ 且 $∀ a∈ G(aH=Ha)$，则称 $H$ 为 $G$ 的 正规子群，记为 $H⊴ G$

对于任意 $N≤ G$，判定正规子群的方法如下：

• $\quad N⊴ G$
  $⇔∀ g∈ G(gNg^{-1}=N)$
  $⇔ ∀ g∈ G(∀ n∈ N(gng^{-1}∈ N))$
• $\mid N\mid =t$ 且 $N$ 是 $G$ 的唯一的 t 阶子群，则其为正规子群
• $N$ 是指数为 2 的子群（陪集数量为 2），则其为正规子群

#商群

若有 $H⊴ G$，则可定义 商群：$G/H=\{Ha\mid a∈ G\}$

则可定义运算 $Ha∘ Hb=Hab$

商群有以下性质：

• $\mid G/H\mid =[G:H]$，因而商群的阶也是 $\mid G\mid$ 的因子。
• 商群保持 $G$ 中的性质。如交换性、循环性等。

#群的同态

若有 $f:G_1→ G_2$，当且仅当 $∀ x,y∈ G_1(f(xy)=f(x)f(y))$，此时 $f$ 是 $G_1$ 到 $G_2$ 的同态映射。

群的同态映射有如下性质：

• 同态保持元素的性质

  有 $f(e_1)=e_2,\,f(x^{-1})=f(x)^{-1}$

  此外，满同态 $f$ 也能把循环群生成元映射到生成元

  另外，必有 $\mid f(a)\mid$ 整除 $\mid a\mid$（映射到的元素阶是原元素阶的因子）。同构时额外有 $\mid f(a)\mid =\mid a\mid$

• 同态保持子代数的性质

  $H≤ G_1⇒ f(H)≤ G_2$

  若 $H⊴ G_1$ 且 $f$ 是满同态，则有 $f(H)⊴ G_2$

• 同态核的性质

  核：$\ker f=\{x\mid x∈ G,f(x)=e_2\}$

  有 $\ker f=\{e_1\}⇔ f\,是单同态$

  有 $\ker f⊴ G_1$，此外，$∀ a,b∈ G_1(f(a)=f(b))⇔ a\ker f=b\ker f$

• 同态基本定理

  若 $H⊴ G$，则 $G/H$ 是 $G$ 的同态像

  若 $G'$ 是 $G$ 的同态像（即 $f(G)=G'$），则 $G/\ker f≅ G'$

一些特殊的自同态/自同构：

• $\operatorname{End} G$：$G$ 的自同态的集合

• $\operatorname{Aut} G$：$G$ 的自同构的集合

• $\operatorname{Inn} G$：$G$ 的内自同构的集合。内自同构即：$f_x:G→ G,\,f_x(a)=xax^{-1}$

  可见必有 $\operatorname{Inn}G⊆\operatorname{Aut}G⊆\operatorname{End}G$

  $\operatorname{End}G$ 是独异点；$\operatorname{Aut}G$ 是群；$\operatorname{Inn}G$ 是 $\operatorname{Aut}G$ 的正规子群

DM4.5 环和域

#环

若代数系统 $⟨ R,+,∙⟩$ 满足以下条件，则构成 环：

• $⟨ R,+⟩$ 构成 Abel 群（封闭、有单位元、有逆元、满足交换律、结合律）
• $⟨ R,∙⟩$ 构成半群（封闭、满足结合律）
• $∙$ 运算对 $+$ 运算满足分配律

环中的一些 符号说明：

• 对于 $+$ 运算：

  $0$（单位元）、$-x$（逆元）、$nx$（幂运算）、$x-y$（即 $x+(-y)$）

• 对于 $∙$ 运算：

  $1$（单位元）、$x^{-1}$（逆元）、$x^n$（幂运算）

环的 性质：

• $a∙ 0=0∙ a=0$，其中 $0$ 是 $+$ 运算的单位元
• $(-a)∙ b=a∙(-b)=-(a∙ b)$
• $(-a)∙(-b)=a∙ b$
• $a∙(b-c)=a∙ b-a∙ c\qquad (b-c)∙ a=b∙ a-c∙ a$
• $({∑_{i=1}^{n}\\}a_i)∙({∑_{j=1}^m\\}b_j)={∑_{i=1}^n\\}{∑_{j=1}^m\\}(a_i∙ b_j)$
• $(na)∙ b=a∙(nb)=n(a∙ b)$

一些特殊的环：

• 交换环（$∙$ 满足交换律）、含幺环（$∙$ 运算有单位元）

• 无零因子环：$a∙ b=0⇒ a=0∨ b=0$

  （零因子即 $a≠0∧ b≠0$ 且 $a∙ b=0$，此时 $a$ 为左零因子，$b$ 为右零因子）

  若 $R$ 为环，则有定理：$R\, 是无零因子环⇔ R\,中的\,∙\, 运算满足消去律$

• 整环：交换、含幺的无零因子环

• 除环：$\mid R\mid >1$，且 $⟨ R^*,∙⟩$ 构成群，则 $R$ 为 除环。其中 $R^*=R-\{0\}$

#域

$\mid R\mid >1$ 时的，具有交换律的除环（或 $R^*$ 元素有逆元的整环）称为 域。

可见对于域 $F$，有 $⟨ F,+⟩$ 和 $⟨ F-\{0\},∙⟩$ 都是 Abel 群

对于有限的整环 $R$，必有 $R^*$ 为群（无零元、有消去律的有限半群），故 有限的整环都是域

若域 $F$ 中，$\mid F\mid$ 有限，则称为 有限域。

有限域 $⟨ F,+⟩$ 中，若 $x1=0$（即 $+$ 运算中，$1$ 的阶为 $x$），则 $x$ 称为有限域的 特征。

有限域的特征是素数。无限域的特征为 0

有限域有如下性质：若 $F$ 为有限域，则存在素数 $p$ 使得 $\mid F\mid =p^n$

验证素数的方法（Miller-Rabin 算法）

Fermat 小定理：$n\,是素数⇒ ∀ a∈ Z^+(a≠0(\operatorname{mod} n)→ a^{n-1}\equiv 1(\operatorname{mod}n))$

另（因为域是无零因子环）有：$n\,是素数⇒ 方程\, x^2\equiv 1(\operatorname{mod}n)\,的根只有\,\begin{cases}x=1\\x=n-1\end{cases}$

可见对于任意奇素数 $n$，必存在$q,m$ 使得 $n-1=2^qm$

此时对于序列 $a^m(\operatorname{mod}n),\ a^{2m}(\operatorname{mod}n),a^{2^2m}(\operatorname{mod}n),\ldots,a^{2^qm}(\operatorname{mod}n)$

序列最后一项必为为 $1$，且前面的项都是 $1$ 或 $n-1$。

该验证方法的准确率约为一半。多次验证可提高准确率。

#子环

环 $R$ 的非空子集 $A$ 关于环中运算 $+,\,∙$ 构成环，则称 $A$ 是 $R$ 的 子环。

子环就是子代数。存在平凡子环。

判别子环时，判断其对于 $+$ 运算构成子群，且对于 $∙$ 运算构成子半群。

相似的，有 子整环、子除环、子域 的概念。

#理想

若 $D$ 是环 $R$ 的非空子集，$⟨ D,+⟩$ 构成 Abel 群，且 $∀ r∈ R,\ rD⊆ D,\ Dr⊆ D$，则称 $D$ 是 $R$ 的 理想。

只满足 $∀ r∈ R,\ rD⊆ D$ 的称为 左理想，同理也有 右理想。

理想是 $R$ 的子环，但子环不一定是理想。

任何环都有平凡理想：$\{0\}$ 与 $R$ 自身。

#商环

若 $D$ 为 $R$ 的理想，称 $⟨ R/D,+,∙⟩$ 构成的环为 $R$ 关于 $D$ 的 商环

其中 $R/D=\{\overline{x}\mid x∈ R\}$，而 $\overline{x}=D+x=\{d+x\mid d∈ D\}$。

并定义：$\overline{x}+\overline{y}=\overline{x+y},\ \overline{x}∙ \overline{y}=\overline{x∙ y}$

#环同态

若映射 $f:R_1→ R_2$ 满足 $f(x+y)=f(x)+f(y)$ 且 $f(xy)=f(x)f(y)$ 则其为环的同态映射。

同态的核是 $\ker f=\{x\mid x∈ R_1,f(x)=0\}$

环同态有如下性质：

• $f(0)=0,\, f(1)=1,\ f(-x)=-f(x),\ f(x^{-1})=f(x)^{-1}$

• $S$ 是 $R_1$ 的子环，则 $f(S)$ 是 $R_2$ 的子环

  $T$ 是 $R_2$ 的子环，则 $f^{-1}(T)$ 是 $R_1$ 的子环

  $D$ 是 $R_1$ 的理想，则 $f(D)$ 是 $f(R_1)$ 的理想

  $I$ 是 $R_2$ 的理想，则 $f^{-1}(I)$ 是 $R_1$ 的理想

• $\ker f=\{x\mid x∈ R_1,\ f(x)=0\}$ 是 $R_1$ 的理想

• 同态基本定理：环 $R$ 的任何商环 $R/D$ 是 $R$ 的同态像。若 $R∼ R'$ 则 $R'≅ R/\ker f$

DM4.6 格

#格

格 也是一种具有两个二元运算的代数系统。

偏序集 $⟨ S,≼⟩$ 中，若 $S$ 的任意二元子集都有 最大上界 和 最小下界，则称之为 格（格的 偏序集定义）。

可见，所有的 全序集 或 链 都是格。

运算 $∧$（求最大下界）、$\lor$（求最小上界）称为格 $⟨ L,≼⟩$ 的 自然运算（也称保交/保联运算）

格的性质：

• 对偶原理

  若 $P$ 是由格中元素与 $≼,≽,=,∧,∨$ 等表示的命题，则将 $P$ 中符号 $≼,≽,∧,∨$ 分别替换为 $≽,≼,∨,∧$ 而得到的命题 $P^*$ 称为 对偶命题。显然有 $(P^*)^*=P$

  若 $P$ 对于一切格为真，则其对偶命题 $P^*$ 也对一切格为真。

• $a≼ a$（自反）

  $a≼ b,\ b≼ c⇒ a≼ c$（传递）

  $a≼ b,\ b≼ a⇒ a=b$（反对称）

  $a∧ b≼ a,\ a∧ b≼ b$（下界）

  $a≼ a∨ b,\ b≼ a∨ b$（上界）

  $a≼ b,\ a≼ c⇒ a≼ b∧ c$（最大下界）

  $b≼ a,\ c≼ a⇒ b∨ c≼ a$（最小上界）

• 格中的等价条件：$a≼ b⇔ a∧ b=a⇔ a∨ b =b$

• 保序不等式：$a≼ b,\ c≼ d⇒ a∧ c≼ b∧ d,\ a∨ c≼ b∨ d$

  分配不等式：$a∨(b∧ c)≼ (a∨ b)∧(a∨ c)\qquad a∧(b∨ c)≽ (a∧ b)∨(a∧ c)$

  模不等式：$a≼ b⇔ a∨(c∧ b)≼ (a∨ c)∧ b$

• 交换律：$a∧ b=b∧ a\qquad a∨ b=b∨ a$

  结合律：$(a∧ b)∧ c=a∧(b∧ c)\qquad (a∨ b)∨ c=a∨(b∨ c)$

  幂等律：$a∧ a = a\qquad a∨ a = a$

  吸收律：$a∧(a∨ b)=a\qquad a∨(a∧ b)=a$

引理：代数系统 $⟨ S,*,∘⟩$ 中，二元运算 $*,∘$ 满足交换、结合、吸收律，则定有 $*,∘$ 满足幂等律，且 $a*b=a⇔ a∘ b = b$

由此引理给出了格的等价定义：

代数系统 $⟨ S,∧,∨⟩$ 中，二元运算 $∧,∨$ 满足交换、结合、吸收律，则 $⟨ S,∧,∨⟩$ 是格（格的 代数系统定义）

#子格、格同态

格 $L$ 的非空子集 $S$ 关于 $∧,∨$ 运算封闭，则 $S$ 是 $L$ 的子格。

注意：子格中的 $∧,∨$ 运算要 放在原格中计算。

若格 $L_1,\ L_2$ 和映射 $f:L_1→ L_2$ 对于 $∀ x,y∈ L_1$ 有 $f(x∧ y)=f(x)∧ f(y),\ f(x∨ y)=f(x)∨ f(y)$，则 $f$ 为同态映射。

格同态有如下性质：

• 保序性：$a≼ b⇒ f(a)≼ f(b)$
• 若 $f$ 为双射，则：当且仅当 $a≼ b⇔ f(a)≼ f(b)$ 时，$f$ 为同构映射。

#完备格、理想格

若格 $L$ 的任何子集 $S$，$S$ 的最大下界 $∧ S$ 和最小上界 $\lor S$ 都存在，则 $L$ 是 完备格。有限格一定是完备格。

注意：$S$ 也可能是空集。取 $L$ 中最大元为 $∧∅$，最小元为 $\lor∅$。可见完备格必有最大/最小元素。

若格 $L$ 的非空子集 $I$ 满足 $∀ a,b∈ I,\ a∨ b∈ I$（上界）且 $∀ a∈ I,∀ x∈ L,\ x≼ a⇒ x∈ I$（下界），则 $I$ 是 $L$ 的 理想。可见理想一定是子格。

$L$ 的所有理想的集合关于 包含关系 可构成 理想格。记为 $I(L)$。

理想格不一定完备，但 $I_0(L)=I(L)∪ \{∅\}$ 必定是完备格。

DM4.7 特殊的格

#模格

对于格 $L$，若 $∀ a,b,c∈ L,\ a≼ b⇒ a∨(c∧ b)=(a∨ c)∧ b$（模律），则 $L$ 为 模格。

格 $L$ 为模格的 判别条件：

• 当且仅当其不含与五角格同构的子格时，$L$ 为模格。
• 当且仅当其满足 $∀ a,b,c∈ L(a≼ b,\ a∨ c=b∨ c,\ a∧ c=b∧ c⇒ a=b)$ 时，$L$ 为模格。

#分配格

若格 $L$ 对于 $∀ a,b,c∈ L$，满足 $a∧(b∨ c)=(a∧ b)∨(a∧ c)$ 或 $a∨(b∧ c)=(a∨ b)∧(a∨ c)$，则 $L$ 为 分配格。

在任何格中，两个分配式都是等价的。即 $a∧(b∨ c)=(a∧ b)∨(a∧ c)⇔ a∨(b∧ c)=(a∨ b)∧(a∨ c)$

模格 $L$ 为分配格的 判别条件：

• 当且仅当其不含与钻石格同构的子格时，$L$ 为分配格。
• 当且仅当对于 $∀ a,b,c,∈ L$ 有 $(a∧ b)∨(b∧ c)∨(c∧ a)=(a∨ b)∧ (b∨ c)∧ (c∨ a)$ 时，$L$ 为分配格。

#有界格、有补格

格的最大元 $1$ 为 全上界，格的最小元 $0$ 为 全下界。存在全上界与全下界的格 $⟨ L,∧,∨,0,1⟩$ 称为 有界格。

有限格必定有界，无限格有可能无界。

显然有 $a∧ 1=a,\ a∨ 0=a,\ a∨ 1=1,\ a∧ 0 = 0$

对于有界格，其对偶命题除运算符互换外，$0,1$ 也要互换。

在有界格中，若 $a∧ b=0,\ a∨ b=1$，则称 $a,b$ 互为 补元。在 有界分配格 中，若元素存在补元，其补元唯一。

若有界格 $L$ 的所有元素都存在补元，则其为 有补格。

#布尔代数

有补分配格称为 布尔格。此时求补运算构成布尔格中的一元运算。

若 $⟨ B,*,∘,△,a,b⟩$ 是代数系统，其中 $*,∘$ 是二元运算，$△$ 是一元运算，$a,b$ 是零元运算。若其满足如下性质则构成布尔格：

• 交换律：$x*y=y*x\qquad x∘ y=y∘ x$
• 分配律：$x*(y∘ z)=(x*y)∘(x*z)\qquad x∘(y*z)=(x∘ y)*(x∘ z)$
• 同一律：$x*b=x\qquad x∘ a=x$
• 补元律：$x*△ x=a\qquad x∘△ x=b$

布尔格有以下性质：

• 双重否定率：
  $\quad a≼ b$
  $⇔ a∧ b=a$
  $⇔ a∨ b=b$
  $⇔ a∧ \overline{b}=0$
  $⇔ \overline{a}∧ b=1$
• 德摩根率：$a≼ b⇔\overline{b}≼ \overline{a}$

布尔代数的同态映射 $f:B_1→ B_2$ 需满足下列条件中的 2 个：

• $f(x∧ y)=f(x)∧ f(y)$
• $f(x∨ y)=f(x)∨ f(y)$
• $f(\overline{x})=\overline{f(x)}$

在布尔代数中，若对元素 $a∈ B$ 有 $∀ x∈ B,\ x≼ a→ (x=a)∨(x=0)$ 则称 $a$ 是 $B$ 中的 原子。

若 $B$ 是 有限布尔代数，$A$ 是 $B$ 中所有 原子 的集合，则必有 $P(A)≅ B$。

可见任何有限布尔代数元素数都是 $2^n$，任何有限布尔代数都同构于 $\{0,1\}^n$