二元關係

數學上，二元關係（英語：Binary relation，或簡稱關係）用於討論兩種物件的連繫。諸如算術中的「大於」及「等於」、幾何學中的「相似」或集合論中的「為……之元素」、「為……之子集」。

定義

設$A,B$為集合，$A\times B$的任何子集稱作$A$到$B$的二元關係，特別是當$A=B$時，稱作$A$上的二元關係,一般記作$R$。若$R\subseteq A\times B$, $R$是從$A$到$B$的二元關係；若$R\subseteq A\times A$,那麼$R$是$A$上的二元關係

或是以正式的邏輯符號表述為

$(\forall r\in R)(\exists x)(\exists y)[\,r=(x,\,y)\,]$

例一：有四件物件 {球，糖，車，槍} 及四個人 {甲，乙，丙，丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有車，則「擁有」的二元關係可以寫為

$R$ = {(球，甲), (糖，乙), (車，丁)}

其中二元有序對的第一項是被擁有的物件，第二項是擁有者。

例二：實數系 $\mathbb {R}$ 上的「大於關係」可定義為

$>\,:=\{\,(a,\,b)\in {\mathbb {R} }^{2}\,|\,(\exists r\in \mathbb {R} )[\,(a=b+r)\wedge (r\neq 0)\,]\}$

由於習慣上 $(a,\,b)\in \,>$ 通常都是寫為 $a>b$ ，更一般來說，不引起混淆的話會把 $(x,\,y)\in R$ 簡寫成 $xRy$ 。

集合的關係

集合$X$與集合$Y$上的二元關係則定義為 $R=(X,Y,G(R))$ ，當中 $G(R)\subseteq X\times Y$ ( 請參見笛卡兒積 ) ，稱為 $R$ 的圖。若 $(x,y)\in G(R)$ 則稱 $x$ 與 $y$ 有關係 $R$ ，並記作 $xRy$ 或 $R(x,y)$ 。

但經常地我們把關係與其圖等價起來，即若 $R\subseteq X\times Y$ 則 $R$ 是一個關係。

話雖如此，我們很多時候索性把集合間的關係 $R$ 定義為 $G(R)$ 而 「有序對 $(x,y)\in G(R)$ 」 即是 「 $(x,y)\in R$ 」。

特殊的二元關係

設$A$是一個集合，則

1. 空集$\varnothing$稱作$A$上的空關係
2. $E_{A}=A\times A$稱作$A$上的全域關係（完全關係）
3. $I_{A}=\{(x,x)|x\in A\}$稱作$A$上的恆等關係

關係矩陣

設$X=\{x_{1},x_{2},\ldots ,x_{n}\}$及$Y=\{y_{1},y_{2},\ldots ,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}}$

則0,1矩陣

$(r_{ij})={\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}}$

稱為$R$的關係矩陣，記作$M_{R}$。

關係圖

設$A=\{x_{1},x_{2},\ldots ,x_{n}\}$，$R$是$A$上的關係，令圖$G=(V,E)$，其中頂點集合$V=A$，邊集合為$E$，且對於任意的$x_{i},x_{j}\in V$，滿足$(x_{i},x_{j})\in E$若且唯若$(x_{i},x_{j})\in R$。則稱圖$G$是關係$R$的關係圖，記作$G_{R}$。

運算

關係的基本運算有以下幾種：

• 設$R$為二元關係，$R$中所有有序對的第一元素構成的集合稱為$R$的定義域，記作${\mbox{dom}}(R)$。形式化表示為

${\mbox{dom}}(R)=\{\,x\,|\,(\exists y)[\,(x,y)\in R\,]\,\}$

• 設$R$為二元關係，$R$中所有有序對的第二元素構成的集合稱為$R$的值域，記作${\mbox{ran}}(R)$。形式化表示為

${\mbox{ran}}(R)=\{\,y\,|\,(\exists x)[\,(x,y)\in R\,]\,\}$

• 設$R$為二元關係，$R$的定義域和值域的併集稱作$R$的域，記作${\mbox{fld}}(R)$，形式化表示為

${\mbox{fld}}(R)={\mbox{dom}}(R)\cup {\mbox{ran}}(R)$

• 設$R$為二元關係，$R$的逆關係，簡稱$R$的逆，記作$R^{-1}$，其中

