离散数学（七）——代数系统

一、运算

1.二元运算

同样地，也可以像这样定义 $𝑛$ 元运算。 $𝑛$ 元运算是函数 $𝑓:{𝑆}^{𝑛}\to 𝑆$ 。

2.运算的封闭性

由于 $𝑆$ 的二元运算的结果必定还是 $𝑆$ 中的元素，因此称集合 $𝑆$ 对运算 $𝑓$ 封闭。

现在取 $𝑆$ 的一个子集 $𝑇$ 。如果 $𝑇$ 中任意两个元素经过运算 $𝑓$ 后还是 $𝑇$ 的元素，那么称子集 $𝑇$ 对 $𝑆$ 的运算 $𝑓$ 封闭。一个不封闭的例子是，整数集上的减法运算对自然数集是不封闭的——因为会产生负数。

3.交换律

假设 $⚬$ 是 $𝑆$ 的二元运算。若：

则称运算 $⚬$ 在 $𝑆$ 上是可交换的，满足交换律。这是在说，这个运算可以不用考虑元素的顺序，都将产生同样的结果。

4.结合律

若：

则称运算 $⚬$ 在 $𝑆$ 上是可结合的，满足结合律。这是在说，在这种运算中，可以忽略括号带来的运算顺序的改变。

5.幂等律

假设运算 $⚬$ 满足结合律，那么可以为这种运算引入幂运算，也就是：

其中右边有 $𝑛$ 个 $𝑥$ 。幂运算必定符合：

在此基础上，假如：

则称 $𝑆$ 的运算 $⚬$ 满足幂等律。这实际亦是说， ${𝑥}^{𝑛}=𝑥$ 。虽然在命题逻辑中逻辑与、逻辑或都满足幂等律，但我们发现数集上的常用运算都不符合幂等律，为此我们引入幂等元，即假如 $𝑆$ 中的元素 $𝑎$ 满足 $𝑎⚬𝑎=𝑎$ ，那么称 $𝑎$ 是运算 $⚬$ 的幂等元。

6.分配律

设两个 $𝑆$ 上的二元运算 $⚬$ 和 $\ast$ 。若：

则称 $\ast$ 对 $⚬$ 是左分配的；若：

则称 $\ast$ 对 $⚬$ 是右分配的。假如上两式都符合，那么可以说 $\ast$ 对 $⚬$ 是可分配的。将分配律区分为左分配和右分配是因为两个运算不一定符合交换律，例如在关系中关系复合对集合并是可分配的，但左分配律和右分配律不能混为一谈：

7.吸收律

现在设两个 $𝑆$ 上的二元运算 $⚬$ 和 $\ast$ 满足交换律。假如：

则称 $⚬$ 和 $\ast$ 满足吸收律。吸收律在命题，逻辑公式与推理论证中的等值演算有出现过。

8.单位元

设 $𝑆$ 上有二元运算 $⚬$ 。假如有元素 ${𝑒}_{𝑙}\in 𝑆$ 满足：

则称 ${𝑒}_{𝑙}$ 是 $⚬$ 的左单位元。相应地，假如有元素 ${𝑒}_{𝑟}\in 𝑆$ 满足：

则称 ${𝑒}_{𝑟}$ 是 $⚬$ 的右单位元。而如果元素 $𝑒$ 既是左单位元、又是右单位元，那么直接称之为 $⚬$ 的单位元。例如在关系中我们提到过：

因此恒等关系是关系复合的单位元。

而假如一个运算既有左单位元、又有右单位元，那么两者必然相等！也就是两者都等于运算的单位元。从此出发可以得出，运算若有单位元，则单位元必唯一。再联系之前的幂等元——单位元必是运算的幂等元。

9.零元

设 $𝑆$ 上有二元运算 $⚬$ 。假如有元素 ${𝜃}_{𝑙}\in 𝑆$ 满足：

