二元关系

二元关系（binary relation），有时简称关系，代指数学上两种物件之间的联系。举凡算术中的“大于”、“小于”以及“等于”，几何学上的“相似”和“全等”，抑或是集合论中的“属于”和“包含于”等，都是所属领域的二元关系。

## 定义

### 集合论方法

给定集合$A$和$B$，若集合$R$为卡氏积$A \times B$的子集，则可称其为$A$到$B$的二元关系。特别地，给定集合$X$，若取集合$S$为$X \times X$的一个子集，则称其为“$X$上”的二元关系。例如，前述从$A$到$B$的二元关系$R$，亦可视为一个在联集$A \cup B$上的二元关系。

将上述文字以形式语言写作：

$$R \subseteq A \times B,$$或者说$$(\forall r \in R)(\exists a \in A)(\exists b \in B)[r = (a, b)],$$ 其中$(a, b)$表示一个有序对。

若集合$A$的元素$a$和$B$的元素$b$满足$(a, b) \in R$，则称$a$和$b$存有关系$R$，可记作$aRb$。

### 范畴论方法

然而，若仅采取集合论方法，单独给定一个二元关系（有序对的集合），有时会产生歧异。例如，一个从$\{1, 2\}$到$\{2\}$的二元关系$T = \{(1, 2), (2, 2)\}$，也可被视为从$\{1, 2, 3\}$到$\{2, 3\}$的二元关系。

为了解决这种歧异，在范畴论（或布林巴基学派）中，从集合$A$到$B$的二元关系被定义为一个三元有序对：

$$R = (A, B, G(R)).$$ 其中称$A$为源集合（定义域），$B$为靶集合（陪域），而$A \times B$的子集$G(R)$则被称作此关系的图。以上述的集合$T$为例，在范畴论中，产生歧异的两种视角会被精确地写作两个不同的三元组：

- $$(\{1, 2\}, \{2\}, \{(1, 2), (2, 2)\})$$
- $$(\{1, 2, 3\}, \{2, 3\}, \{(1, 2), (2, 2)\})$$

这两个关系的“图”皆为$T$。

这种看似繁复的定义，其必要性体现在范畴论对态射的基本要求：任意态射必须具备唯一且确定的源物件与靶物件。此定义也因而成为合法建构关系范畴最精简的方法。

实务上，这里常涉及数学上常见的“符号的滥用”（abuse of notation）──即关系本身与其“图”被视为同一物，因而出现将三元组$R$直接写作$R \subseteq A \times B$、$R = G(R)$或$(a, b) \in G(R)$被记作$aRb$之类的语法。

## 示例

### 集合到集合的关系

- 任意从集合$A$到$B$的映射$f$，都是从$A$到$B$的二元关系，并满足：

$$(\forall a \in A)(\exists! b \in B)[(a, b) \in f].$$

具体来说，以正整数集$\mathbb{Z}^+$的模$3$运算（$\text{mod }3$）为例，其可被定义为

$$\{(n, r) \in \mathbb{Z}^+ \times \{0, 1, 2\} \mid (\exists q \in \mathbb{N})(n = 3q + r)\} = \{(1, 1), (2, 2), (3, 0), (4, 1), \dots\}.$$

- 从质数的集合$P = \{2, 3, 5, 7\}$到合数的集合$C = \{6, 8, 9, 10\}$的整除关系（记作 $\mid$）可被定义为

$$\{(p, c) \in P \times C \mid (\exists q \in \mathbb{Z}^+)(c = pq)\} = \{(2, 6), (2, 8), (2, 10), (3, 6), (3, 9), (5, 10)\}.$$

### 集合上的关系

- 任意集合$X$上的空关系，被定义为空集合$\varnothing$。
- 任意集合$X$上的全域关系（$E_X$），或称完全关系，被定义为$X \times X$。
- 任意集合$X$上的恒等关系（$I_X$），被定义为$\{(x, y) \in X \times X \mid x = y\}$。
- 实数集$\mathbb{R}$上的大于关系（$>$），可被定义为$\{(x, y) \in \mathbb{R} \times \mathbb{R} \mid (\exists r \in \mathbb{R}^+)(x = y + r)\}$。

## 关系表示法

### 关系矩阵

