关系的特殊性质及其闭包

特殊性质

	自反关系	反自反关系	对称关系	反对称关系	传递关系
内容
充要条件	$I_X\subseteq R$	$R\cap I_X=\varnothing$	$R^{-1}=R$	$R\cap R^{-1}\subseteq I_X$	$R^2\subseteq R$
关系矩阵	对角线全为$1$	对角线全为$0$	对称	任意两个相互对称的位置上至少有一个$0$
备注					可以推出$\forall n\in Z^{+},R^n\subseteq R$

闭包

设$R$是$X$上的关系，$P$是某种关系的性质。包含$R$的、具有性质$P$的、$X$上的最小关系为$R$的$P$闭包，记为$R^P$.

条件

1. $R\subseteq R^P$
2. $R^P$具有性质$P$
3. $\forall X$上的具有性质$P$的关系$R^{\prime }$，若$R\subseteq R^{\prime }$，则$R^P\subseteq R^{\prime }$.

三个特殊闭包

自反闭包

$r(R)=R\cup I_X$

对称闭包

$s(R)=R\cup R^{-1}$

传递闭包

$t(R)={\bigcup }_{n\in N}{R}^n$

推论

若$|X|=n$，则$t(R)={\bigcup }_{m=1}^n{R}^n$

关系矩阵

$$M_{t(r)}=M_R\vee M_{R^2}\vee \cdots \vee M_{R^n}$$

等价关系和划分

等价关系和等价类

集合$X$上自反、对称且传递的关系称为$X$上的等价关系。

设$R$是$X$上的等价关系，$x\in X$，定义$X$的子集
[x]R={y∣y∈X,且yRx}[x]_R=\{y|y\in X,且yRx\} [x]R​={y∣y∈X,且yRx}
称$[x{]}_R$为$x$（关于$R$）的等价类，$x$为等价类$[x{]}_R$的代表元。

也就是说，$x(\in X)$的等价类$[x{]}_R$由$X$中所有与$x$等价的元素组成。

性质

1. 若$(x,y)\in R$，则$[x{]}_R=[y{]}_R$

   $x,y$同样具有关系$R$

   • 任意等价类中的任意一个元素都可以作为该等价类的代表元

2. 若$(x,y)\notin R$，则$[x{]}_R\cap [y{]}_R=\varnothing$

   • 任意两个等价类要么相等要么没有公共元素

3. ${\bigcup }_{z\in X}[z{]}_R=X$

   • 等价类是由所有那些相互等价的元素组成的，且其外的元素都不与其中的元素等价

商集

$X$上关于$R$的所有等价类组成的集合称为$X$关于$R$的商集，记为$X/R$，即
X/R={[x]R∣x∈X}X/R=\{[x]_R|x\in X\} X/R={[x]R​∣x∈X}

划分

设$\pi$是集合$X$的非空子集的集合（$\pi \subseteq P(X)$ ），满足

• $\forall A,B\in \pi ,A=B或A\cap B=\varnothing$
• ${\bigcup }_{A\in \pi }=X$

则称$\pi$是$X$的划分，$\pi$中的元素称为该划分的划分块。

划分和等价关系

等价关系和划分可以相互导出。

性质

1. 设$R$是$X$上的等价关系，那么商集$X/R$是$X$的划分

   记由$R$导出的划分$X/R$为${\pi }_R$

2. 设$\pi$是集合$X$的划分，则关系
   R={(x,y)∣x,y同属于π的一个划分块}R=\{(x,y)|x,y同属于\pi的一个划分块\} R={(x,y)∣x,y同属于π的一个划分块}
   则$R$是$X$上的等价关系。

   这样导出的$R$记为$R_{\pi }$

推论

$$R=R_{{\pi }_R},\pi ={\pi }_{R_{\pi }}$$

所以本质上，等价关系和划分描述的是同一件事情的两个方面。

证明

πR=X/R;RπR={(x,y)∣x,y∈[u]R}⇒(x,y)∈R\pi_R=X/R;R_{\pi_R}=\{(x,y)|x,y\in[u]_R\}\Rightarrow (x,y)\in R πR​=X/R;RπR​​={(x,y)∣x,y∈[u]R​}⇒(x,y)∈R

偏序关系

集合$X$上自反、反对称和传递的关系称为$X$上的偏序关系（偏序），又称部分序关系（部分序）。

• 通常用$\le$表示$x$和$y$满足这种偏序关系
• $x<y$表示$x\le y$且$x\ne y$，这时称$x$在$y$的前面或$y$在$x$的后面

全序关系

若"$\le$"是$X$上的偏序，且对于$X$中的任意两个元素$x,y$，$x\le y$和$y\le x$总有一个成立（可比较），则称“$\le$”为$X$上的全序关系（全序）。

偏序集

$(X,\le )$

若$\le$是全序，则上述标记为全序集。

哈斯图

有限偏序集可以直观地表示为哈斯图。

覆盖

设$(X,\le )$是偏序集，对于任意的$x,y\in X$，若$x<y$，且不存在$z$，使得$x<z<y$，则称$y$覆盖$x$，或称$y$是$x$的直接后继。

哈斯图

规定结点$x,y$之间有箭头当且仅当$y$覆盖$x$，且$y$位于$x$的上方。

全序集的哈斯图是一条直线。

性质

最大元和最小元