则称 ${𝜃}_{𝑙}$ 是 $⚬$ 的左零元。相应地，假如有元素 ${𝜃}_{𝑟}\in 𝑆$ 满足：

则称 ${𝜃}_{𝑟}$ 是 $⚬$ 的右零元。而如果元素 $𝜃$ 既是左零元、又是右零元，那么直接称之为 $⚬$ 的零元。与单位元类似，若运算既有左零元、又有右零元，那么两者必等于运算的唯一的零元。零元亦必是运算的幂等元。

10.逆元

设 $𝑆$ 上有二元运算 $⚬$ ，并且运算有单位元 $𝑒$ 。假如有元素 ${𝑦}_{𝑙}\in 𝑆$ 满足：

则称 ${𝑦}_{𝑙}$ 是 $𝑥$ 的左逆元。相应地，假如有元素 ${𝑦}_{𝑟}\in 𝑆$ 满足：

则称 ${𝑦}_{𝑟}$ 是 $𝑥$ 的右逆元。而如果元素 $𝑦$ 既是左逆元、又是右逆元，那么直接称之为 $𝑥$ 的逆元，也简称逆。而若 $𝑥$ 具有逆元，那么称 $𝑥$ 可逆。同样地，若元素既有左逆又有右逆，那么两者必等于唯一的逆元。

假如运算满足结合律，那么可逆的元素的逆元是唯一的。单位元的逆元是其自身；零元没有逆元。

11.消去律

设 $𝑆$ 上有二元运算 $⚬$ ，若：

并且：

那么称运算 $⚬$ 满足消去律。需要注意，对于消去律，我们排除 $𝑥$ 是零元的情况。

二、代数

1.基本概念

一个代数是一个二元组 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ ，其中 $𝐴$ 称为该代数的基集，是一个集合；而 ${\mathrm{\Sigma }}_{𝐴}$ 也是一个集合，但它是 $𝐴$ 上的运算的集合，称为该代数的运算集。

有时我们会将运算集拆写为 ${𝜎}_{{𝐴}_1}^{\left({𝑛}_1\right)},{𝜎}_{{𝐴}_2}^{\left({𝑛}_2\right)},\dots ,{𝜎}_{{𝐴}_{𝑚}}^{\left({𝑛}_{𝑚}\right)}$ ，其中 ${𝜎}_{{𝐴}_{𝑖}}^{\left({𝑛}_{𝑖}\right)}$ 是指某个 ${𝑛}_{𝑖}$ 元运算 ${𝜎}_{{𝐴}_{𝑖}}:{𝐴}^{{𝑛}_{𝑖}}\to 𝐴$ 。这样，我们也可以将代数拆写为 $\left(𝐴,{𝜎}_{{𝐴}_1}^{\left({𝑛}_1\right)},{𝜎}_{{𝐴}_2}^{\left({𝑛}_2\right)},\dots ,{𝜎}_{{𝐴}_{𝑚}}^{\left({𝑛}_{𝑚}\right)}\right)$ ，这样方便体现每一种运算的元数。

现在假设有两个代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right),\left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ 。假如运算集 ${\mathrm{\Sigma }}_{𝐴},{\mathrm{\Sigma }}_{𝐵}$ 是一一对应的，并且所对应的两个运算 ${𝜎}_{{𝐴}_{𝑖}},{𝜎}_{{𝐵}_{𝑗}}$ 都具有相同的元数，那么称这两个代数是同类型的代数。

现在假设代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ ，并假设 $𝐵$ 是基集 $𝐴$ 的子集。假如子集 $𝐵$ 对运算集 ${\mathrm{\Sigma }}_{𝐴}$ 中的所有运算亦是封闭的，那么基于 ${\mathrm{\Sigma }}_{𝐴}$ 中的每个运算一一定义 $𝐵$ 上的运算以形成新运算集 ${\mathrm{\Sigma }}_{𝐵}$ ，那么称 $\left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ 是 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ 的子代数。

2.同余关系