给定集合$X = \{x_1, x_2, \dots, x_n\}$和$Y = \{y_1, y_2, \dots, y_m\}$，$R$为从$X$到$Y$的一个关系，并令$$r_{ij} = \begin{cases} <pre> 1, & (x_i, y_j) \in R \\ 0, & (x_i, y_j) \notin R </pre> \end{cases},$$ 其中$i, j \in \mathbb{Z}^+$，而$i \le n$且$j \le m$。

则$R$的关系矩阵，记作$M_{R}$，为以下的布林矩阵（或称0,1矩阵）：

$$M_R = (r_{ij})_{n \times m} = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1m} \\ r_{21} & r_{22} & \cdots & r_{2m} \\ \vdots & \vdots & \vdots & \vdots \\ r_{n1} & r_{n2} & \cdots & r_{nm} \end{bmatrix}.$$

### 关系图

给定集合$X = \{x_1, x_2, \ldots, x_n\}$，令$R$为$X$上的一个二元关系，图$G = (V, E)$，其中顶点集合$V = X$，边集合为$E$，且满足$$(\forall x_i \in V)(\forall x_j \in V)[(x_i, x_j) \in E \iff x_i R x_j].$$ 则可称图$G$是关系$R$的关系图，亦可记作$G_R$。此与前文所提及的“关系的图”是不同的观念，“关系的图”是一个集合，而“关系图”通常是关系的视觉展示。

## 运算

给定从集合$A$到$B$的二元关系$R$，以下为一些关系$R$的基本运算：

- 定义域：$R$中所有有序对$(a, b)$的第一元素$a$所构成的集合被称为$R$的定义域，记作$\operatorname{dom}(R)$。形式语言写作

$$\operatorname{dom}(R) = \left\{a \in \bigcup \bigcup R \;\Big|\; (\exists b)[(a, b) \in R]\right\}.$$

需注意的是$\operatorname{dom}(R) \ne A$，而是$\operatorname{dom}(R) \subseteq A$。

- 值域：$R$中所有有序对$(a, b)$的第二元素$b$所构成的集合被称为$R$的值域，记作$\operatorname{ran}(R)$。形式语言写作

$$\operatorname{ran}(R) = \left\{b \in \bigcup \bigcup R \;\Big|\; (\exists a)[(a, b) \in R]\right\}.$$

需注意的是$\operatorname{ran}(R) \ne B$，而是$\operatorname{ran}(R) \subseteq B$。

- 域：$R$的定义域和值域的联集被称为$R$的域，记作$\operatorname{fld}(R)$，形式语言写作

$$\operatorname{fld}(R) = \operatorname{dom}(R) \cup \operatorname{ran}(R) = \bigcup \bigcup R.$$

- 复合关系：给定关系$F$和$G$，“物件$f$透过$F$，再透过$G$与物件$g$建立的关系”被称为$F$与$G$的复合关系，记作$F \mathbin{;} G$，定义为

$$F \mathbin{;} G = \big\{(f, g) \in \operatorname{dom}(F) \times \operatorname{ran}(G) \;\big|\; (\exists x)\{[(f, x) \in F] \land [(x, g) \in G]\}\big\}.$$

此处复合关系“先$F$再$G$”的顺序，与微积分中常见的复合函数$\textbf{F} \circ \textbf{G}$，所依循的“先$\textbf{G}$再$\textbf{F}$”相反。

- 逆关系：$R$的逆关系，简称$R$的逆，记作$R^{-1}$，被定义为

$$R^{-1} = \{(b, a) \in \operatorname{ran}(R) \times \operatorname{dom}(R) \mid (a, b) \in R\}.$$

值得注意的是，复合关系$(R \mathbin{;} R^{-1})$和$(R^{-1} \mathbin{;} R)$会分别包含恒等关系（$I_{\operatorname{dom}(R)}$和$I_{\operatorname{ran}(R)}$），然而不见得两复合关系相等，或与其对应的恒等关系相等。

- 限制：给定集合$X$。关系$R$中从$X$出发的部分被称为$R$在$X$上的限制，记作$R \upharpoonright X$，定义为

$$R \upharpoonright X = \{(a, b) \in R \mid a \in X\}.$$

- 像：给定集合$X$。与$X$的任意元素有关系$R$的物件，所构成的集合被称为$X$在$R$下的像，记作$R[X]$，定义为

$$R[X] = \operatorname{ran}(R \upharpoonright X).$$

- 幂运算：给定集合$X$及$X$上的关系$S$。“重复复合关系$S$”被称为$S$的幂运算，遵守如下规则：

