Sec5-关系

二元关系

Definition $A$ $B$ $A\times B$ $R$ $A$ $B$ 二元关系 $\langle x,y\rangle \in R$ $x Ry$ $\langle x,y \rangle \notin R$ $x \not R y$ 。

$A=B$ $A\times A$ $A$ 上的一个二元关系。二元关系可简称为关系。

Example：用描述的方法定义二元关系，例如：

D_{x} = {⟨ x, y ⟩ ∣ x \in X \land y \in Y \land x 整 除 y}

Example：定义集合的真包含关系和包含关系：

\begin{matrix} R_{1} = {⟨ x, y ⟩ ∣ x \in P (A) \land y \in P (A) \land x \subseteq y} \\ R_{2} = {⟨ x, y ⟩ ∣ x \in P (A) \land y \in P (A) \land x \subset y} \end{matrix}

Definition $n\in N$ $n>1$ $A_1\sim A_n$ $n$ $A_1\times A_2\times \cdots\times A_n$ $A_1$ $A_n$ 上的一个 $\boldsymbol n$ 元关系。

Definition：特殊的关系

$I_A= \left\{\langle x,x\rangle \mid x \in A\right\}$ .
$E_A= \left\{\langle x,y\rangle \mid x \in A \wedge y\in A\right\}$ .
$\varnothing$ .

Definition：定义域、值域、域。

$\operatorname{dom}(R)=\{x \mid (\exists y) (\langle x,y\rangle \in R)\}$ . 即左边的一项组成的集合。
$\operatorname{ran}(R)=\{y \mid (\exists x) (\langle x,y\rangle \in R)\}$ . 即右边的一项组成的集合。
$\operatorname{fld}(R)=\operatorname{dom}(R)\cup \operatorname{ran}(R)=\cup \cup R$ . 即所有讨论的元素组成的集合。

Lemma $A$ $B$ $R$ $\langle x,y \rangle \in R$ $x\in \cup\cup R,y\in \cup\cup R$ .

Proof $\{x,\{x,y\}\}\in R \Rightarrow \{x,y\}\in \cup {R}\Rightarrow x\in \cup\cup R,y\in \cup\cup R$ .

关系矩阵和关系图

Definition $M(R)=(r_{i,j})_{m\times n}$ $r_{i,j}=[\langle i,j \rangle\in R]$ .

Definition $x,y$ $\Leftrightarrow \langle x,y \rangle \in R$ .

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

$R: X\to Y,S : Y\to Z$ ：

Definition（关系的逆） $R$ $R^{-1}$ $Y$ $X$ 的关系：

R^{- 1} = {⟨ x, y ⟩ ∣ ⟨ y, x ⟩ \in R}

$x,y$ $\langle x,y \rangle \in R \Leftrightarrow \langle y,x \rangle \in R^{-1}$ .

Definition（关系的合成） $R$ $S$ $S \circ R$ $X$ $Z$ 的关系：

S \circ R = {⟨ x, y ⟩ ∣ (\exists z) (⟨ x, z ⟩ \in R \land ⟨ z, y ⟩ \in S)}

$S$ $R$ 上。

Definition（关系的限制） $R$ $A$ $R \upharpoonright A$ $A$ $Y$ 的关系：

R ↾ A = {⟨ x, y ⟩ ∣ ⟨ x, y ⟩ \in R \land x \in A}

$A$ 中的元素。

Definition（关系的象） $A$ $R$ $R[A]$ 为集合：

R [A] = {y ∣ (\exists x) (x \in A \land ⟨ x, y ⟩ \in R)}

$A$ $R$ 中能到达的元素的集合。

Example $R=\{\langle a,\{a\} \rangle,\langle \{a\},\{\{a\}\} \rangle\}$ .

$R \upharpoonright \{a\}=\{\langle a,\{a\} \rangle\}$ .
$R \upharpoonright \{\{a\}\}=\{\langle \{a\},\{\{a\}\} \rangle\}$ .
$R^{-1} \upharpoonright \{a\}=\varnothing$ .
$R[\{a\}]=\{\{a\}\},R[\{\{a\}\}]=\{\{\{a\}\}\}$ .（关系的象接收的参数是集合，输出也是集合）

我们可以用 关系矩阵 再来表示关系的逆和关系的合成。

$\boldsymbol M(R^{-1})=\boldsymbol M(R)^{\top}$ .
$\boldsymbol M(S \circ R)=\boldsymbol M(R)\boldsymbol M(S)$ .

为什么是反的，因为关系矩阵里面行代表左端元素，列代表右端元素，同时，矩阵乘法里面的乘法用析取替代.

Theorem（关系的逆的性质）：

$\operatorname{dom}(R^{-1})=\operatorname{ran}(R), \operatorname{ran}(R^{-1})=\operatorname{dom}(R)$ .
$(R^{-1})^{-1}= R$ .
$(S\circ R)^{-1}=R^{-1} \circ S^{-1}$ . （可以类比矩阵求逆）

$R \circ R^{-1}=I_Y$ $I_Y\circ R=R \circ I_Y=R$ .

Theorem（关系的合成满足结合律）：

$Q:X\to Y,S:Y\to Z , R:Z\to W$ ，则：

(R \circ S) \circ Q = R \circ (S \circ Q)

就像矩阵乘法，满足结合律，但是通常不满足交换律。

Proof：

\begin{aligned} ⟨ x, y ⟩ \in (R \circ S) \circ Q \\ \Leftrightarrow (\exists z) (⟨ x, z ⟩ \in Q \land ⟨ z, y ⟩ \in R \circ S) \\ \Leftrightarrow (\exists z) (⟨ x, z ⟩ \in Q \land (\exists w) (⟨ z, w ⟩ \in S \land ⟨ w, y ⟩ \in R)) \\ \Leftrightarrow (\exists w) (\exists z) (⟨ x, z ⟩ \in Q \land ⟨ z, w ⟩ \in S \land ⟨ w, y ⟩ \in R) \\ \Leftrightarrow (\exists w) (⟨ x, w ⟩ \in S \circ Q \land ⟨ w, y ⟩ \in R) \\ \Leftrightarrow ⟨ x, y ⟩ \in R \circ (S \circ Q) \end{aligned}