同余关系是一种特殊的等价关系。对于代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ ，假设 $𝐴$ 上的等价关系 $𝑅\subseteq 𝐴\times 𝐴$ ，若对任意运算集中的 $𝑛$ 元运算 ${𝜎}_{𝐴}$ ，对任意 $\left({𝑎}_1,{𝑎}_2,\dots ,{𝑎}_{𝑛}\right),\left({𝑏}_1,{𝑏}_2,\dots ,{𝑏}_{𝑛}\right)\in 𝐴$ 都有：

那么称这样的等价关系为代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ 上的同余关系。也就是说，参与运算的元素替换为与自己等价的元素，运算的结果依然与原运算结果等价。这称为代数的运算保持关系 $𝑅$ ，或者说 $𝑅$ 对代数有可置换性。

3.商代数

既然同余关系 $𝑅$ 是一种特殊的等价关系，那么代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)$ 的基集必然能够关于 $𝑅$ 形成商集 $𝐴/𝑅$ 。这提供了一种系统地得到原代数的同类型代数的方法：也就是，首先用基集生成商集 $𝐴/𝑅$ ，然后基于原运算集 ${\mathrm{\Sigma }}_{𝐴}$ 中的每一种运算、生成商集上的新运算以生成新运算集 ${\mathrm{\Sigma }}_{𝐴/𝑅}$ 。

注意！ ${\mathrm{\Sigma }}_{𝐴/𝑅}$ 中的运算是商集上的运算！也就是说，其中的 $𝑛$ 元运算 ${𝜎}_{𝐴/𝑅}:{\left(𝐴/𝑅\right)}^{𝑛}\to 𝐴/𝑅$ 的结果是一个集合¹¹ $𝐴$ 的一个等价类、而不是 $𝐴$ 中的元素！现在我们给出 ${𝜎}_{𝐴/𝑅}$ 的精确定义，假设它对应的是原运算集 ${\mathrm{\Sigma }}_{𝐴}$ 中的运算 ${𝜎}_{𝐴}$ ：

通俗地说：等价类的运算 ${𝜎}_{𝐴/𝑅}$ 的结果，是取其中每一个等价类的代表、做运算 ${𝜎}_{𝐴}$ 后的结果所在的等价类。

4.同态

同态是一种特殊的函数。对于两个同类型的代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right),\left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ ，首先定义两者的基集之间的函数 $𝑓:𝐴\to 𝐵$ 。对于任意 ${\mathrm{\Sigma }}_{𝐴}$ 中的运算 ${𝜎}_{𝐴}$ 、以及它所对应的 ${\mathrm{\Sigma }}_{𝐵}$ 中的运算 ${𝜎}_{𝐵}$ ，如果：

那么称函数 $𝑓$ 是同态。同态对代数中的运算是可交换的。举一个简单的例子：假如 ${\mathrm{\Sigma }}_{𝐴}$ 中的运算 $⚬$ 对应 ${\mathrm{\Sigma }}_{𝐵}$ 中的 $\ast$ ，且 ${𝑎}_1,{𝑎}_2\in 𝐴$ ，那么对于同态函数 $𝑓$ 下式总成立：

5.同构

为了进一步区分同态，我们利用函数的性质来为细分同态。假如同态函数 $𝑓$ 是单函数，那么称 $𝑓$ 是单同态；若同态函数 $𝑓$ 是满函数，那么称 $𝑓$ 是满同态；若同态函数 $𝑓$ 是双函数，也就是 $𝑓$ 既是单同态、又是满同态，那么称 $𝑓$ 是同构，并称两代数 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right),\left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ 间同构，记为 $\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)\simeq \left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ 。

对于满同态 $𝑓:\left(𝐴,{\mathrm{\Sigma }}_{𝐴}\right)\to \left(𝐵,{\mathrm{\Sigma }}_{𝐵}\right)$ ，假设 ${\mathrm{\Sigma }}_{𝐴}$ 中的两个运算 $⚬,\ast$ 分别对应 ${\mathrm{\Sigma }}_{𝐵}$ 中的 ${⚬}^{\prime },{\ast }^{\prime }$ ，那么：