$$S^{n} = \begin{cases} I_X, & n = 0 \\ S^{n - 1} \mathbin{;} S, & n \in \mathbb{Z}^+ \end{cases}.$$

## 性质

给定集合$X$上的二元关系$R$，通常主要考虑关系$R$是否具有以下三种性质（或其相关变体）：

### 自反性

- 自反性：$(\forall x \in X)(xRx)$，意即$X$的任意元素都与元素本身具有关系$R$。

此性质与$I_X \cap R = I_X$，或者说$I_X \subseteq R$等价。

- 非自反性：$(\exists x \in X)[\neg(xRx)]$，意即$X$有元素不与元素本身具有关系$R$。

此性质与$I_X \cap R \subset I_X$等价。

- 反自反性：$(\forall x \in X)[\neg(xRx)]$，意即$X$的任意元素都不与元素本身具有关系$R$。

此性质与$I_X \cap R = \varnothing$等价。

### 对称性

- 对称性：$(\forall x \in X)(\forall y \in X)(xRy \implies yRx)$。

此性质与$R = R^{-1}$等价。

- 不对称性（non-symmetric）：$(\exists x \in X)(\exists y \in X)[xRy \land \neg(yRx)]$。
- 非对称性（asymmetric）：$(\forall x \in X)(\forall y \in X)[xRy \implies \neg(yRx)]$。

此性质与$R \cap R^{-1} = \varnothing$等价。

- 反对称性（antisymmetric）：$(\forall x \in X)(\forall y \in X)[(xRy \land yRx) \implies x = y]$。

此性质与$R \cap R^{-1} \subseteq I_X$等价。

以上对称性的各种变体皆在描述$xRy$与$yRx$之间的联系。

### 传递性

- 传递性：$(\forall x \in X)(\forall y \in X)(\forall z \in X)[(xRy \land yRz) \implies xRz]$。

此性质与$(R \mathbin{;} R) \subseteq R$等价。

- 非传递性：$(\exists x \in X)(\exists y \in X)(\exists z \in X)[xRy \land yRz \land \neg(xRz)]$。
- 反传递性：$(\forall x \in X)(\forall y \in X)(\forall z \in X)[(xRy \land yRz) \implies \neg(xRz)]$。

此性质与$(R \mathbin{;} R) \cap R = \varnothing$等价。

以上传递性的各种变体皆在描述$xRy$、$yRz$与$xRz$之间的联系。

## 闭包

### 性质

给定集合$X$上的二元关系$R$。若一个$X$上的二元关系$S$满足：

- 包含性：$S \supseteq R$。
- 自反性：$S$是自反的。
- 最小性：$S$对任意包含$R$的$X$上自反关系$T$，满足$S \subseteq T$。

则称$S$为$R$的自反闭包，也常记作$r(R)$或$R^{=}$。

将上述条件中所有的“自反”替换成“对称”，则称$S$为$R$的对称闭包，记作$s(R)$；替换成“传递”，则称为传递闭包，记作$t(R)$。

### 构造

以下为自反、对称及传递闭包的构造方法：

- 自反闭包：$r(R) = R \cup R^0 = R \cup I_X$。
- 包含性：$R \subseteq R \cup I_X = r(R)$。
- 自反性：由于$I_X \subseteq r(R)$，有$(\forall x \in X)[(x, x) \in r(R)]$，故$r(R)$是自反的。

对任意$X$上的自反关系$T$，有$(\forall x \in X)[(x, x) \in T]$，即$I_X \subseteq T$。

若同时$R \subseteq T$，则$r(R) = R \cup I_X \subseteq T$。

以$X = \{1, 2, 3\}$、$R = \{(1, 1), (1, 2), (2, 3)\}$为例。

$r(R) = R \cup \{(1, 1), (2, 2), (3, 3)\} = \{(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)\}$。

- 对称闭包：$s(R) = R \cup R^{-1}$。
- 包含性：$R \subseteq R \cup R^{-1} = s(R)$。

若$(x, y) \in s(R)$，则$(x, y) \in R$或$(x, y) \in R^{-1}$成立，分别使得$(y, x) \in R^{-1}$或$(y, x) \in R$。

而$(y, x) \in s(R)$。故$s(R)$是对称的。

对任意$X$上的对称关系$T$，若$R \subseteq T$。

则$(x, y) \in R \implies (y, x) \in T$，而有$R^{-1} \subseteq T$。故$s(R) = R \cup R^{-1} \subseteq T$。