Theorem: 关系的合成的性质。

$R_2,R_3:X\to Y,R_1:Y\to Z$ ，有：

$R_1\circ(R_2\cup R_3)=R_1\circ R_2 \cup R_1\circ R_3$ .
$R_1\circ (R_2 \cap R_3)\sube R_1\circ R_2 \cap R_1 \circ R_3$ .

$\langle x,y \rangle$ ，有：

\begin{aligned} ⟨ x, y ⟩ \in R_{1} \circ (R_{2} \cup R_{3}) \Leftrightarrow (\exists z) (⟨ x, z ⟩ \in R_{2} \cup R_{3} \land ⟨ z, y ⟩ \in R_{1}) \\ \Leftrightarrow (\exists z) (⟨ x, z ⟩ \in R_{2} \lor ⟨ x, z ⟩ \in R_{3} \land ⟨ z, y ⟩ \in R_{1}) \\ \Leftrightarrow (\exists z) (⟨ x, z ⟩ \in R_{2} \land ⟨ z, y ⟩ \in R_{1}) \lor (\exists z) (⟨ x, z ⟩ \in R_{3} \land ⟨ z, y ⟩ \in R_{1}) \\ \Leftrightarrow ⟨ x, y ⟩ \in R_{1} \circ R_{2} \cup R_{1} \circ R_{3} \end{aligned}

而对于交集的情况，仅仅是包含关系，是因为两个 "z" 不一定相同。

$R_3:X\to Y$ $R_1,R_2:Y\to Z$ ，有：

$(R_1\cup R_2)\circ R_3=R_1\circ R_3 \cup R_2\circ R_3$ .
$(R_1 \cap R_2)\circ R_3\sube R_1\circ R_3 \cap R_2 \circ R_3$ .

Theorem：象的性质。

$R[A\cup B]=R[A]\cup R[B]$ .
$R[\cup A]=\cup \{R[B]\mid B\in A\}$ .
$R[A\cap B]\sube R[A]\cap R[B]$ .
$R[\cap A]\sube \cap \{R[B]\mid B\in A\},A\not= \varnothing$ .
$R[A]-R[B]\sube R[A-B]$ .

Proof $y$ ，有：

\begin{aligned} y \in R [\cup A] & \Leftrightarrow y \in ran (R ↾ \cup A) \\ \Leftrightarrow (\exists x) (x \in \cup A \land ⟨ x, y ⟩ \in R) \\ \Leftrightarrow (\exists x) (\exists B) (B \in A \land x \in B \land ⟨ x, y ⟩ \in R) \\ \Leftrightarrow (\exists B) (B \in A \land (\exists x) (x \in B \land ⟨ x, y ⟩ \in R)) \\ \Leftrightarrow (\exists B) (B \in A \land y \in R [B]) \\ \Leftrightarrow (\exists B) (y \in R [B] \land R [B] \in {R [B] ∣ B \in A}) \\ \Leftrightarrow y \in \cup {R [B] ∣ B \in A} \end{aligned}

$y$ ，有：

\begin{aligned} y \in R [A \cap B] & \Leftrightarrow (\exists x) (x \in A \cap B \land ⟨ x, y ⟩ \in R) \\ \Leftrightarrow (\exists x) (x \in A \land x \in B \land ⟨ x, y ⟩ \in R) \\ \Rightarrow (\exists x) (x \in A \land ⟨ x, y ⟩ \in R) \land (\exists x) (x \in B \land ⟨ x, y ⟩ \in R) \\ \Leftrightarrow y \in R [A] \land y \in R [B] \\ \Leftrightarrow y \in R [A] \cap R [B] \end{aligned}

关系的性质

$R$ 。

$\forall x\in A, xRx$ $R$ 是 自反的；
$\forall x\in A, x\not R x$ $R$ 是 非自反的。
$A$ $R$ $\forall x,y\in A, xRy\to yRx$ $R$ 是对称的；
$\forall x,y\in A, xRy\wedge yRx\to x=y$ $R$ 是 反对称 的；
$\forall x,y\in A, xRy \to y \not R x$ .
$\forall x,y\in A, xRy\to y\not R x$ $R$ 是 非对称 的。
$x,y,z\in A$ $(x Ry\wedge yRz) \to xRz$ $R$ $A$ 上的传递的关系。

性质	定义	关系矩阵	关系图
自反关系	$\forall x\in A, xRx$	对角线全为 1	每个节点都有自环
非自反关系	$\forall x\in A,x\not Rx$	对角线全为 0	每个节点都没有自环
对称关系	$\forall x,y\in A,xRy\to yRx$	$M(R)$ $M(R)=M(R)^\top$	每条边都有反向边
反对称关系	$\forall x,y\in A,(xRy\wedge yRx)\to x=y$	对角线可以为 0,1；非对角线的对称位置不能同时为 1.	每条边都没有反向边，但是可以有自环
非对称关系	$\forall x,y\in A,x Ry\to y\not Rx$	对角线全为 0；非对角线的对称位置不能同时为 1.	每条边都没有反向边，不可以有自环
传递关系	$\forall x,y,z\in A$ $(x Ry\wedge yRz) \to xRz$	$M^2 \vee M=M$ $M^2$ $M$ 里面也为 1.	$u$ $v$ $2$ $u,v$ 也有连边。

关注具体的运算：

"=" 运算，是自反的，对称的，传递的。
$a=a$ $a=b\to b=a$ $a=b\wedge b=c\to a=c$ .
"<" 运算，是非自反的，反对称的，非对称的，传递的。
$a\not<a$ $a<b \wedge b<a$ $a<b\to b\not<a$ $a<b,b<c\to a<c$ .
$\sube$ " 运算，是自反的，反对称的，传递的。
$a\sube a$ $a\sube b \wedge b\sube a \to a=b$ $a\sube b \wedge b\sube c \to a\sube c$ .
$\le$ " 运算，是自反的，反对称的，传递的。
$a\le a$ $a\le b \wedge b\le a \to a=b$ $a\le b \wedge b\le c \to a\le c$ .

Definition（自反、非自反） $A$ $R$ ：

