蒟蒻博主缓考了离散，于是开始芝士总结与复习，进度（2/5）
关系
定义与性质
关系定义
- 关系：我们知道关系就是两个事物之间的联系，抽象一下，具体是啥关系不重要，哪两个东西在一起很重要。所以我们定义如下：
- $若集合R \subseteq X\times Y ，则称R是X到Y的二元关系，简称关系。$
- 若R是X到X的关系，也称R是X上的二元关系。
- $我们可以把< x , y >\in R 记作xRy $
- $< x , y >\notin R记作x\bar Ry $
- 特殊情况：
- $R = \phi，称为空关系 $
- $R = U_X(U_X = X\times X)，称为全域关系 $
- $R = I_X(I_X = \{< x , x >| x \in X \})，称为恒等关系 $
- 定义域(domain)/值域(range)：
- $dom(R) = \{x \in X | \exists y \in Y : < x , y > \in R \}, dom(R) \subseteq X $
- $ran(R) = \{y \in Y | \exists x \in X : < x,y> \in R \}, ran(R) \subseteq Y $
- 后面这种类似的东西我都只写一个，另一个类比
- 矩阵/关系图表示：
- 用矩阵和图的方式来表示一个关系（DS课学过图和矩阵表示方法，很像）
…
- 用矩阵和图的方式来表示一个关系（DS课学过图和矩阵表示方法，很像）
关系性质
- 五个性质：记住他们的定义、矩阵的特征、图的特征
- 这些性质的前提是R为非空集合X上的关系
- 定义
- 自反：$R满足 \forall x (x \in X \rightarrow < x,x> \in R) $
- 反自反：$R满足 \forall x (x \in X \rightarrow < x,x> \notin R) $
- 对称：$R满足 \forall x \forall y (x \in X \wedge y \in X \wedge xRy \rightarrow yRx) $
- 反对称：$R满足 \forall x \forall y (x \in X \wedge y \in X \wedge xRy \wedge x \neq y \rightarrow y \bar Rx) $
- 传递：$R满足 \forall x \forall y \forall z(x \in X \wedge y \in X \wedge z \in X \wedge xRy \wedge yRz \rightarrow xRz) $
- 例：恒等关系是自反、对称、传递的；“<”关系是反自反、反对称、传递的。
- 矩阵与图的特征
- 见图：
…
- 见图：
运算
- 关于$\cup、\cap、-、\sim、\oplus $等运算，关系就是二元序偶集的一种，可以照搬运算。
- 有三大新运算：复合、逆（注意与取反区分）、闭包
复合
- 定义：R为X到Y的关系，S是Y到Z的关系
- $则R\cdot S = \{< x,z> | \exists y \in Y: xRy \wedge ySz \} $
- 运算不满足交换律，但满足结合律。
- 复合的矩阵表示就是俩矩阵相乘（），细想一下逻辑完全符合
- 性质：
- 复合运算的定义域与值域讨论：
- 我们把关系作用于集合，定义为：
- $R是X到Y的集合，R[A] = \{y \in Y | \exists x \in A: < x,y> \in R \}, R^{-1}同理 $
- 所以我们易证：
- $dom(R \cdot S) = R^{-1}[domS], ran(R \cdot S) = R[ranR] $
- 我们把关系作用于集合，定义为：
逆关系
- 定义：记作$R^{-1} $
- 关系中的每个有序偶的第一元与第二元对换
- 在矩阵上表现为原矩阵的转置$M_R^T $
- 关系图上表示为每一条边反向
- 注意与$\sim R $区分
关系五大性质对应的判断条件
- R是A上的二元关系
- $R是自反的 \iff I_A \subseteq R $
- $R是反自反的 \iff I_A \nsubseteq R (I_A \cap R = \phi) $
- $R是对称的 \iff R^{-1} = R $
- $R是反对称的 \iff R^{-1} \cap R \subseteq I_A $
- $R是传递的 \iff R \cdot R \subseteq R $
闭包
- 自反，对称，传递关系都是极大的条件，也就是说，任何一个关系，我都可以通过增加元素，使得其满足这三个性质。而反自反与反对称不行，所以诞生了闭包的运算，也就是通过添加元素，使得关系满足这三个性质形成的最小关系。
- 定义：关系R’为R的自反（对称、传递）闭包(它们都为A上的关系)，当且仅当满足：
- $R’是自反的 $
- $R \subseteq R’ $
- $对于A上的任何一个自反（对称、传递）的关系R’’，R \subseteq R’’ \rightarrow R’ \subseteq R’’(可以看作是一种极小化,这一条称为闭包的最小性) $
- R的自反、对称、传递闭包分别记作：r(R),s(R),t(R)
- 由定义可知：
- R是自反（对称、传递）的，当且仅当R = r/s/t(R)
- R的三大闭包的存在性与唯一性证明：
- $r(R) = R \cup I_A $
- $s(R) = R \cup R^{-1} $
- $t(R) = \cup_{n=1}^\infty R^n $
- 证明都非常的有意思，s(R)的证明直接通过定义，r/t的证明可以证明等式两边相互包含。
- 传递闭包缩小定理：对于有限集A，A中有n个元素，则 $t(R) = \cup_{i=0}^n R^i $
- 可证：$对于任意k > 0 都有R^{n+k} \subseteq \cup_{i=0}^n R^i $
- 性质：
- 闭包运算不破坏包含序关系，即：$若R_1 \subseteq R_2 ，则r/s/t(R_1) \subseteq r/s/t(R_2) $
- 闭包运算也基本不破坏R本身的三大性质，除s(R)会破坏R的传递性（即R传递，s(R)不一定传递，这是一大不对称因素）
- 所以性质2导致s与t运算不可逆 $（st(R) 不一定= ts(R) 但 st(R) \subseteq ts(R) ） $
- 尝试证明
…
序关系
- 序关系有偏序关系，严格偏序关系（拟序关系），全序关系，良序关系
序关系定义
- 偏序：R满足自反，反对称，传递三个性质，则R是A上的偏序关系，用< A , <= >表示偏序结构
- 严格偏序：是自反改为反自反的偏序，就是说一定要比出个高低。
- 但我们发现由反自反与传递可以推出反对称（可以使用反证法，假设关系不是反对称，则一定能推出< x , x >的元素），所以我们定义只需反自反、传递就行。
- 严格偏序和偏序有如下关系：$< = \leq - I_A $
- 全序：若< A , <= >是偏序结构
- $\forall x,y \in A \rightarrow x <= y \vee y <= x ,则称< A , <= >全序结构或者链$（也就是说任意两元素都是可比的）
覆盖与哈斯图
- 由于序关系是传递的，所以我们能够简化关系图，即若x < y, y < z, 则我再图中只画出这两条线，因为x，z之间的关系显而易见，然后偏序关系中的自反关系在图中省略，即不画自圈，就得到了哈斯图。而我们要描述两个元素之间的关系，就需要看它们之间是否夹着不上不下的元素，没有的话这两个元素看上去在我们的序关系中是相邻的，我们称之为覆盖。
- 覆盖：$y覆盖x \Leftrightarrow x < y \wedge \neg \exists z(z \in A \wedge x < z \wedge z < y) $
偏序结构中的特殊元素
- 前提：$< A, \leq>是偏序结构，B \subseteq A $
- 极大元：$b是B的极大元 \Leftrightarrow b \in B \wedge \forall x(x \in B \rightarrow x \leq b) $
- 最大元：$b是B的最大元 \Leftrightarrow b \in B \wedge \neg \exists x(x \in B \wedge x \leq b) $
- 极大与最大的区别：极大是没比我大，最大是比啥都大，根源在于不是所有的元素之间都可比。
- 极小与最小同理。
- 上界：$b是B的上界 \Leftrightarrow b \in A \wedge \forall x(x \in B \rightarrow x \leq b) $
- 最小上界：$b是B的最小上界 \Leftrightarrow b是B的上界 \wedge \forall x(x是B的上界 \rightarrow b \leq x) $
- 下界与最大下界同理。
- 一定要注意并不是所有元素之间都可以比较，所以可能上下界和最大最小元不存在
良序结构
- 定义：若一个偏序结构的每个非空子集都有最小元，则该结构为良序结构。
- 所以良序一定是全序，因为对于任意两个元素，我们都可以当作非空子集拎出来，然后它们俩必有一个最小元。
- 但是全序并不一定是良序，因为可能存在一个无穷递降的序列，使得没有最小元。
- 所以我们可证：良序 $\Leftrightarrow $ 没有无穷递降序列的全序。
- 又：全序关系中，任何非空子集的极小元与最小元等价，所以也可以表述上互换。
等价关系
- 等价关系满足：自反，对称，传递（模m同余的关系就是典型的等价关系）
- 由于传递性，我能用等价关系确定一个集合，叫等价类。
- A中与x有等价关系R的元素的集合，为x关于R的等价类，记作：$[x]_R $
- $[x]_R = \{y | y \in A \wedge xRy \}$
- 性质：等价关系与等价类满足下列性质
- $[x]_R = [y]_R \Leftrightarrow xRy $(传递性证)
- $x,y \in A\wedge x\bar Ry \rightarrow [x]_R \cap [y]_R = \phi $（反证法）
- $\cup_{x \in A}[x]_R = A $(全覆盖定理，$x \in [x]_R $可证)
- 商集：A上关于R的所有等价类的集合，记作A/R
- 划分: $对于A，若有\pi \subseteq \rho(A), 且\pi 满足三个条件，则称\pi 为A的划分 $
- $\forall S \in \pi, S \neq \phi $
- $\forall B,C \in \pi, 若B \neq C 则B \cap C = \phi $
- $\cup \pi = A $
- $\pi 中元素为划分块， \sharp \pi 称作$ 秩
- 由上我们可以知道A上的每个等价关系唯一确定的商集就是一个划分
- $由A上的划分\pi 我们令R_\pi = \{< x,y> | \exists S \in \pi (x,y \in S) \},我们可以唯一确定一个等价关系R_\pi，且A/R_\pi = \pi $
待完善。。。