以$X = \{1, 2, 3\}$、$R = \{(1, 1), (1, 2), (2, 3)\}$为例。

$s(R) = R \cup \{(1, 1), (2, 1), (3, 2)\} = \{(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)\}$。

- 传递闭包：$t(R) = \bigcup_{i \in \mathbb{Z}^+} R^i = R \cup R^2 \cup R^3 \cup \cdots$。
- 包含性：$R \subseteq R \cup R^{2} \cup \cdots = t(R)$。

若$(x, y) \in t(R)$且$(y, z) \in t(R)$，则存在正整数$m$和$n$使得$(x, y) \in R^m$而$(y, z) \in R^n$。

根据复合关系定义与幂运算规则，可得$(x, z) \in R^m \mathbin{;} R^n = R^{m + n}$。

由于$m + n \in \mathbb{Z}^+$，$R^{m + n} \subseteq t(R)$，使得$(x, z) \in t(R)$。故 $t(R)$满足传递性。

对任意$X$上的传递关系$T$，若$R \subseteq T$，使用数学归纳法可以证明对所有正整数$n$都有$R^n \subseteq T$：

- 当$n = 1$时，根据已知条件有$R^1 = R \subseteq T$成立。
- 假设当$n = k$时，$R^k \subseteq T$成立。
- 当$n = k + 1$时，考虑$R^{k + 1}$中任意有序对$(x, z)$。

因$R^{k + 1} = R^k \mathbin{;} R$，而存在$y \in X$使得$(x, y) \in R^k$且$(y, z) \in R$。

由归纳假设可知$(x, y) \in T$，已知条件可知 $(y, z) \in T$，又$T$具传递性，因此$(x, z) \in T$。

综上所述，$R^{k+1} \subseteq T$成立。

根据数学归纳法，对所有正整数$n$都有$R^n \subseteq T$。故$t(R) = R \cup R^2 \cup R^3 \cup \cdots \subseteq T$。

有趣的是，若$|X| = n$，其中$n \in \mathbb{Z}^+$，则

$t(R) = \bigcup_{i = 1}^n R^i = R \cup R^2 \cup \cdots \cup R^n$。

欲证明此等式，只需证明当$k > n$时，$R^k \subseteq \bigcup_{i=1}^n R^i$。

对任意$R^k$的元素$(x_1, x_{k + 1})$，存在$X$的元素序列$\{x_i\}_{i = 1}^{k + 1}$，使得$(\forall i \in \{1, 2, \dots, k\})[(x_i, x_{i + 1}) \in R]$。

由于集合$X$中只有$n$个相异元素，而序列含有$k + 1$个物件，又$k + 1 > n$。

根据鸽笼原理，存在索引$I, J$满足$1 \le I < J \le k + 1$，使得：

$x_I = x_J$。

因此可以从$\{x_i\}_{i = 1}^{k + 1}$去除从$x_{I + 1}$到$x_{J}$的部分，得到序列$\{y_i\}_{i = 1}^{k + 1 - (J - I)}$，依然满足$(y_i, y_{i + 1}) \in R$。

若新序列的长度仍然大于$n$，则必定可以重复上述步骤，以继续缩短序列。由于序列长度是有限的正整数，此过程会在关系步数$m$满足$1 \le m \le n$时停止。

由此可知，存在一个正整数$m \le n$，使得$(x_1, x_{k + 1}) \in R^m$。因此：

$$(x_1, x_{k + 1}) \in \bigcup_{i=1}^n R^i$$

由此证得，对所有$k > n$，皆有$R^k \subseteq \bigcup_{i=1}^n R^i$。故当$|X| = n$时，传递闭包只需联集至第$n$项。

以$X = \{1, 2, 3\}$、$R = \{(1, 1), (1, 2), (2, 3)\}$为例，$R^2 = \{(1, 1), (1, 2), (1, 3)\} = R^3 = R^4 = \cdots$。

$t(R) = R \cup R^2 \cup R^3 = R \cup R^2 = \{(1, 1), (1, 2), (1, 3), (2, 3)\}$。

### 现实用途

在图论中，求传递闭包是一个重要的问题，例如：给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有道路相连通。直接利用关系矩阵相乘来求传递闭包是一种方法，然而此法复杂度较高。若在计算矩阵相乘时，使用分治法可以降低时间复杂度。不过，利用基于动态规划的Floyd-Warshall算法会更加具有效率。