(1)若 $⚬$ 满足交换律、结合律、幂等律，那么 ${⚬}^{\prime }$ 亦满足交换律、结合律、幂等律；
(2)若 $⚬$ 对 $\ast$ 有分配律，那么 ${⚬}^{\prime }$ 对 ${\ast }^{\prime }$ 亦有分配律；
(3)若 $⚬$ 和 $\ast$ 有吸收律，那么 ${⚬}^{\prime }$ 和 ${\ast }^{\prime }$ 亦有吸收律；
(4)若 ${𝑥}_{𝐴}\in 𝐴$ 是 $⚬$ 的单位元或零元，那么 $𝑓\left({𝑥}_{𝐴}\right)$ 是 ${⚬}^{\prime }$ 的单位元或零元；
(5)若 $𝑎\in 𝐴$ 关于 $⚬$ 的逆元是 ${𝑎}^{-1}$ ，那么 $𝑓\left(𝑎\right)\in 𝐵$ 关于 ${⚬}^{\prime }$ 的逆元是 $𝑓\left({𝑎}^{-1}\right)$ 。

值得注意的是，满同态不保持消去律(除非 $𝑓$ 同时还是单函数)！而由于商代数必是原代数的满同态，因此商代数保持原代数除消去律以外的所有性质。

既然同构既是满同态、又是单同态，那么同构的代数会保持一切性质。

三、群

代数系统是一种特殊的代数，它对代数中的运算做出了一些限制，或者说要求其中的运算需要满足一定的性质。

群是代数系统中的其中一种。假设集合 $𝐺$ 、并且其上有二元运算 $⚬$ ，若此运算满足结合律、 $𝐺$ 中有单位元 $𝑒$ 、且 $𝐺$ 中任意元素 $𝑥$ 都有关于 $⚬$ 的逆元 ${𝑥}^{-1}\in 𝐺$ ，那么称 $𝐺$ 为群。

由于群要求其中任意元素都有逆元，因此群的运算不能有零元。同时，由群的定义可知，群上的运算必然满足消去律。

群并不要求 $⚬$ 满足交换律。但如果其确实满足交换律，那么称群为交换群、或称阿贝尔群。当群是交换群时，且运算具有和普通加法类似的性质的时候，将运算记为 $+$ 并称之为加法，运算结果称为和，群本身称为加群。加群的单位元记为 $0$ ， $𝑎$ 的逆元记为 $-𝑎$ 。

不是加群的群称为乘群，其上的运算称为乘法，运算的结果称为积，运算符可以省略不写，即 $𝑎⚬𝑏=𝑎𝑏$ 。之后总假定所讨论群为乘群。

1.群元素的阶

既然群的运算满足结合律，那么就可以引入(整数)幂运算。对于群中的任意元素 $𝑎$ ：

将使 ${𝑎}^{𝑘}=𝑒$ 成立的最小的正整数 $𝑘$ 称为 $𝑎$ 的阶，记为 $\left|𝑎\right|$ 。此时，也可以称 $𝑎$ 为 $𝑘$ 阶元。假如 $𝑘$ 不存在则称 $𝑎$ 为无限阶元。

2.子群

既然群是代数，那么群必有子代数，称为子群。严格来说，对于群 $𝐺$ ，有子集 $𝐻\subseteq 𝐺$ ，若 $𝐻$ 关于 $𝐺$ 的运算 $⚬$ 构成群，那么就称 $𝐻$ 是 $𝐺$ 的子群。这显然说明以下三点：

(1) $𝐻$ 对 $⚬$ 封闭；
(2) $𝐺$ 的单位元是 $𝐻$ 的单位元；
(3) $𝐻$ 中的元素 $𝑎$ ，其在 $𝐺$ 中的逆元 ${𝑎}^{-1}$ 就是 $𝑎$ 在 $𝐻$ 中的逆元。

