离散数学: 近世代数（群、环、域）
近世代数
群
半群定义
- 群和半群是特殊的代数，都只含一个非空集合和一个二元运算，因此元素运算时可省略运算符号 给定代数 < S, ∘ >：
- 半群：若∘可结合，称该代数为半群
- 可交换半群：在半群基础上，∘可交换
- 独异点/含幺半群/拟半群：在半群基础上，∘有幺元
- 子半群：半群的所有子代数都是半群，称为前者的子半群
- 循环半群：给定半群M, ∘，元素a ∈ M，由a自身进行n次运算得到的集合为S : {ak|k ∈ Z}，称：
- a生成了循环半群 < S, ∘ >，a为生成元
- < S, ∘ >为 < M, ∘ >的循环子半群
- 生成集：给定集合G ⊆ S，若所有S的元素可由G中元素及其相互运算后得到，则称G为生成集
- 积半群：两个半群的积代数为积半群
群的性质
- 群：若独异点中的每个元素都有逆元，称该独异点为群
- 基本性质：
- 封闭性：群作为一个代数拥有的性质
- 结合律：群作为一个半群拥有的性质
- 存在单位元：群作为一个独异点拥有的性质
- 所有元素作为逆元：群拥有的性质
- 幂运算规则：
- $a^n=\begin{cases}e,&n=0\\aa^{n-1},&n>0\\(a^{-1})^{-n},&n<0\end{cases}$
- (ab)−1 = b−1a−1，利用可约律证
- 每个非零元素都是可约元，因此方程有唯一解
- 元素的阶：
- 使ar = e的最小的正整数r，记为|a| = r
- 若存在ak = e，则必有$k\equiv0(\rm{mod}\ r)$
- |a−1| = |a|
- $\rm Abel$群：即可交换群，满足(ab)n = anbn；证明一个群为可交换群最简单的方法为证明abab = a2b2
子群
- 若群G的非空子集H关于G的运算构成群，称其为子群，根据集合关系有真子群之分，通过≤、<说明其关系
- 判定方法：
- ∀a∀b(a,b∈H→ab∈H∧a−1∈H)，即同时满足子代数、所有元素有逆元的性质
- 只需证明含幺元，aa−1 = e ∈ H
- ∀a∀b(a,b∈H→ab−1∈H)
- $\begin{align}(a,b\in H\rightarrow ab^{-1}\in H)\Rightarrow(a,a)\rightarrow e\in H\Rightarrow (e,a)\rightarrow a^{-1}\Rightarrow(a,b^{-1})\rightarrow ab\in H\end{align}$
- H有穷，且∀a∀b(a,b∈H→ab∈H)
- $\begin{align}有穷\Rightarrow(\exist k)a^k=e\in H\wedge aa^{k-1}=e\in H\Rightarrow a^{-1}=a^{k-1}\in H\end{align}$
- ∀a∀b(a,b∈H→ab∈H∧a−1∈H)，即同时满足子代数、所有元素有逆元的性质
- 生成的子群：设a ∈ G，则由a生成的群{ak|k ∈ Z}是G的子群，记作 < a>
- 中心子群：称{a ∈ G | ∀x(x∈G∧ax=xa)}为G的中心
- 子群的并和交：若H, K ≤ G
- H ∩ K ≤ G
- H ∪ K ⇔ (H⊆K) ∨ (K⊆H)
- 子群格：偏序集 < {H | H ≤ G}, ⊆ >为G的子群格
- 陪集：H为G的子群，左陪集定义为aH = {a ∘ h | h ∈ H}，其中a ∈ G
- 陪集相当于H在G中的扩充，陪集通常不一定是G的子群
- 存在陪集eH = H
- 所有陪集的阶相等，等于|H|
- 若左陪集和右陪集总相等，称该子群为正规子群
- 左陪集关系：CH = { < a, b> | a, b ∈ G ∧ b−1a ∈ H}
陪集关系是一种等价关系
aH = [a]CH，即G中任意元素在H上的陪集等于该元素所属的等价类
- $\begin{align}&充分性:\forall h\in H,a、ah\in aH;令b=ah,即h=ba^{-1}\Rightarrow a,b\in G\wedge ba^{-1}\in H\\&必要性:a,b\in G\wedge ba^{-1}=h\in H\Rightarrow b=ah\in aH\end{align}$
意义：在找出任意一个子群后，可通过陪集(扩充)来找到其余的所有陪集，而由陪集关系导出的等价类和陪集的对应关系，可得H的不相同陪集个数等于总等价类个数
所有陪集的并集等于G，任意两个不相等陪集完全不相交
- 拉格朗日定理：有限群的阶一定能被任意子群H的阶整除，且商等于等价类的个数
- 存在a是k阶元 ⇔ k整除|G|
循环群
- 若G中任意元素能由a ∈ G的任意次幂表示，则称G = < a>，a为生成元
- 找出循环群G的生成元：
- 若G为无限循环群，则只有a, a−1是生成元
- 若G为n阶循环群，则ak是生成元，其中k小于n且与n互素，因此共有φ(n)个生成元
- 循环群的子群仍是循环群，无限循环群的子群除平凡群外都是无限循环群
- n阶循环群G = < a>的子群：若n有k个正因子，则恰有k个子群，每个正因子d唯一对应一个d阶子群，且$\begin{align}a^{\large\frac{|G|}{d}}\end{align}$为该子群的生成元
环、域、格
环
- 具有两个二元运算的群，通常定义为 < R, +, × >，其中：
- < R, + >构成$\rm Abel$群
- < R, × >构成乘法半群
- ×对+满足分配律
- 称加法幺元为环的零元
- 可交换环、含幺环、无零因子环：乘法半群满足交换律、含幺元、若两数乘积为零元则必有一项为零元
- 布尔环：乘法半群满足等幂律
- 整环：同时满足可交换环、含幺环、无零因子环的性质
域
- 域的定义：
- R是整环的基础上，乘法群中任意元素有其逆元
- R是环的基础上，乘法群是$\rm Able$群
格
- 偏序格：任意有两元素的子集都在整个集合中存在最小上界和最大下界的偏序集
- 代数格：代数 < L, ∘, × >，且∘,×满足交换律、结合律、等幂律、吸收律
- 其中，定义每个元素的∘运算为其最大下界，×运算为其最小上界
- 偏序格和代数格等价
- 完全格：每个非空子集均有上下确界
- 有界格：有上下确界，完全格一定是有界格
- 分配格：两运算满足分配律
- 有补格(有余格)：对任意两元素的最小上界等于整个格的上确界，最大下界等于整个格的下确界