《离散数学（二）》学习笔记

过了快一年半，又再次接触到了《离散数学》这门课。与之前学习《线性代数》、《概率论》时那种“过了就行”的心态相比，现在我对数学慢慢开始有了敬畏的心理，可能是最近搞深度学习被各种数学公式折磨够了吧。而且，从主观感受上来说，《离散数学》这门课是最“返璞归真”的数学课，它用数学符号把世界上各种事物抽象成数学符号，用一种“理想的形式”来研究世界。我记得《离散数学（一）》的老师说过，世界是连续的，但是计算机底层只有高低电平，没法表示连续的数据，所以《离散数学》对计算机专业的学生来说是非常重要的一门数学课。

代数

6.1代数结构

代数由三部分组成：

• 一个集合，称为代数的载体，这个集合通常非空。
• 定义在载体上的运算。根据上课的内容，运算要有封闭性，即运算后的结果还要在载体上。

运算是指从$S^m$ 到$S$的一个映射。

• 载体的特异元素，如零元，幺元，叫做代数常数。若不关心特异元素则可以没有代数常数。

代数运算的几个性质

• 交换律
• 结合律
• 分配律（下式表示*对+左可分配）

$$a*(b+c)=a*b+a*c$$

• 吸收率(下式表示*对+左可吸收)

$$x*(x+y)=x$$

• 消去律（下式表示左可消去）

$$a*x=a*y \Rarr x=y$$

代数常数

一般就是零元和幺元。

零元和任何元素运算都是零元，幺元和任何元素运算都是该元素，可以类比整数集合上乘法的0和1。

书上还介绍了一个定理

推论6.1-2：一个二元运算的幺元（零元）是唯一的。

即左幺元和右幺元相等，证明直接用左右幺元相乘即可。

逆元

定义6.1-3 若x*y=e，e为幺元，则称x是y的左逆元，y是x的右逆元。

定理6.1-3 对于可结合运算，如果一个元素有左逆元和右逆元，则左右逆元相等。

简单利用结合律即可证明。

6.2 子代数 & 6.3 同态

子代数

定义6.2-2 设$A=<S,\circ,\triangle,k>$是一代数，如果

• $S' \sub S$
• S’对S上的运算$\circ$和$\triangle$封闭
• $k\in S$

那么$A'=<S,\circ,\triangle,k>$是A的子代数。

子代数中较难满足的一个条件就是封闭性，这个定义告诉我们一个代数系统可以由若干个（或者只有一个）子代数组成。

同构

定义6.3-1 代数$A=<S,*,\triangle,k>$和$A'=<S',*',\triangle',k'>$是同构的，当且仅当

• $h: S\rarr S'$
• $h(a*b)=h(a)*'h(b)$
• $h(\triangle a)=\triangle'h(a)$
• $h(k)=k'$

其中h是一个双射函数。

这里a、b是S的任意元素，映射h叫做从A到A’的同构，A‘叫做A在映射h下的同构象。

同构有许多优秀的性质，在一定程度上可以简化研究。如果一个代数系统过于复杂，则我们可以找出与其同构的一个代数（通常比原来的代数系统更简单），从而简化研究。在中学时候我们就学习过把生活中的问题抽象成数学问题，那么同构就是将问题抽象成另一个数学问题，当然前提是我们丢弃了我们不关心的部分，且我们关心的部分性质相似（甚至不变）。

同态

正如文所说，我们可以寻找某个代数的同构来简化研究。但是，同构的定义太“强”了，我们很难找到一个满足这样条件的一个双射函数。所以，同态降低了要求，放弃了“h是一个双射函数”的要求

定义6.3-2 代数$A=<S,*,\triangle,k>$和$A'=<S',*',\triangle',k'>$是同态的，当且仅当

• $h: S\rarr S'$
• $h(a*b)=h(a)*'h(b)$
• $h(\triangle a)=\triangle'h(a)$
• $h(k)= k'$

这里a、b是S的任意元素，映射h叫做从A到A’的同态，A‘叫做A在映射h下的同态象。根据h是单射还是满射，还延伸出了单一同态和满同态的概念。

关于同态，有几条重要的性质。

定理6.3-2 设h是从$A=<S,*,\triangle,k>$到$A'=<S',*',\triangle',k'>$d的同态，那么A的同态象$A''=<h(S),*',\triangle',k'>$是A’的子代数。