$R^{-1}=\{\,p\,|\,(\exists x)(\exists y)[\,(x,y)\in R\wedge p=(y,x)\,]\,\}$

• 設$F,G$為二元關係，$G$與$F$的合成關係記作$F\circ G$，其中

$F\circ G=\{(x,y)|\exists t,~(x,t)\in F\wedge (t,y)\in G\}$

• 設$R$為二元關係，$A$是一個集合。$R$在$A$上的限制記作$R\upharpoonright A$，其中

$R\upharpoonright A=\{(x,y)|(x,y)\in R\wedge x\in A\}$

• 設$R$為二元關係，$A$是一個集合。$A$在$R$下的像記作$R[A]$，其中

$R[A]={\mbox{ran}}(R\upharpoonright A)$

• 設$R$為$A$上的二元關係，在右複合的基礎上可以定義關係的冪運算：

$R^{0}=I_{A}\$
$R^{n+1}=R^{n}\circ R\$

性質

關係的性質主要有以下五種：

• 自反性：$\forall x\in A,~(x,x)\in R$

在集合X上的關係R，如對任意$x\in X$，有$(x,x)\in R$，則稱R是自反的。

• 非自反性（自反性的否定的強型式）：$\forall x\in A,~~(x,x)\notin R$

在集合X上的關係R，如對任意$x\in X$，有$(x,x)\notin R$，則稱R是非自反的。

• 對稱性：$\forall x,y\in A,~(x,y)\in R\implies (y,x)\in R$

在集合X上的關係R，如果有$(x,y)\in R$且$x\neq y$必有$(y,x)\in R$，則稱R是對稱的。

• 反對稱性（不是對稱性的否定）：$\forall x,y\in A,~((x,y)\in R\wedge (y,x)\in R)\implies x=y$
• 非對稱性（對稱性的否定的強型式）：$\forall x,y\in A,~(x,y)\in R\implies (y,x)\notin R$

非對稱性是 滿足非自反性的反對稱性。

• 傳遞性：$\forall x,y,z\in A,~((x,y)\in R\wedge (y,z)\in R)\implies (x,z)\in R$

設$R$為集合$A$上的關係，下面給出$R$的五種性質成立的充要條件：

1. $R$在$A$上自反，若且唯若$I_{A}\subseteq R$
2. $R$在$A$上非自反，若且唯若$R\cap I_{A}=\emptyset$
3. $R$在$A$上對稱，若且唯若$R=R^{-1}\$
4. $R$在$A$上反對稱，若且唯若$R\cap R^{-1}\subseteq I_{A}$
5. $R$在$A$上非對稱，若且唯若$R\cap R^{-1}=\emptyset$
6. $R$在$A$上傳遞，若且唯若$R\circ R\subseteq R$

閉包

設$R$是非空集合$A$上的關係，$R$的自反（對稱或傳遞）閉包是$A$上的關係$R'$，滿足

1. $R'$是自反的（對稱的或傳遞的）
2. $R\subseteq R'$
3. 對$A$上任何包含$R$的自反（對稱或傳遞）關係$R''$有$R'\subseteq R''$

一般將$R$的自反閉包記作$r(R)$，對稱閉包記作$s(R)$，傳遞閉包記作$t(R)$。

下列三個定理給出了構造閉包的方法：

1. $r(R)=R\cup R^{0}$
2. $s(R)=R\cup R^{-1}$
3. $t(R)=R\cup R^{2}\cup R^{3}\cup \cdots$

對於有限集合$A$上的關係$R$，存在一個正整數$r$，使得

$t(R)=R\cup R^{2}\cup \cdots \cup R^{r}$

求傳遞閉包是圖論中一個非常重要的問題，例如給定了一個城市的交通地圖，可利用求傳遞閉包的方法獲知任意兩個地點之間是否有路相連通。可以直接利用關係矩陣相乘來求傳遞閉包，但那樣做複雜度比較高；好一點的辦法是在計算矩陣相乘的時候用分治法降低時間複雜度；但最好的方法是利用基於動態規劃的Floyd-Warshall算法來求傳遞閉包。

參見

• 有序對
• 二元集合
• 笛卡兒積
• 偏序關係
• 等價關係
• 相容關係