二元关系

二元關係（英語：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}1,&(x_{i},y_{j})\in R\\0,&(x_{i},y_{j})\notin R\end{cases}},$$ 其中$i,j\in \mathbb {Z} ^{+}$，而$i\leq n$且$j\leq 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}Rx_{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)\neq 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)\neq 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\leq I<J\leq 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\leq m\leq n$時停止。

由此可知，存在一個正整數$m\leq 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算法會更加具有效率。

参见

• 有序对
• 二元集合
• 笛卡儿积
• 偏序关系
• 等价关系
• 相容关系