定理6.3-3 设h是从$A=<S,*,\triangle,k>$到$A'=<S',*',\triangle',k'>$d的同态，A的在h下的同态象为$A''=<h(S),*',\triangle',k'>$，那么：

• 若*是可交换的或可结合的，则在A‘’中，*‘也是可交换的或可结合的。
• 在A中的幺元e和零元$\theta$则A’'中有幺元$h(e)$和$h(\theta)$
• 对于运算*，若一个元素$x$有逆元$x^{-1}$，那么在代数A’'中，对于运算$x'$，元素$h(x)$有逆元$h(x^{-1})$
• 可分配的性质保持不变。

6.4 同余关系

这个关系的名字挺有意思的，应该就是由数论里的同余关系“借”来的，就跟偏序关系的符号$\preccurlyeq$长得很像小于等于符号一个道理（甚至可以直接写成小于等于）。

首先回顾一下什么是关系，用白话说，关系就是序偶构成的集合$R=\{<a,b>,<c,d>,\cdots \}$，如果一对序偶$<a,b>\in R$，我们称a和b有R关系，或者aRb（这两种表达都挺重要的）。关系可以由两个集合进行笛卡尔积产生。

而等价关系，就是有自反、对称、传递性质的关系，最常见的等价关系就是相等关系。

等价类

等价类的定义如下：

定义3.5-3 设R是集合S上的等价关系，对于每一$a\in A$，a关于R的等价类是集合$\{x|xRa\}$记为$[a]_R$。

等价类描述了与a有关系的所有元素，是一个集合，根据等价关系的性质可知，等价类中任意两个元素都有等价关系。不难证明，R的等价类集合（集合的集合）是A的划分。同理我们可以从一个A的划分得出A上的一个等价类，即A的划分中的每个元素（集合的元素还是集合）对自己作笛卡尔积。

可能有点绕，看下面这个例子：

$$\{[a]_R|a\in R\}=\{\{1,4,7\},\{2,5,8\},\{3,6\}\}$$

是集合S=$\{1,2,3,4,5,6,7\}$的一个划分，也是R的等价类集合（我们这里定义R为模3后余数相等），也可以表示为商集的形式$A/R$

保持

若对于S，R是S上的等价关系，$\forall a,b,c\in S,\ aRb \Rarr a*cRb*c$，则称等价关系R在运算*下能保持。对于单元运算符也同理。

保持的意思就是，如果两个元素存在某种等价关系，则两个元素与另一个元素分别运算后的结果仍是等价的。

定义6.4-2 设~是代数$A=<S,*,\triangle>$的载体S上的等价关系，对一切元素$a,b,c\in S$,

1. 若a~b，则a*c~b*c和c*a~c*b
2. 若a~b，则$\triangle a \sim \triangle b$

都满足，则~称为代数A上的同余关系，~的等价类叫做关系~的同余类。

这里说"~的等价类"，应该是指商集S/R，即一个等价类的集合。

构造同余关系

同余关系不太好找，但是书中提供了一个方法来简单地构造同余关系。

aRb当且仅当$h(a)=h(b)$，用集合表示为$R=\{<a,b>|h(a)=h(b)\}$，h是任何一个同态。

简单地说，就是”代数系统A到A’的任意同态h可以诱导出同余关系“，方法就是将象相等的原象划分为一个等价类。

6.5 商代数

在等价关系中，我们将集合关于R的所有等价类再构成一个集合，称为一个划分，或者商集。那么类似的，我们对商代数定义如下。

定义6.5-1 设~是代数$A=\{S,*,\triangle,k\}$上的同余关系，A的关于~的商代数记为A/~，是代数$<S/~,*',\triangle',[k]>$这里的*’和$ \triangle '$定义如下：

对于$\forall [a],[b]\in S/\sim$，有

$$[a]*'[b]=[a*b],\triangle'[a]=[\triangle a]$$

这么一理解有些抽象，可以这么想，既然符合等价关系的元素关系运算后仍符合等价关系，只是它们换了一个等价类呆着而已，那我们可以不关心具体的运算元素，而是关注运算元素的等价类，我们只关心两个等价类运算后会去往哪个等价类。所以，这里的商代数上的关系都被定义成了等价类（集合）的运算。