$\forall x\in A, xRx$ $R$ 是自反的；
$\forall x\in A, x\not R x$ $R$ 是非自反的。

Example

$I_A$ $E_A$ $A$ $P(A)$ 上的包含关系和相等关系都是自反的。这些关系都不是非自反的。

非空集合 $A$ $\varnothing$ $\N$ $<$ $A$ $P(A)$ $\subsetneq$ 是非自反的。这些关系都不是自反的。

$A$ $\varnothing$ 是自反的。

$P(A)$ ？

$A=\{1,2\}$ $R=\{\langle 1,1 \rangle, \langle 2,2\rangle,\langle 3,1 \rangle\}$ .

自反关系的图形解释（绿色表示一定存在该关系，红色表示一定不存在该关系，灰色表示不关心）

非自反关系的图形解释：

$R$ $A$ $\boldsymbol M(R)$ $G(R)$ 的每个顶点都有自环；
$R$ $A$ $\boldsymbol M(R)$ $G(R)$ 的每个顶点都没有自环。

$A$ 上，不存在既是自反的，又是非自反的关系。

Definition：对称、反对称、非对称。

$A$ $R$ $\forall x,y\in A, xRy\to yRx$ $R$ 对称 $\forall x,y\in A, xRy\leftrightarrow yRx$ .
$M(R)$ $G(R)$ $e_{i,j}$ $e_{j,i}$ 或者没有连边。
$\forall x,y\in A, xRy\wedge yRx\to x=y$ $R$ 是 反对称 的；
$M(R)$ $i\not=j$ $r_{i,j} \wedge r_{j,i}\not =1$ $G(R)$ $e_{i,j}$ $e_{j,i}$ $i=j$ 。
$\forall x,y\in A, xRy\to y\not R x$ $R$ 是 非对称 的。

$\varnothing$ 是对称的、反对称的、非对称的。

$A=\{1,2\}$ $R=\{\langle 1,2 \rangle, \langle 3,2 \rangle, \langle 2,3 \rangle\}$ .

Definition：传递关系。

$x,y,z\in A$ $(x Ry\wedge yRz) \to xRz$ $R$ $A$ 上的传递的关系。

$\boldsymbol M(R)^2=\boldsymbol M(R)$ .

一些结论：

$R_1,R_2$ $A$ $R_1^{-1},R_1\cap R_2,R_1\cup R_2$ $A$ 上自反的关系。
证明比较容易。
$R_1,R_2$ $A$ $R_1^{-1},R_1\cap R_2,R_1\cup R_2$ $A$ 上对称的关系。
可以利用对称矩阵的性质，也可以利用定义：
$\begin{array}{r} ⟨ x, y ⟩ \in R_{1} \cup R_{2} \Leftrightarrow ⟨ x, y ⟩ \in R_{1} \lor ⟨ x, y ⟩ \in R_{2} \\ \Leftrightarrow ⟨ y, x ⟩ \in R_{1} \lor ⟨ y, x ⟩ \in R_{2} \Leftrightarrow ⟨ y, x ⟩ \in R_{1} \cup R_{2} \end{array}$
$R_1,R_2$ $A$ $R_1^{-1},R_1\cap R_2$ $A$ $R_1\cup R_2$ 不一定是传递的关系。
$\begin{aligned} ⟨ x, y ⟩ \in R_{1} \cap R_{2} \land ⟨ y, z ⟩ \in R_{1} \cap R_{2} \\ \Leftrightarrow & ⟨ x, y ⟩ \in R_{1} \land ⟨ x, y ⟩ \in R_{2} \land ⟨ y, z ⟩ \in R_{1} \land ⟨ y, z ⟩ \in R_{2} \\ \Rightarrow & ⟨ x, z ⟩ \in R_{1} \land ⟨ x, z ⟩ \in R_{2} \\ \Leftrightarrow & ⟨ x, z ⟩ \in R_{1} \cap R_{2} \end{aligned}$

$A$ $R$ ，则
- $R$ $\Leftrightarrow R=R^{-1}$ $\langle x,y \rangle \in R \Leftrightarrow \langle y,x \rangle \in R \Leftrightarrow \langle x,y \rangle \in R^{-1}$ .
- $R$ $\Leftrightarrow R\cap R^{-1}\sube I_A$ .
  $\Rightarrow$ $R$ 是反对称的，
  $\begin{matrix} ⟨ x, y ⟩ \in R \cap R^{- 1} \Leftrightarrow ⟨ x, y ⟩ \in R \land ⟨ x, y ⟩ \in R^{- 1} \\ \Leftrightarrow ⟨ x, y ⟩ \in R \land ⟨ y, x ⟩ \in R \\ \Rightarrow x = y \Rightarrow ⟨ x, y ⟩ \in I_{A} \end{matrix}$
  $R\cap R^{-1} \sube I_A$ .
  $\Leftarrow$ $R\cap R^{-1}\sube I_A$ $R$ $\langle x,y \rangle \in R\wedge \langle y,x \rangle\in R\Rightarrow x=y$ ，从这个条件出发：
  $\begin{matrix} ⟨ x, y ⟩ \in R \land ⟨ y, x ⟩ \in R \Leftrightarrow ⟨ x, y ⟩ \in R \land ⟨ x, y ⟩ \in R^{- 1} \\ \Leftrightarrow ⟨ x, y ⟩ \in R \cap R^{- 1} \Rightarrow ⟨ x, y ⟩ \in I_{A} \Rightarrow x = y \end{matrix}$
  因此得证。

关系的闭包

多个关系的合成（关系的幂）

Definition（多个关系的合成）

$A$ $R$ $n\in \N$ $R$ $n$ $R^n$ 定义如下：

$R^0=\{\langle x,x \rangle\mid x\in A\}=I_A$ .
$R^{n+1} =R^n \circ R(n\ge 0)$ .

Lemma（关系的幂存在循环节） $A$ $|A|=n$ $R$ $A$ $s,t,s\not=t$ $R^{s}=R^t$ $R^s$ $R$ $s$ 次合成。

Proof $i\in N$ $R^i$ $A$ $P(A\times A)$ $|A|=n$ $|P(A\times A)|=2^{n^2}$ 。

