第十章关系¶

二元关系¶

定义：对集合 $A$ 和 $B$，$A \times B$ 的任一子集称为 $A$ 到 $B$ 的一个 二元关系 ，一般记作 $R$。若 $\langle x,y\rangle \in R$，可记作 $x R y$；若 $\langle x,y\rangle \notin R$，可记作 $x \not R y$。在 $A=B$ 时，$A \times A$ 的任一子集称为 $A$ 上的一个 二元关系。二元关系可 简称关系
$n$ 元关系：若 $n \in N$ 且 $n>1,A_{1},A_{2},\cdots,A_{n}$ 是 $n$ 个集合，则 $A_{1} \times A_{2} \times \cdots \times A_{n}$ 的任一子集称为从 $A_{1}$ 到 $A_{n}$ 上的一个 n 元关系
特殊关系：对任意的集合 $A$
- $A$ 上的 恒等关系 $I_{A}$ 定义为
  
  \[ I_{A}=\{\langle x,x\rangle \mid x \in A\} \]
- $A$ 上的 全域关 系（全关系）$E_{A}$ 定义为
  
  \[ E_{A}=\{\langle x,y\rangle \mid x \in A \wedge y \in A\} \]
- $\emptyset$ 是 $A$ 上的 空关系
- 定义域和值域：对 $A$ 到 $B$ 的一个关系 $R$，可以定义
- $R$ 的定义域 $\operatorname{dom}(R)$ 为
  
  \[ \operatorname{dom}(R)=\{x \mid(\exists y)(\langle x,y\rangle \in R)\} \]
- $R$ 的值域 $\operatorname{ran}(R)$ 为
  
  \[ \operatorname{ran}(R)=\{y \mid(\exists x)(\langle x,y\rangle \in R)\} \]
- $R$ 的域 $\operatorname{fld}(R)$ 为
  
  \[ \operatorname{fld}(R)=\operatorname{dom}(R) \cup \operatorname{ran}(R) \]
性质：
- 对 $A$ 到 $B$ 的关系 $R$，如果 $\langle x,y\rangle \in R$，则
  
  \[ x \in \cup \cup R,y \in \cup \cup R \]
- 对 $A$ 到 $B$ 的关系 $R$，则
  
  \[ \operatorname{fld}(R)=\cup \cup R \]

关系矩阵和关系图¶

关系矩阵¶

设集合 $X=\left\{x_{1},x_{2},\cdots,x_{m}\right\},Y=\left\{y_{1},y_{2},\cdots,y_{n}\right\}$

