二元關係（），有時簡稱關係，代指數學上兩種物件之間的聯繫。舉凡算術中的“大於”、“小於”以及“等於”，幾何學上的“相似”和“全等”，抑或是集合論中的“屬於”和“包含於”等，都是所屬領域的二元關係。
定義
集合論方法
給定集合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。
這種看似繁複的定義，其必要性體現在範疇論對態射的基本要求：任意態射必須具備唯一且確定的源物件與靶物件。此定義也因而成為合法建構關係範疇最精簡的方法。
實務上，這裡常涉及數學上常見的“符號的濫用”（）──即關係本身與其「圖」被視為同一物，因而出現將三元組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}
1, & (x_i, y_j) \in R \\
0, & (x_i, y_j) \notin R
\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}等價。
- 不對稱性（）：(\exists x \in X)(\exists y \in X)[xRy \land \neg(yRx)]。
- 非對稱性（）：(\forall x \in X)(\forall y \in X)[xRy \implies \neg(yRx)]。
:此性質與R \cap R^{-1} = \varnothing等價。
- 反對稱性（）：(\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。
:以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}。
{{Math proof|
- 包含性：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。
{{Math proof|
- 包含性：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。
{{Math proof
|drop=no
|1=
欲證明此等式，只需證明當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 ，使得：
: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算法會更加具有效率。
参见
- 有序对
- 二元集合
- 笛卡儿积
- 偏序关系
- 等价关系
- 相容关系
參考資料
评论 (0)