二元關係

二元關係（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算法會更加具有效率。