$R^0,R^1,\cdots,R^{2^{n^2}}$ $2^{n^2}+1$ $s,t,s\not=t$ $R^{s}=R^t$ .

Lemma（幂次的性质） $A$ $R$ $A$ $m,n$ 是非零自然数，则：

$R^{m+n}=R^m\circ R^n$ .
$R^{mn}=(R^m)^n$ .

Proof：

$m$ $n$ ，

$n=1$ $R^{m+1}=R^m\circ R^1=R^m\circ R$
$n=k(k\ge 1)$ $n=k+1$ $R^{m+k+1}=R^{m+k}\circ R=R^m\circ R^k\circ R=R^m\circ R^{k+1}$ .

$m$ $n$ ，

$n=1$ $R^{m\cdot 1}=R^m$ .
$n=k(k\ge 1)$ $n=k+1$ 时，利用刚刚 1 的结论，有：
$R^{m(k+1)}=R^{mk+m}=R^{mk}\circ R^m=(R^m)^k\circ R^m=(R^m)^{k+1}$ .

Lemma（循环相等的性质） $A$ $R$ $A$ $s,t$ $s<t$ $R^s=R^t$ ，则：

$R^{s+k}=R^{t+k}$ $k$ 是任意的自然数。
$R^{s+kp+i}=R^{s+i}$ $k$ $i$ $p=t-s$ .
$B=\{R^0,R^1,\cdots,R^{t-1}\}$ $R$ $B$ $q$ $R^q\in B$ .

Proof：

$R^{s+k}=R^s \circ R^k =R^t \circ R^k=R^{t+k}$ .
$\begin{matrix} R^{s + (n + 1) p + i} = R^{s + n p + i} \circ R^{p} \\ = R^{s + i} \circ R^{p} = R^{s + p + i} = R^{t + i} = R^{s + i} \end{matrix}$
$q<t$ $B$ $R^q\in B$ ；

$q\ge t$ $q-s>0$ $k,i$ $q=s+kp+i$ $0\le i\le p-1$ $R^q =R^{s+kp+i}=R^{s+i}$ $s+i \le t-1$ .
$R^q=R^{s+i}\in B$ .

闭包的定义

Definition（闭包）：

$A$ $R$ $A$ $R'$ ，满足：