定义：
- 若 $R$ 是 $X$ 到 $Y$ 的一个关系，则 $R$ 的关系矩阵是 $m \times n$ 矩阵
  
  \[ M(R)=\left(r_{i j}\right)_{m \times n} \]
  
  矩阵元素是 $r_{i j}$，且
  
  \[ r_{i j}=\left\{\begin{array}{ll} 1,& \mathrm{当}\left\langle x_{i},y_{j}\right\rangle \in R \\ 0,& \mathrm{当}\left\langle x_{i},y_{j}\right\rangle \notin R \end{array}\right. \]
  
  其中 $1 \leqslant i \leqslant m,1 \leqslant j \leqslant n$
- 若 $R$ 是 $X$ 上的一个关系，则 $R$ 的关系矩阵是 $m \times m$ 方阵（$m$ 行、$m$ 列的矩阵）
  
  \[ M(R)=\left(r_{i j}\right)_{m \times m} \]
  
  矩阵元素是 $r_{i j}$，且
  
  \[ r_{i j}=\left\{\begin{array}{ll} 1,& \mathrm{当}\left\langle x_{i},x_{j}\right\rangle \in R \\ 0,& \mathrm{当}\left\langle x_{i},x_{j}\right\rangle \notin R \end{array}\right. \]
  
  其中 $1 \leqslant i \leqslant m,1 \leqslant j \leqslant m$
$A$ 到 $B$ 的关系 $R$ 是 $A \times B$ 的子集，$A \times B$ 有 $m \times n$ 个有序对，矩阵 $M(R)$ 有 $m$ 行、$n$ 列，共有 $m \times n$ 个元素， $M(R)$ 的每个元素恰好对应 $A \times B$ 的一个有序对。用 $M(R)$ 中元素 $r_{i j}$ 的值表示有序对 $\left\langle x_{i},y_{j}\right\rangle$ 是否在 $R$ 中，因为只有 $\in$ 和 $\notin$ 两种情况，所以 $r_{i j}$ 只取值 $0$ 和 $1$ 是合理的。

关系图¶

设集合 $X=\left\{x_{1},x_{2},\cdots,x_{m}\right\}$，$Y=\left\{y_{1},y_{2},\cdots,y_{n}\right\}$

定义
- 若 $R$ 是 $X$ 到 $Y$ 的一个关系，则 $R$ 的关系图是一个有向图 $G(R)=\langle V,E\rangle$，它的顶点集是 $V=X \cup Y$，边集是 $E$，从 $x_{i}$ 到 $y_{j}$ 的有向边 $e_{i j} \in E$，当且仅当 $\left\langle x_{i},y_{j}\right\rangle \in R$
- 若 $R$ 是 $X$ 上的一个关系，则 $R$ 的关系图是一个有向图 $G(R)=\langle V,E\rangle$，它的顶点集是 $V=X$，边集是 $E$，从 $x_{i}$ 到 $x_{j}$ 的有向边 $e_{i j} \in E$ 当且仅当 $\left\langle x_{i},x_{j}\right\rangle \in R$
关系图中一条有向边 $e_{i j}$ 与 $R$ 中的一个有序对 $\left\langle x_{i},x_{j}\right\rangle$ 一一对应

关系的逆、合成、限制和象¶

对 $X$ 到 $Y$ 的关系 $R$，$Y$ 到 $Z$ 的关系 $S$，定义：
- $R$ 的逆 $R^{-1}$ 为 $Y$ 到 $X$ 的关系
  
  \[ R^{-1}=\{\langle x,y\rangle \mid\langle y,x\rangle \in R\} \]
- $R$ 与 $S$ 的合成 $S \circ R$ 为 $X$ 到 $Z$ 的关系
  
  \[ S \circ R=\{\langle x,y\rangle \mid(\exists z)(\langle x,z\rangle \in R \wedge\langle z,y\rangle \in S)\} \]
对任意的集合 $A$ 定义：
- $R$ 在 $A$ 上的限制 $R \upharpoonright A$ 为 $A$ 到 $Y$ 的关系
  
  \[ R \upharpoonright A=\{\langle x,y\rangle \mid\langle x,y\rangle \in R \wedge x \in A\} \]
- $A$ 在 $R$ 下的象 $R[A]$ 为集合
  
  \[ R[A]=\{y \mid(\exists x)(x \in A \wedge\langle x,y\rangle \in R)\} \]

合成的关系矩阵¶

$R^{-1}$ 的关系矩阵 $\boldsymbol{M}(R^{-1})$ 就是 $R$ 的关系矩阵的 转置矩阵
$S \circ R$ 的关系矩阵就是 $R$ 的关系矩阵左乘 $S$ 的关系矩阵

\[ M(S \circ R)=M(R) M(S) \]

其中

\[ w_{i j}=\bigvee_{k=1}^{n}\left(r_{i k} \wedge s_{k j}\right) \]

关系的运算的性质¶

对 $X$ 到 $Y$ 的关系 $R$ 和 $Y$ 到 $Z$ 的关系 $S$，则

\[ \begin{aligned} \operatorname{dom}\left(R^{-1}\right) &=\operatorname{ran}(R)\\ \operatorname{ran}\left(R^{-1}\right)&=\operatorname{dom}(R)\\ \left(R^{-1}\right)^{-1}&=R\\ (S \circ R)^{-1}&=R^{-1} \circ S^{-1} \end{aligned} \]
对 $X$ 到 $Y$ 的关系 $Q$，$Y$ 到 $Z$ 的关系 $S$，$Z$ 到 $W$ 的关系 $R$，则

\[ (R \circ S) \circ Q=R \circ(S \circ Q) \]
对 $X$ 到 $Y$ 的关系 $R_{2}$ 和 $R_{3}$，$Y$ 到 $Z$ 的关系 $R_{1}$，有

\[ \begin{aligned} R_{1} \circ\left(R_{2} \cup R_{3}\right) &=R_{1} \circ R_{2} \cup R_{1} \circ R_{3}\\ R_{1} \circ\left(R_{2} \cap R_{3}\right) &\subseteq R_{1} \circ R_{2} \cap R_{1} \circ R_{3} \end{aligned} \]
对 $X$ 到 $Y$ 的关系 $R_{3}$，$Y$ 到 $Z$ 的关系 $R_{1}$、$R_{2}$，有

\[ \begin{aligned} \left(R_{1} \cup R_{2}\right) \circ R_{3} &=R_{1} \circ R_{3} \cup R_{2} \circ R_{3}\\ \left(R_{1} \cap R_{2}\right) \circ R_{3} &\subseteq R_{1} \circ R_{3} \cap R_{2} \circ R_{3} \end{aligned} \]
对 $X$ 到 $Y$ 的关系 $R$ 和集合 $A$，$B$，有

\[ \begin{aligned} R[A \cup B] &=R[A] \cup R[B]\\ R[\cup A] &=\cup\{R[B] \mid B \in A\}\\ R[A \cap B] &\subseteq R[A] \cap R[B]\\ R[\cap A] &\subseteq \cap\{R[B] \mid B \in A\}\ (A \neq \emptyset)\\ R[A]-R[B] &\subseteq R[A-B] \end{aligned} \]

关系的性质¶

自反性¶

定义：对 $A$ 上的关系 $R$，若对任意的 $x \in A$ 都有 $x R x$，则称 $R$ 为 $A$ 上自反的关系；若对任意的 $x \in A$ 都有 $x \not R x$，则称 $R$ 为 $A$ 上 非自反 的关系。
数学形式：
- $R$ 是 $A$ 上自反的 $\Leftrightarrow(\forall x)\left(x \in A \rightarrow x R x\right)$
- $R$ 是 $A$ 上非自反的 $\Leftrightarrow(\forall x)(x \in A \rightarrow x \not R x)$
性质：
- 在非空集合 $A$ 上的恒等关系 $I_{A}$ 和全关系 $E_{A}$ 都是自反的
- 在非空集合 $A$ 上的空关系 $\emptyset$ 是非自反的
- 在集合 $\mathbb{N}$ 上的小于关系 $<$ 是非自反的
- 在集合 $A$ 的幂集 $P(A)$ 上的真包含关系 $\subsetneqq$ 是非自反的
- 如果 $R$ 是 $A$ 上自反的，则关系矩阵 $M(R)$ 的主对角线元素都是 $1$（即 $r_{i i}$ 都是 $1$），关系图 $G(R)$ 的每个顶点都有自圈
- 如果 $R$ 是 $A$ 上非自反的，则 $M(R)$ 的主对角线元素都是 $0$，$G(R)$ 的每个顶点都没有自圈
三种状态：
- 自反
- 非自反
- 既不是自反也不是非自反

对称性¶

定义：对 $A$ 上的关系 $R$，对任意的 $x,y \in A$，若 $x R y \rightarrow y R x$，则称 $R$ 为 $A$ 上对称的关系；若 $(x R y \wedge y R x) \rightarrow(x=y)$，则称 $R$ 为 $A$ 上 反对称 的关系。
数学形式：
- $R$ 是 $A$ 上对称的 $\Leftrightarrow(\forall x)(\forall y) ((x \in A \wedge y \in A \wedge x R y) \rightarrow y R x)$
- $R$ 是 $A$ 上反对称的 $\Leftrightarrow(\forall x)(\forall y) ((x \in A \wedge y \in A \wedge x R y \wedge y R x) \rightarrow x=y)$
- $R$ 是 $A$ 上反对称的 $\Leftrightarrow(\forall x)(\forall y) ((x \in A \wedge y \in A \wedge x R y \wedge x \neq y) \rightarrow y \not R x)$
性质：
- 在非空集合 $A$ 上的全关系是对称的，不是反对称的
- 在 $B=\{x \mid x \in \mathbb{N} \wedge x \neq 0\}$ 上的整除关系、小于等于关系、小于关系都是反对称的，且不是对称的
- 在非空集合 $A$ 上的恒等关系和空关系都是对称的，也都是反对称的
- 如果 $R$ 是 $A$ 上对称的，则 $M(R)$ 是对称矩阵（对任意的 $i$ 和 $j$，$r_{i j}=r_{j i}$），$G(R)$ 中任意两个顶点之间或者没有有向边，或者互有有向边 $e_{i j}$ 和 $e_{j i}$
- 如果 $R$ 是 $A$ 上反对称的，则 $M(R)$ 是反对称矩阵（对任意的 $i \neq j$，若 $r_{i j}=1$ 则 $r_{j i}=0$），$G(R)$ 中任意两个顶点之间或者没有有向边，或者仅有一条有向边
四种状态：
- 对称
- 反对称
- 既不是对称也不是反对称
- 既是对称也是反对称

传递性¶

定义：$R$ 为 $A$ 上的关系，对任意的 $x,y,z \in A$，若 $(x R y \wedge y R z) \rightarrow x R z$，则称 $R$ 为 $A$ 上传递的关系。
数学形式：
- $R$ 是 $A$ 上传递的 $\Leftrightarrow(\forall x)(\forall y)(\forall z)((x \in A \wedge y \in A \wedge z \in A \wedge x R y \wedge y R z) \rightarrow x R z)$
性质：
- 在集合 $A$ 上的全关系、恒等关系、空关系都是传递的
- 在 $B=\{x \mid x \in \mathbb{N} \wedge x \neq 0\}$ 上的整除关系、小于等于关系、小于关系都是传递的
两种状态：
- 传递
- 非传递

关系的闭包¶

多个关系的合成¶

关系 $R$ 的 $n$ 次幂 $R^{n}$ 定义：对 $A$ 上的关系 $R$，$n \in \mathbb{N}$，关系 $R$ 的 $n$ 次幂 $R^{n}$ 定义如下：
- $R^{0}={\langle x,x\rangle \mid x \in A}=I_{A}$
- $R^{n+1}=R^{n} \circ R \quad(n \geqslant 0)$
性质：
- 设 $A$ 是有限集合，$|A|=n$，$R$ 是 $A$ 上的关系，则存在自然数 $s$ 和 $t$，$s \neq t$，使得 $R^{s}=R^{t}$
- 设 $A$ 是有限集合，$R$ 是 $A$ 上的关系，$m$ 和 $n$ 是非零自然数，则
  - $R^{m} \circ R^{n}=R^{m+n}$
  - $\left(R^{m}\right)^{n}=R^{m n}$
- 设 $A$ 是有限集合，$R$ 是 $A$ 上的关系，若存在自然数 $s$ 和 $t$，$s<t$，使得 $R^{s}=R^{t}$，则
  - $R^{s+k}=R^{t+k}$，其中 $k$ 为自然数；
  - $R^{s+k p+i}=R^{s+i}$，$k$ 和 $i$ 为自然数，$p=t-s$
  - 令 $B=\left\{R^{0},R^{1},\cdots,R^{t-1}\right\}$，则 $R$ 的各次幂均为 $B$ 的元素，即对任意的自然数 $q$，有 $R^{q} \in B$

闭包的定义¶

定义：
- 对非空集合 $A$ 上的关系 $R$，如果有 $A$ 上另一个关系 $R^{\prime}$ 满足：
  - $R^{\prime}$ 是自反的（对称的，传递的）
  - $R \subseteq R^{\prime}$
  - 对 $A$ 上任何自反的（对称的，传递的）关系 $R^{\prime \prime}$
    
    \[ R \subseteq R^{\prime \prime} \rightarrow R^{\prime} \subseteq R^{\prime \prime} \]
- 则称关系 $R^{\prime}$ 为 $R$ 的自反（对称，传递）闭包，记作 $r(R)$（$s(R),t(R)$）
- 直观上说：
- 自反闭包 $r(R)$ 是有自反性的 $R$ 的“最小”超集合
- 对称闭包 $s(R)$ 是有对称性的 $R$ 的“最小”超集合
- 传递闭包 $t(R)$ 是有传递性的 $R$ 的“最小”超集合

必闭包性质¶

对非空集合 $A$ 上的关系 $R$，有
- $R$ 是自反的 $\Leftrightarrow r(R)=R$
- $R$ 是对称的 $\Leftrightarrow s(R)=R$
- $R$ 是传递的 $\Leftrightarrow t(R)=R$
对非空集合 $A$ 上的关系 $R_{1}$，$R_{2}$，若 $R_{1} \subseteq R_{2}$，则
- $r\left(R_{1}\right) \subseteq r\left(R_{2}\right)$
- $s\left(R_{1}\right) \subseteq s\left(R_{2}\right)$
- $t\left(R_{1}\right) \subseteq t\left(R_{2}\right)$
对非空集合 $A$ 上的关系 $R_{1}$、$R_{2}$，则
- $r\left(R_{1}\right) \cup r\left(R_{2}\right)=r\left(R_{1} \cup R_{2}\right)$
- $s\left(R_{1}\right) \cup s\left(R_{2}\right)=s\left(R_{1} \cup R_{2}\right)$
- $t\left(R_{1}\right) \cup t\left(R_{2}\right) \subseteq t\left(R_{1} \cup R_{2}\right)$

闭包的构造¶

对非空集合 $A$ 上的关系 $R$，有

\[ \begin{aligned} r(R)&=R \cup R^{0} \\ s(R)&=R \cup R^{-1} \\ t(R)&=R \cup R^{2} \cup R^{3} \cup \cdots \end{aligned} \]
设 $A$ 为非空有限集合，$|A|=n$，$R$ 是 $A$ 上的关系，则存在一个正整数 $k \leqslant n$，使得

\[ t(R)=R^{+}=R \cup R^{2} \cup \cdots \cup R^{k} \]
Warshall 算法：令 $B[j, i]$ 表示矩阵 $B$ 第 $j$ 行第 $i$ 列的元素：
1. 令矩阵 $\boldsymbol{B}=\boldsymbol{M}(R)$
2. 令 $i=1$，$n=|A|$
3. 对 $1 \leqslant j \leqslant n$，如果 $\boldsymbol{B}[j,i]=1$，则对 $1 \leqslant k \leqslant n$，令
  
  \[ \boldsymbol{B}[j,k]=\boldsymbol{B}[j,k] \vee \boldsymbol{B}[i,k] \]
4. $i$ 加 $1$，
5. 若 $i \leqslant n$，则转到 $(3)$，否则停止，且
  
  \[ M\left(R^{+}\right)=\boldsymbol{B} \]
对非空集合 $A$ 上的关系 $R$，有
- 若 $R$ 是自反的，则 $s(R)$ 和 $t(R)$ 是自反的
- 若 $R$ 是对称的，则 $r(R)$ 和 $t(R)$ 是对称的
- 若 $R$ 是传递的，则 $r(R)$ 是传递的
- $r(s(R))=s(r(R))$
- $r(t(R))=t(r(R))$
- $s(t(R))\subseteq t(s(R))$
结论：由定理可知，若要求出 $R$ 的自反、对称且传递的闭包，则应先求 $r(R)$，再求 $s(r(R))$，最后求 $t(s(r(R)))$。

等价关系和划分¶

等价关系¶

等价关系：对非空集合 $A$ 上的关系 $R$，如果 $R$ 是 自反的、对称的和传递的 ，则称 $R$ 为 $A$ 上的等价关系。
- 图 $(a)$：可以用正方形表示 $A \times A$，$A$ 上的关系是 $A \times A$ 的子集，因此可以用正方形的子集表示。
- 图 $(b)$：$A$ 上的等价关系可以用正方形的一条对角线和线上的若干正方形表示。
- 图 $(c)$：表示的关系不是等价关系。
  - 它包括了对角线，所以有自反性。
  - 它以对角线为对称轴，所以有对称性。
  - 但它没有传递性。因为 $R$ 中的 $a$ 和 $b$ 点对应的有序对，经传递得到 $c$ 点对应的有序对应在 $R$ 中，但 $c$ 点不在 $R$ 中。
等价类：$R$ 是非空集合 $A$ 上的等价关系，对任意的 $x \in A$，令

\[ [x]_{R}=\{y \mid y \in A \wedge x R y\} \]

则称集合 $[x]_{R}$ 为 $x$ 关于 $R$ 的等价类，简称 $x$ 的 等价类 ，也可记作 $[x]$ 或 $\bar{x}$，$x$ 称为等价类 $[x]_{R}$ 的 代表元素
性质：$R$ 是非空集合 $A$ 上的等价关系，对任意的 $x,y \in A$
- $[x]_{R} \neq \emptyset$ 且 $[x]_{R} \subseteq A$
- 若 $x R y$，则 $[x]_{R}=[y]_{R}$
- 若 $x \not R y$，则 $[x]_{R} \cap[y]_{R}=\emptyset$
- $\cup\left\{[x]_{R} \mid x \in A\right\}=A$
商集：对非空集合 $A$ 上的关系 $R$，以 $R$ 的不相交的等价类为元素的集合称为 $A$ 的商集，记作 $A / R$

\[ A/ R= \{y \mid (\exists x)(x \in A \wedge y = [x]_{R})\} \]

划分¶

定义：对非空集合 $A$，若存在集合 $\pi$ 满足下列条件：
- $(\forall x)(x \in \pi \rightarrow x \subseteq A)$ （A 的子集族）
- $\emptyset \notin \pi$ （不空）
- $\cup \pi=A$ （不漏）
- $(\forall x)(\forall y)((x \in \pi \wedge y \in \pi \wedge x \neq y) \rightarrow x \cap y=\emptyset)$ （不交）
则称 $\pi$ 为 $A$ 的一个划分，称 $\pi$ 中的元素为 $A$ 的 划分块
$A$ 的一个划分 $\pi$ 是 $A$ 的非空子集的集合（即 $\pi \subseteq P(A)$ 且 $\emptyset \notin \pi $），$ A $ 的这些子集互不相交，且它们的并集为 $ A$
诱导：
- 由等价关系 $R$ 诱导出来的 $A$ 的划分：
  - 对非空集合 $A$ 上的等价关系 $R$，$A$ 的商集 $A / R$ 就是 $A$ 的划分，它称为由等价关系 $R$ 诱导出来的 $A$ 的划分，记作 $\pi_{R}$
- 划分 $\pi$ 诱导出的 $A$ 上的等价关系：
  - 对非空集合 $A$ 的一个划分 $\pi$，令 $A$ 上的关系 $R_{\pi}$ 为
    
    \[ R_{\pi}=\{\langle x,y\rangle \mid(\exists z)(z \in \pi \wedge x \in z \wedge y \in z)\} \]
    
    则 $R_{\pi}$ 为 $A$ 上的等价关系，它称为划分 $\pi$ 诱导出的 $A$ 上的等价关系
- 对非空集合 $A$ 的一个划分 $\pi$ 和 $A$ 上的等价关系 $R$，$\pi$ 诱导 $R$ 当且仅当 $R$ 诱导 $\pi$

相容关系和覆盖¶

相容关系¶

相容关系：对非空集合 $A$ 上的关系 $R$，如果 $R$ 是 自反的、对称的 ，则称 $R$ 为 $A$ 上的相容关系。
相容类：对非空集合 $A$ 上的相容关系 $R$，若 $C \subseteq A$，且 $C$ 中任意两个元素 $x$ 和 $y$ 有 $x R y$，则称 $C$ 是由相容关系 $R$ 产生的相容类，简称相容类。
最大相容类：对非空集合 $A$ 上的相容关系 $R$，一个相容类若不是任何相容类的真子集，就称为最大相容类，记作 $C_{R}$。
- 性质：
  - $(\forall x)(\forall y)\left(\left(x \in C_{R} \wedge y \in C_{R}\right) \rightarrow x R y\right)$
  - $(\forall x)\left(x \in A-C_{R} \rightarrow(\exists y)\left(y \in C_{R} \wedge x R y\right)\right)$
  - 对非空有限集合 $A$ 上的相容关系 $R$，若 $C$ 是一个相容类，则存在一个最大相容类 $C_{R}$，使 $C \subseteq C_{R}$

覆盖¶

覆盖：对非空集合 $A$，若存在集合 $\Omega$ 满足下列条件：
- $(\forall x)(x \in \Omega \rightarrow x \subseteq A)$
- $\emptyset \notin \Omega$
- $\cup \Omega=A$
则称 $\Omega$ 为 $A$ 的一个覆盖，称 $\Omega$ 中的元素为 $\Omega$ 的 覆盖块。
一个划分是一个覆盖，但一个覆盖不一定是一个划分。因为划分中各元素不相交，覆盖中各元素可能相交。
完全覆盖：对非空集合 $A$ 上的相容关系 $R$，最大相容类的集合是 $A$ 的一个覆盖，称为 $A$ 的完全覆盖，记作 $C_{R}(A)$，而且 $C_{R}(A)$ 是唯一的。
对非空集合 $A$ 的一个覆盖 $\Omega=\left\{A_{1},A_{2},\cdots,A_{n}\right\}$，由 $\Omega$ 确定的关系

\[ R=A_{1} \times A_{1} \cup A_{2} \times A_{2} \cup \cdots \cup A_{n} \times A_{n} \]

是 $A$ 上的相容关系

偏序关系¶

偏序关系和拟序关系¶

偏序关系：对非空集合 $A$ 上的关系 $R$，如果 $R$ 是 自反的、反对称的和传递的 ，则称 $R$ 为 $A$ 上的偏序关系。偏序关系 $R$ 通常记作 $\leqslant$，当 $x R y$ 时，可记作 $x \leqslant y$。
- 偏序关系又称 弱偏序关系，或 半序关系。
拟序关系：对非空集合 $A$ 上的关系 $R$，如果 $R$ 是 非自反的和传递的 （暗含了反对称），则称 $R$ 为 $A$ 上的拟序关系。拟序关系 $R$ 通常记作 $<$ 当 $x R y$ 时，可记作 $x<y$。
- 拟序关系又称 强偏序关系。
性质：
- 若 $R$ 为 $A$ 上的拟序关系，则 $R$ 是反对称的
- 对 $A$ 上的拟序关系 $R$，$R \cup R^{0}$ 是 $A$ 上的偏序关系
- 对 $A$ 上的偏序关系 $R$，$R-R^{0}$ 是 $A$ 上的拟序关系
偏序结构：集合 $A$ 与 $A$ 上的关系 $R$ 一起称为一个结构。集合 $A$ 与 $A$ 上的偏序关系 $R$ 一起称为一个偏序结构，或称 偏序集 ，并记作 $\langle A,R\rangle$

哈斯图¶

盖住关系：对偏序集 $\langle A,\leqslant\rangle$，如果 $x,y \in A$，$x \leqslant y$，$x \neq y$，且不存在元素 $z \in A$ 使得 $x \leqslant z$ 且 $z \leqslant y$，则称 $y$ 盖住 $x$。$A$ 上的盖住关系 $\operatorname{cov} A$ 定义为

\[ \operatorname{cov} A=\{\langle x,y\rangle \mid x \in A \wedge y \in A \wedge y \mathrm{盖住} x\} \]
对偏序集 $\langle A,\leqslant\rangle$，$A$ 上的盖住关系 $\operatorname{cov} A$ 是唯一的，可以用盖住关系画偏序集的哈斯图，作图规则为：
- 每个顶点代表 $A$ 的一个元素，
- 若 $x \leqslant y$ 且 $x \neq y$，则顶点 $y$ 在顶点 $x$ 上方，
- 若 $\langle x,y\rangle \in \operatorname{cov} A$，则 $x,y$ 间连无向边

上确界和下确界¶

最大/最小/极大/极小元¶

定义：对偏序集 $\langle A,\leqslant\rangle$，且 $B \subseteq A$，进一步
- 若 $(\exists y)(y \in B \wedge(\forall x)(x \in B \rightarrow y \leqslant x))$，则称 $y$ 为 $B$ 的 最小元。
- 若 $(\exists y)(y \in B \wedge(\forall x)(x \in B \rightarrow x \leqslant y))$，则称 $y$ 为 $B$ 的 最大元。
- 若 $(\exists y)(y \in B \wedge(\forall x)((x \in B \wedge x \leqslant y) \rightarrow x=y))$，则称 $y$ 为 $B$ 的 极小元。
- 若 $(\exists y)(y \in B \wedge(\forall x)((x \in B \wedge y \leqslant x) \rightarrow x=y))$，则称 $y$ 为 $B$ 的 极大元。
性质：
- 最小（大）元不一定存在，若存在必唯一。
- 在非空有限集合 $B$ 中，极小（大）元必存在，不一定唯一。
直观理解：
- 最小元是哈斯图最下面那个（有多个则没有最小元）
- 最大元是哈斯图最上面那个（有多个则没有最大元）
- 极大元是哈斯图最上面那个（有多个则全部是极大元）
- 极小元是哈斯图最下面那个（有多个则全部是极小元）
- 极大和最大的差别在于 $B$ 中是否包含不可比较的元素

上下界¶

定义：对偏序集 $\langle A,\leqslant\rangle$，且 $B \subseteq A$，进一步
- 若 $(\exists y)(y \in A \wedge(\forall x)(x \in B \rightarrow x \leqslant y))$，则称 $y$ 为 $B$ 的上界。
- 若 $(\exists y)(y \in A \wedge(\forall x)(x \in B \rightarrow y \leqslant x))$，则称 $y$ 为 $B$ 的下界。
- 若集合 $C=\{y \mid y 是 B 的上界 \}$，则 $C$ 的最小元称为 $B$ 的 上确界 或最小上界。
- 若集合 $C=\{y \mid y 是 B 的下界 \}$，则 $C$ 的最大元称为 $B$ 的 下确界 或最大下界。
性质：
- 上下界未必存在，存在时也未必唯一。
- 上（下）确界未必存在，存在必唯一。
- 存在上（下）界，也未必存在上（下）确界。
- 如果 $b$ 是 $B$ 的最大（小）元，则 $b$ 是 $B$ 的上（下）确界。
- 如果 $b$ 是 $B$ 的上（下）界，而且 $b \in B$，则 $b$ 一定是 $B$ 的最大（小）元。

全序关系和链¶

可比：对偏序集 $\langle A,\leqslant\rangle$，对任意的 $x$，$y \in A$，若有 $x \leqslant y$ 或 $y \leqslant x$，则称 $x$ 和 $y$ 是可比的
全序关系：对偏序集 $\langle A,\leqslant\rangle$，如果对任意的 $x$，$y \in A$，$x$ 和 $y$ 都可比，则称 $\leqslant$ 为 $A$ 上的 全序关系，或称 线序关系 ，并称 $\langle A,\leqslant\rangle$ 为 全序集
（反）链的长度：对偏序集 $\langle A,\leqslant\rangle$，且 $B \subseteq A$，进一步
- 如果对任意的 $x,y \in B$，$x$ 和 $y$ 都是可比的，则称 $B$ 为 $A$ 上的链，$B$ 中元素个数称为 链的长度
- 如果对任意的 $x,y \in B$，$x$ 和 $y$ 都不是可比的，则称 $B$ 为 $A$ 上的反链，$B$ 中元素个数称为 反链的长度
定理：
- 对偏序集 $\langle A,\leqslant\rangle$，设 $A$ 中最长链的长度是 $n$，则将 $A$ 中元素分成不相交的反链，反链个数至少是 $n$
- 对偏序集 $\langle A,\leqslant\rangle$，若 $A$ 中元素为 $m n+1$ 个，则 $A$ 中或者存在一条长度为 $m+1$ 的反链，或者存在一条长度为 $n+1$ 的链

良序关系¶

良序关系 ：对偏序集 $\langle A,\leqslant\rangle$，如果 $A$ 的任何非空子集都有最小元，则称 $\leqslant$ 为 良序关系 ，称 $\langle A,\leqslant\rangle$ 为 良序集
性质：
- 一个良序集一定是全序集
- 一个有限的全序集一定是良序集
- 良序定理：任意的集合都是可以良序化的

区间¶

在全序集 $\langle\mathbb{R},\leqslant\rangle$ 上，对于 $a,b \in \mathbb{R}$，$a \neq b$，$a \leqslant b$，则
- $[a,b]=\{x \mid x \in \mathbb{R} \wedge a \leqslant x \leqslant b\}$，称为从 $a$ 到 $b$ 的 闭区间
- $(a,b)=\{x \mid x \in \mathbb{R} \wedge a \leqslant x \leqslant b \wedge x \neq a \wedge x \neq b\}$，称为从 $a$ 到 $b$ 的 开区间
- $[a,b)=\{x \mid x \in \mathbb{R} \wedge a \leqslant x \leqslant b \wedge x \neq b\}$ 称为从 $a$ 到 $b$ 的 半开区间
- $(a,b]=\{x \mid x \in \mathbb{R} \wedge a \leqslant x \leqslant b \wedge x \neq a\}$ 称为从 $a$ 到 $b$ 的半开区间
- 还可以定义下列区间
  
  \[ \begin{aligned} (-\infty,a] &=\{x \mid x \in \mathbb{R} \wedge x \leqslant a\}\\ (-\infty,a) &=\{x \mid x \in \mathbb{R} \wedge x \leqslant a \wedge x \neq a\}\\ [a,\infty) &=\{x \mid x \in \mathbb{R} \wedge a \leqslant x\},\\ (a,\infty) &=\{x \mid x \in \mathbb{R} \wedge a \leqslant x \wedge x \neq a\},\\ (-\infty,\infty) &=\mathbb{R} \end{aligned} \]

第十章 关系¶

二元关系¶

关系矩阵和关系图¶

关系矩阵¶

关系图¶

关系的逆、合成、限制和象¶

合成的关系矩阵¶

关系的运算的性质¶

关系的性质¶

自反性¶

对称性¶

传递性¶

相关性质¶

关系的闭包¶

多个关系的合成¶

闭包的定义¶

必闭包性质¶

闭包的构造¶

等价关系和划分¶

等价关系¶

划分¶

相容关系和覆盖¶

相容关系¶

覆盖¶

偏序关系¶

偏序关系和拟序关系¶

哈斯图¶

上确界和下确界¶

最大/最小/极大/极小元¶

上下界¶

全序关系和链¶

良序关系¶

区间¶

第十章关系¶