基于以上三点，在 $𝐻$ 是 $𝐺$ 的非空子集的情况下，可以给出两条子群判定定理：

假如群 $𝐻$ 能表示成 $𝐻=\left\{{𝑎}^{𝑟}|𝑟\in 𝐙\right\}$ 的形式，也就是说群中的元素都能由 $𝑎$ 表示、生成，那么称之为循环群，将 $𝑎$ 称为生成元。

3.陪集

假设群 $𝐺$ 及其子群 $𝐻$ 。对于任意 $𝑎\in 𝐺$ ，可以生成两个 $𝐺$ 的子集：

分别称为 $𝐻$ 在 $𝐺$ 的左陪集和右陪集。左右陪集一般都不是 $𝐺$ 的子群。但我们有如下的子群判定定理：

同时，不同的 $𝑎,𝑏\in 𝐺$ 也可能生成同样的左或右陪集。例如对于右陪集来说， $𝐻𝑎=𝐻𝑏$ 当且仅当 $𝑎\in 𝐻𝑏$ 当且仅当 $𝑎{𝑏}^{-1}\in 𝐻$ 。对于左陪集亦然。

因此我们根据满足 $𝐻𝑎=𝐻𝑏$ 的条件定义等价关系 $𝑅\subseteq 𝐺\times 𝐺$ ：

也就是当且仅当 $𝐻𝑎=𝐻𝑏$ ，那么 ${\left[𝑎\right]}_{𝑅}=𝐻𝑎$ ，因此子群 $𝐻$ 的所有右陪集将组合成一个集合族 $𝐺/𝐻$ ，构成了一个 $𝐺$ 的划分！对于左陪集亦是如此。

4.正规子群

假设群 $𝐺$ 及其子群 $𝐻$ 。若对于任意 $𝑎\in 𝐺$ ，都有 $𝐻𝑎=𝑎𝐻$ ，那么称 $𝐻$ 是 $𝐺$ 的正规子群，也称为不变子群。在此情况下，上述的等价关系就进化为同余关系。

交换群因为满足交换律，因此交换群的子群都满足上述条件，都是正规子群。

既然对于正规子群 $𝑅$ 是同余关系，那么就可以像商代数那样，对群 $𝐺$ 系统地生成一个商群！假设 $𝑁$ 是 $𝐺$ 的正规子群，由 $𝑁$ 的所有陪集构成的集合族 $𝐺/𝑁$ 是 $𝐺$ 的划分。在 $𝐺/𝑁$ 上定义运算 $⚬$ ： $\forall 𝑎,𝑏\in 𝐺,𝑁𝑎⚬𝑁𝑏=𝑁\left(𝑎𝑏\right)$ ，那么 $𝐺/𝑁$ 就关于 $⚬$ 构成一个群，称为 $𝐺$ 关于 $𝑁$ 的商群。

5.群同态

假设两个群 $𝐺,{𝐺}^{\prime }$ ，并且有函数 $𝑓:𝐺\to {𝐺}^{\prime }$ 。如果函数满足：

那么称 $𝑓$ 是 $𝐺$ 到 ${𝐺}^{\prime }$ 的一个同态。特别地，若 $𝐺={𝐺}^{\prime }$ ，那么称 $𝑓$ 为自同态。

同样地，根据这个函数的性质，也将同态分为满同态、单同态以及同构。代数同态具有的性质，群同态也都具有。例如：

(1)群同态保持单位：若 $𝑒$ 是 $𝐺$ 的单位元，那么 $𝑓\left(𝑒\right)$ 是 ${𝐺}^{\prime }$ 的单位元；
(2)群同态与求逆元运算可交换： ${\left(𝑓\left(𝑎\right)\right)}^{-1}=𝑓\left({𝑎}^{-1}\right)$ 。