$R'$ 是自反的（对称的，传递的）,
$R\sube R'$ ,
$R'$ $A$ 上满足 1 和 2 的关系中最小的一个。也就是说：
$(\forall R^{″}) (R^{″} 具有某性质 \land R \subseteq R^{″} \to R^{'} \subseteq R^{″})$

$R'$ $R$ $r(R)$ $s(r),t(R)$ ）
$R$ 的关系图中加入最少的边，使得其称为自反（对称，传递）的，即使自反（对称，传递）闭包。

闭包的性质

Lemma（闭包的性质）：

$A$ $R$ ，有 不变性：

$R$ $\Leftrightarrow r(R)=R$ .
$R$ $\Leftrightarrow s(R)=R$ .
$R$ $\Leftrightarrow t(R)=R$ .

Proof：抓住“最小”超集合的概念即可。
$A$ $R_1,R_2$ $R_1\sube R_2$ ，则有 包含关系：

$r(R_1) \sube r(R_2)$ ;
$s(R_1) \sube s(R_2)$ ;
$t(R_1)\sube t(R_2)$ .

Proof：抓住“最小”超集合的概念即可。例如：
$R_1\sube R_2$ $R_2\sube r(R_2)$ $R_1 \sube r(R_2)$ ：

r (R_{2}) 自 反 \land R_{1} \subseteq r (R_{2}) \to r (R_{1}) \subseteq r (R_{2})

$A$ $R_1,R_2$ ，有 并集的关系：

$r(R_1) \cup r(R_2) =r(R_1\cup R_2)$ .
$s(R_1)\cup s(R_2)=s(R_1\cup R_2)$ .
$t(R_1)\cup t(R_2)\sube t(R_1\cup R_2)$ .

Proof $r(R_1)$ $r(R_2)$ $A$ $r(R_1)\cup r(R_2)$ $A$ $R_1\cup R_2 \sube r(R_1)\cup r(R_2)$ $r(R_1)\cup r(R_2)$ $R_1 \cup R_2$ $r(R_1\cup R_2) \sube r(R_1)\cup r(R_2)$ . （最小关系的性质）
$R_1\sube R_1 \cup R_2 \Rightarrow r(R_1)\sube r(R_1\cup R_2)$ $r(R_2)\sube r(R_1\cup R_2)$ $r(R_1)\cup r(R_2)\sube r(R_1\cup R_2)$ .
$r(R_1\cup R_2)=r(R_1)\cup r(R_2)$ .
$t$ $t(R_1)\cup t(R_2)$ $A$ $t(R_1)\cup t(R_2)\sube t(R_1\cup R_2)$ .

闭包的构造方法

Lemma（闭包的构造方法）

构造自反闭包 $A$ $R$ $r(R)=R\cup R^0$ .
构造对称闭包 $A$ $R$ $s(R)=R\cup R^{-1}$ .
构造传递闭包 $A$ $R$ $t(R)=R\cup R^2\cup R^3 \cup \cdots$ .

Proof：

$\forall x\in A,\langle x,x \rangle\in R\cup R^0$ $R\cup R^0$ 是自反的。

$R''$ ，需要证明
$R^{″} 是自反的 \land R \subseteq R^{″} \to R \cup R^{0} \subseteq R^{″}$
$\langle x,y \rangle \in R\cup R^0$ $\langle x,y \rangle \in R$ $\langle x,y \rangle \in R^0$
$\langle x,y \rangle \in R$ $R\sube R''$ $\langle x,y \rangle \in R''$ .
$\langle x,y \rangle \in R^0$ $x=y$ $R''$ $\langle x,y \rangle \in R''$ .
$\forall\langle x,y \rangle( \langle x,y \rangle \in R\cup R^0 \to \langle x,y \rangle \in R'')$ $R\cup R^0 \sube R''$ .

$\forall x,y\in A, \langle x,y \rangle \in R\cup R^{-1}$ ，则

$\langle x,y \rangle \in R$ $\langle y,x \rangle \in R^{-1}\sube R \cup R^{-1}$ .
$\langle x,y \rangle \in R^{-1}$ $\langle y,x \rangle\in R \sube R\cup R^{-1}$ .
$\forall x,y\in A, \langle x,y \rangle \in R\cup R^{-1}\to \langle y,x \rangle\in R\cup R^{-1}$ $R\cup R^{-1}$ 是对称的。
$R''$ ，需要证明
$R^{″} 是对称的 \land R \subseteq R^{″} \to R \cup R^{- 1} \subseteq R^{″}$
$\langle x,y \rangle \in R\cup R^{-1}$ $\langle x,y \rangle \in R$ $\langle x,y \rangle \in R^{-1}$
$\langle x,y \rangle \in R$ $R\sube R''$ $\langle x,y \rangle \in R''$ .
$\langle x,y \rangle \in R^{-1}$ $\langle y,x \rangle \in R$ $R\sube R''$ $\langle y,x \rangle\in R''$ $R''$ $\langle x,y \rangle \in R''$ .
$\langle x,y \rangle \in R\cup R^{-1} \to \langle x,y \rangle \in R''$ $R\cup R^{-1}\sube R''$ .

$n\in \N,n\ge 1$ $R^n \sube t(R)$ $R\cup R^2\cup R^3 \cup \cdots \sube t(R)$ .

$t(R)\sube R\cup R^2\cup R^3 \cup \cdots$ .

$\boldsymbol{t(R)}$ 可以有限构造出）

$A$ $|A|=n$ $R$ $A$ $k\le n$ ，使得：

t (R) = R^{+} = R \cup R^{2} \cup \dots \cup R^{k}

Proof $k\le n$ .

Algorithm（Warshall）

$\boldsymbol B[j,i]$ $\boldsymbol B$ $j$ $i$ 列的元素；

$\boldsymbol B=\boldsymbol M(R)$ .
$i=1,n=|A|$ .
$1\le j\le n$ $\boldsymbol B[j,i]=1$ $1\le k\le n$ ，令：
$B [j, k] = B [j, k] \lor B [i, k]$
$i=i+1$ .
$i\le n$ ，则转到 3，否则停止。

闭包的性质

Theorem

$R$ $s(R),t(R)$ 是自反的；
$R$ $r(R),t(R)$ 是对称的；
$R$ $r(R)$ 是传递的。

Proof：

$s(R),t(R)$ 中都能保持；
$a$ $b$ $b$ $a$ .

Theorem $A$ $R$ ，有：

$rs(R)=sr(R)$ .
$rt(R)=tr(R)$ .
$st(R)\sube ts(R)$ .

Proof：利用闭包的构造方法。

也就是说，如果把一个有向图变成无向图，则可能出现新的“联通关系”

等价关系和划分

常见的等价关系：

$I_A$ ，一个数就是一个等价类；
谓词公式的等值，一个等价类有无穷多种谓词公式；
$m$ $i,i+m,i+2m\cdots$ 就是一个等价类。
$E_A$ $A$ $A$ 是一个等价类。

等价关系、等价类

Definition（等价关系）

$A$ $R$ $R$ $R$ $A$ 上的等价关系。

等价关系在关系矩阵和关系图中的表示：

$(a,b),(b,c)$ $(a,c)$ 一定属于矩阵。因此只能是一个是一个一个正方形。
如果不存在传递性，只能是一个对称矩阵，如果不存在对称性，只能由一个一个阶梯型构成。
在关系图中，表现为关系图由一个一个全联通图组成。

Definition（等价类）

$R$ $A$ $x\in A$ ，令

[x]_{R} = {z ∣ z \in A \land x R z}

$[x]_R$ $x$ $R$ 的 等价类。

Theorem（等价类满足的性质）

$[x]_R \not=\varnothing$ $[x]_R \sube A$ .
$xRy$ $[x]_R =[y]_R$ .
$x\not R y$ $[x]_R \cap [y]_R =\varnothing$ .
$\cup \{[x]_R \mid x\in A\}=A$ .

Proof：

显然；
$[x]_R \sube [y]_R$ $yRx$ ，有：
$z \in [x]_{R} \Rightarrow z \in A \land x R z \overset{y R x}{\Rightarrow} z \in A \land y R z \Rightarrow z \in [y]_{R}$
$[y]_R\sube [x]_R$ $[x]_R=[y]_R$ .
$yRz$ $xRz$ $xRy$ $yRz$ $x\not Ry$ $x\not Rz$ ：
$z \in [y]_{R} \Rightarrow z \in A \land y R z \overset{x R̸ y}{\Rightarrow} z \in A \land x R̸ z \Rightarrow z \notin [x]_{R}$
$[x]_R\cap [y]_R=\varnothing$ .
$x\in A,[x]_R\sube A$ $\cup \{[x]_R \mid x\in A\}\sube A$ ；

$x\in A$ $x\in [x]_R$ $x\in \cup \{[x]_R \mid x\in A\}$ $A\sube \cup \{[x]_R \mid x\in A\}$ .
$\cup \{[x]_R \mid x\in A\}=A$ .

Definition（商集）

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

$A$ $A$ $R$ 是同余 3 的关系，则：

A / R = {{1, 4, 7}, {2, 5, 8}, {3, 6}}

划分

$\{a,b,c,d\}$ $\{\{a\},\{b\},\{c,d\}\}$ ，思考怎么用数学语言来表示合法的划分。

Definition（划分、划分块）

$A$ $\pi$ 满足下列条件：

$(\forall x)(x\in \pi \to x\sube A)$ $A$ 以外的元素）
$\varnothing \notin \pi$ ；（不存在空集）
$\cup \pi =A$ ；（不漏）
$(\forall x)(\forall y)((x\in \pi \wedge y\in \pi \wedge x\not=y)\to x\cap y =\varnothing)$ ；（不重）

$\pi$ $A$ 划分 $\pi$ $A$ 的 划分块。

Theorem（商集是划分）

$A$ $R$ $A$ $A/R$ $A$ $R$ $A$ $\pi_R$ .

Proof：利用等价类的性质。

Lemma（通过等价关系构造划分） $A$ $\pi$ $A$ $R_\pi$ 为：

R_{π} = {⟨ x, y ⟩ ∣ (\exists z) (z \in π \land x \in z \land y \in z)}

$R_\pi$ $A$ $\pi$ 诱导 $A$ 上的等价关系。

Lemma（等价关系和划分一一对应） $A$ $\pi$ $A$ $R$ $\pi$ $R$ $R$ $\pi$ .

先证必要性 $\pi$ $R$ $R$ $\pi'$ $x\in A$ $x$ $\pi$ $B$ $\pi'$ $B'$ $\pi=\pi'$ $B=B'$ $y\in A$ ，有：

y \in B \overset{π 诱 导 R}{\Leftrightarrow} x R y \Leftrightarrow [x]_{R} = [y]_{R} \overset{R 诱 导 π^{'}}{\Leftrightarrow} y \in B^{'}

$B=B'$ $x$ $\pi=\pi'$ .

再证明充分性 $R$ $\pi$ $\pi$ $R'$ $x,y\in A$ ，有：

\begin{matrix} x R y \Leftrightarrow [x]_{R} = [y]_{R} \Leftrightarrow x \in [x]_{R} \land y \in [y]_{R} \\ \Leftrightarrow x, y 在 π 的 一 个 划 分 块 里 面 \Leftrightarrow x R^{'} y \end{matrix}

相容关系和覆盖

Definition（相容关系）

$A$ $R$ $R$ $R$ $A$ 上的相容关系。

从图论的角度看，每个顶点都有自环，且没有有向边，都是无向边。

Definition（相容类）

$C\sube A$ $C$ $x$ $y$ $xRy$ $C$ $R$ 产生的相容类，简称相容类（也就是一个团）

C = {x ∣ x \in A \land (\forall y) (y \in C \to x R y)}

Definition（最大相容类）

$A$ $R$ $C_R$ .

最大相容类的性质：

$(\forall x)(\forall y)((x\in C_R \wedge y\in C_R)\to xRy)$ . 互相有关系
$(\forall x)(x\in A-C_R \to (\exists y)(y\in C_R \wedge x\not Ry))$ . 不能加入新的元素

从图论的角度看，就是最大子团。

Theorem（最大相容类的构造） $A$ $R$ $C$ $C_R$ $C \sube C_R$ .

Proof $C$ $n-|C_0|$ 步。

Lemma（每个元素都有对应包含的最大相容类） $\{a\}$ 出发即可。这样的最大相容类不唯一，因为选择元素的序列可能不同。

Definition（覆盖）

$A$ $\Omega$ ，满足下列条件：

$(\forall x)(x\in \Omega \to x\sube A)$ ；
$\varnothing \notin \Omega$ .
$\cup \Omega =A$ .

$\Omega$ $A$ $\Omega$ $\Omega$ 的覆盖块。

Examples.

一个划分是一个覆盖，但是一个覆盖不一定是一个划分；
$A$ $R$ $A$ $A$ 完全覆盖 $C_R(A)$ $C_R(A)$ 是唯一的。
$A$ $R$ $A$ $C_R(A)$ .
用覆盖的子集的笛卡尔积（也就是子集的完全图）求并，得到的关系，是相容关系。
不同的覆盖可能确定相同的相容关系，比如：
$\begin{matrix} Ω_{1} = {{1, 2, 3}, {3, 4}}; \\ Ω_{2} = {{1, 2}, {2, 3}, {1, 3}, {3, 4}} \end{matrix}$

偏序关系

偏序关系和拟序关系

Definition（偏序关系）

$(P,\le)$ $P$ $\le$ 组成的二元组。满足以下性质：

$(\forall a\in P)(a\le a)$ .
$(\forall a,b\in P)(a\le b\wedge b\le a\to a=b)$ .
$(\forall a,b,c\in P)(a\le b\wedge b\le c \to a\le c)$ .

$\le$ 需要满足自反性、反对称性、传递性。

Definition（拟序关系）

$<$ 需要满足非自反性、传递性。

$(\forall a)(a \not<a)$ .
$(\forall a,b,c)(a< b \wedge b < c\to a<c)$ .

$a<b \wedge b<a$ 为假。因此，拟序关系也符合反对称性。

Lemma（拟序关系和偏序关系的相互转换）

也就是有没有取等：

$A$ $R$ $R\cup R^0$ $A$ 上的偏序关系；
$A$ $R$ $R-R^0$ $A$ 上的逆序关系。

因此，拟序关系和偏序关系的区别只是自反性。

Examples 可以验证，

$U$ $(2^U,\sube)$ 是一个偏序集。主要根据集合包含的性质。
$a,b\in \Z$ $a\le b$ $a|b$ $(\Z,\le)$ 是一个偏序集。证明，可以将整数用其所有因数组成的集合表示，可以转换为集合包含的关系。例如：
$2 | 4 \Rightarrow {1, 2} \subseteq {1, 2, 4}$

Hasse 图

$a<b$ $c$ $a<c<b$ $a$ $b$ 连边；也就是 不画自环 和 传递关系得到的有向边。

Definition（盖住关系） $(A,\le)$ $x,y\in A,x\le y,x\not=y$ $z\in A$ $x\le z$ $z\le y$ $y$ $x$ $A$ $\operatorname{cov}(A)$ 定义为：

cov A = {⟨ x, y ⟩ ∣ x \in A \land y \in A \land y 盖 住 x}

Example $\{1,2,3,4,6,12\}$ $D_A$ $A$ $A$ $\operatorname{cov}A$ 为：

cov A = {⟨ 1, 2 ⟩, ⟨ 1, 3 ⟩, ⟨ 2, 4 ⟩, ⟨ 2, 6 ⟩, ⟨ 3, 6 ⟩, ⟨ 4, 12 ⟩, ⟨ 6, 12 ⟩}

$y$ $x$ $y/x$ 为质数。

$(2^{[n]},\sube)$ 的 Hasse 图：

$(P,\sube)$ $x$ $y\in P$ $y>x$ $x$ 是一个极大元素。
$x$ $z\in P$ $z\le x$ ，则称为最大元素。
类似定义极小元素和最小元素。

一个偏序集可能不存在最大和最小元素。

$P=\{2,3,4,5,6\}$ 上的整除关系，4,5,6 都是极大元素，但是没有最大元素。

$(2^{[n]},\sube)$ $\{1,2,3\}$ .

Definition（最大最小元，极大极小元）

$(\exist y)(y\in B\wedge (\forall x)(x\in B\to y\le x))$ $y$ $B$ 的最小元；
$(\exist y)(y\in B\wedge (\forall x)(x\in B\to x\le y))$ $y$ $B$ 的最大元；
$(\exist y)(y\in B\wedge (\forall x)((x\in B\wedge x\le y)\to x=y))$ $y$ $B$ 的极小元；
$(\exist y)(y\in B\wedge (\forall x)((x\in B\wedge y\le x)\to x=y))$ $y$ $B$ 的极大元。

$y$ $B$ 中其他元素都有关系，而且都小于等于/大于等于它们，则称为最小/最大元；（要求比较严格，必须能够比较）
$y$ $B$ 中有关系的元素比较，都小于等于/大于等于它们，称为极大/极小元。

Lemma（最大最小元存在必唯一）

Proof $y_1,y_2$ $B$ $y_2 \in B\to y_1 \le y_2$ $y_1 \in B\to y_2\le y_1$ $y_1=y_2$ .

Lemma（最大最小元是极大极小元）

Proof $y$ $B$ $(\forall x)(x\in B\to x\le y)$ $y\le x \wedge x\le y$ $x=y$ . 因此是极大元。

Definition（上（下）确界）

$(A,\le)$ $B\sube A$ ，进一步定义：

$(\exists y)(y\in A\wedge (\forall x)(x\in B \to x\le y))$ $y$ $B$ $B$ 中所有元素的元素，不一定存在）
$(\exists y)(y\in A\wedge (\forall x)(x\in B \to y\le x))$ $y$ $B$ $B$ 中所有元素的元素，不一定存在）
$C=\{y\mid y 是 B 的上界\}$ $C$ $B$ 的上确界或最小上界；（不一定存在，如果存在必唯一）
$C=\{y\mid y 是 B 的下界\}$ $C$ $B$ 的下确界或最大下界。（不一定存在，如果存在必唯一）

Definition（全序关系）

$(P,\le)$ $\le$ $\le$ 是全序关系。

(\forall x, y) (x \leq y \lor y \leq x)

Definition（良序关系）

$(A,\le)$ $A$ $\le$ $(A,\le)$ 为良序集。

$(\N,\le)$ 是全序集，也是良序集；
$(\Z,\le)$ 是全序集，但是不是良序集。

Proof（一个良序集一定是全序集）

$x,y\in A$ $\{x,y\}\sube A$ $x$ $y$ $x\le y$ $y\le x$ $(A,\le)$ 是全序集。

Proof（一个有限的全序集一定是良序集）

$(A,\le)$ 是有限的全序集

$B\in A$ $x,y\in B$ $x,y$ 无关系，和全序集矛盾。

Theorem（Zorn）

对于一个非良序的集合，可以定义集合上的一个全序关系，使该集合成为良序集。

任何集合都是可以良序化的。良序定理、Zorn 引理、选择公理三者等价。

$(\Z,\le)$ $\Z$ $R$ 为：

| a | \leq | b | ⟹ a R b

$\Z$ $(\Z,R)$ 是良序集。

Definition（区间）

$(R,\le)$ $a,b \in R,a\not=b,a\le b$ ，则：

$[a,b]=\{x\mid x\in R\wedge a\le x \le b\}$ $a$ $b$ 的闭区间；
$(a,b)=\{x\mid x\in R \wedge a\le x \le b \wedge x\not= a \wedge x\not= b\}$ $a$ $b$ 的开区间；
定义半开区间……

Definition（链）

$(P,\le)$ $C\sube P$ $C$ $C$ $P$ 的一个链。

(\forall x, y) (x \in C \land y \in C \to x \leq y \lor y \leq x)

Definition（反链）

$(P,\le)$ $C\sube P$ $C$ $C$ $P$ 的一个反链。

(\forall x, y) (x \in C \land y \in C \to x ≰ y \land y ≰ x)

Definition（链和反链的长度）

$(P,\le)$ $C\sube P$ $|C|=n$ $C$ $P$ $n$ $C\sube P$ $|C|=n$ $C$ $P$ $n$ 反链。

Definition

极大链：我们说一个链是极大的，当且仅当把任何一个其它的元素添加进去之后都不再是一个链。
最大链 则定义为元素最多的链。

都不是唯一的。

Definition 个偏序集的宽度则被定义为其中最大反链的大小。

从 Hasse 图理解这件事情

$\{\{1,2,3\},\{2\}\}$ 是链（在 Hasse 图上不一定连续）
$\{\varnothing,\{2\},\{2,3\},\{1,2,3\}\}$ 是极大链，同时也是最大链。
$\{\{1\},\{2,3\}\}$ 是极大反链；
$\{\{1\},\{2\},\{3\}\}$ 是极大反链，也是最大反链。

链划分和反链划分

Definition

链划分 $\mathcal C=\set{C_1,C_2,\dots,C_m}$ $P$ $i,j\in [m],i\not=j\implies C_i\cap C_j=\varnothing$ .
类似定义 反链划分。

Theorem 任何偏序集最小反链划分的大小等于其高度。

证明类似于一层一层剥下来。

Theorem 任何偏序集最小链划分的大小等于其宽度。

$|P|$ $|P|$ 的偏序集都成立……

关系的计数

$|A|=n$ ，则：

$A$ $2^{n\times n}$ 种；
$2^{n^2-n}$ 种（固定了对角线元素）；
$2^{\sum_{i=1}^ni}=2^{(n(n+1)/2)}$ 种；
$x\not=y$ $(0,0),(0,1),(1,0)$ $x=y$ ，取值没有限制。因此一共：
$3^{(n (n - 1) / 2)} \cdot 2^{n}$
种；
$3^{(n(n-1)/2)}$ 种。
$k$ $\sum_{k=0}^n S(n,k)$ 种。递推表达式为：
$r_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} r_{k}$
传递关系、偏序关系的计数比较困难。可以去 OEIS 搜一下。

关系性质的保持

$A\times A$ $R_1,R_2$ 取逆/交/并/合成/平方是否能够保持自反性、非自反性、对称性、反对称性、传递性。

	$^{-1}$	$\cap$	$\cup$	$\circ$	$^2$
自反	可以	可以	可以	可以	可以
非自反	可以	可以	可以	不可以(24)	不可以 (25)
对称	可以	可以	可以	不可以(34)	可以 (35)
反对称	可以	可以	不可以(43)	不可以(44)	不可以(45)
传递	可以	可以	不可以(53)	不可以(54)	可以 (55)

反例及说明：

$A=\{1,2\}$ $R_1=\{\langle 1,2 \rangle\},R_2=\{\langle 2,1 \rangle\}$ $\langle 2,2 \rangle$ $R_1\circ R_2$ 中。

$A=\{1,2\}$ $R_1=\{\langle 1,2 \rangle,\langle 2,1 \rangle\}$ $\langle 2,2 \rangle$ $R_1^2$ 中。

$A=\{1,2,3\}$ $R_1=\{\langle 1,2 \rangle,\langle 2,1 \rangle \}$ $R_2=\{\langle 2,3 \rangle,\langle 3,2 \rangle\}$ .

$R_1\circ R_2=R_2\circ R_1$ 的关系都可以保持对称性。

$A=\{1,2\}$ $R_1=\{\langle 1,2 \rangle\},R_2=\{\langle 2,1 \rangle\}$ .

$A=\{1,2,3\}$ $R_1=\{\langle 1,2 \rangle,\langle 2,3 \rangle,\langle 1,3 \rangle\}$ $R_2=\{\langle 2,1 \rangle,\langle 3,2 \rangle,\langle 3,1 \rangle\}$ .

$\langle 2,3 \rangle$ $\langle 3,2 \rangle$ $R_1\circ R_2$ 中。

$A=\{1,2,3,4\}$ $R_1=\{\langle 1,2 \rangle,\langle 2,4 \rangle,\langle 4,3 \rangle,\langle 3,1 \rangle\}$ $\langle 4,1 \rangle$ $\langle 1,4 \rangle$ $R_1^2$ 中。

$A=\{1,2,3\}$ $R_1=\{\langle 2,3 \rangle\},R_2=\{\langle 1,2 \rangle\}$ .

$A=\{1,2,3\}$ $R_1=\{\langle 1,2 \rangle,\langle 2,3 \rangle,\langle 1,3 \rangle\}, R_2 = \{\langle 3,1 \rangle,\langle 1,2 \rangle,\langle 3,2 \rangle\}$ .

$R_1\circ R_2=\{\langle 3,2 \rangle,\langle 3,3 \rangle,\langle 1,3 \rangle\}$ 。

Theorem (55) $R$ $R^2$ 也是传递关系：

Proof：

\begin{matrix} x R^{2} y \land y R^{2} z \Rightarrow x R s \land s R y \land y R t \land t R z \\ \Rightarrow x R y \land y R z \Rightarrow x R^{2} z \end{matrix}

往年题目

$n$ $n$ $k$ $k$ $C_{n-1}^k$ $n-1-k$ $r_{n-1-k}$ 种等价关系。因此：

r_{n} = \sum_{k = 0}^{n - 1} C_{n - 1}^{k} r_{n - 1 - k} = \sum_{k^{'} = 0}^{n - 1} C_{n - 1}^{k^{'}} r_{k^{'}}

化为题目要求的形式，也就是：

r_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} r_{k}

可以写出前几项：

1, 1, 2, 5, 15, 52, 203

称为贝尔数列。

还可以通过第二类斯特林数求出其通项，

第二类斯特林数 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ $S(n,k)$ $n$ $k$ 个互不区分的非空子集的方案数。

递推式

{\begin{matrix} n \\ k \end{matrix}} = {\begin{matrix} n - 1 \\ k - 1 \end{matrix}} + k {\begin{matrix} n - 1 \\ k \end{matrix}}

$\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]$ 。

考虑用组合意义来证明。

我们插入一个新元素时，有两种方案：

$\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}$ 种方案；
$k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$ 种方案。

根据加法原理，将两式相加即可得到递推式。

通项公式

{\begin{matrix} n \\ m \end{matrix}} = \sum_{i = 0}^{m} \frac{(- 1)^{m - i} i^{n}}{i! (m - i)!}

根据定义，我们有：

\begin{matrix} r_{n} = \sum_{k = 1}^{n} {\begin{matrix} n \\ k \end{matrix}} = \sum_{k = 1}^{n} \sum_{i = 0}^{k} \frac{(- 1)^{k - i} i^{n}}{i! (k - i)!} \end{matrix}

$<_A$ $<_B$ $A,B$ $A\times B$ $<_L$ 如下：

⟨ a, b ⟩ <_{L} ⟨ a^{'}, b^{'} ⟩ \Leftrightarrow either a <_{A} a^{'} or (a = a^{'} \land b <_{B} b^{'})

$<_L$ 也是一个线序关系。

$<_L$ $a\not<_A a$ $a=a \wedge b\not<_Bb'$ 均不成立。
$<_L$ 具有传递性：
$\langle a,b \rangle<_L \langle a',b' \rangle$ $\langle a',b' \rangle<_L\langle a'',b'' \rangle$ ，则：
- $a<_A a'$ $a'<_A a''$ $<_A$ $a<_A a''$ $\langle a,b \rangle<_L \langle a'',b'' \rangle$ .
- $a<_A a'$ $a'=a'' \wedge b'<_B b''$ $a<_A a''$ $\langle a,b \rangle<_L \langle a'',b'' \rangle$ .
- $a=a' \wedge b<_B b'$ $a'<_A a''$ $a<_A a''$ $\langle a,b \rangle<_L \langle a'',b'' \rangle$ .
- $a=a' \wedge b<_B b'$ $a'=a'' \wedge b'<_B b''$ $a=a''\wedge b<_B b''$ $\langle a,b \rangle<_L \langle a'',b'' \rangle$ .
$<_L$ 具有传递性。

$<_L$ 是一个线序关系。