二元关系

数学上，二元关系（Template:Lang-en，或简称关系）用於讨论两种物件的连系。诸如算术中的「大於」及「等於」、几何学中的「相似」或集合论中的「为……之元素」、「为……之子集」。

定义

设$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$上的二元关系

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

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

例一：有四件物件 {球，糖，车，枪} 及四个人 {甲，乙，丙，丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有车，则「擁有」的二元关系可以寫為

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

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

例二：實數系 $ℝ$ 上的「大於關係」可定義為

$>:=\{(a,b)\in {ℝ}^2|(\mathrm{\exists }r\in ℝ)[(a=b+r)\wedge (r\ne 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,\dots ,x_n\}$及$Y=\{y_1,y_2,\dots ,y_m\}$，$R$是$X$ 和$Y$上的关系，令

$r_{ij}=\{\begin{array}{cc}1& (x_i,y_j)\in R\\ 0& (x_i,y_j)\notin R\end{array}$

则0,1矩阵

$(r_{ij})=\left[\begin{array}{cccc}{r}_{11}& r_{12}& \cdots & r_{1m}\\ r_{21}& r_{22}& \cdots & r_{2m}\\ ⋮& ⋮& ⋮& ⋮\\ r_{n1}& r_{n2}& \cdots & r_{nm}\end{array}\right]$

称为$R$的关系矩阵，记作$M_R$。

关系图

设$A=\{x_1,x_2,\dots ,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$的定义域，记作$\text{dom}(R)$。形式化表示为

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

• 设$R$为二元关系，$R$中所有有序对的第二元素构成的集合称为$R$的值域，记作$\text{ran}(R)$。形式化表示为

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

• 设$R$为二元关系，$R$的定义域和值域的并集称作$R$的域，记作$\text{fld}(R)$，形式化表示为

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

• 设$R$为二元关系，$R$的逆关系，简称$R$的逆，记作$R^{-1}$，其中

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

• 设$F,G$为二元关系，$G$與$F$的合成關係记作$F\circ G$，其中

$F\circ G=\{(x,y)|\mathrm{\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]=\text{ran}(R\upharpoonright A)$

• 设$R$为$A$上的二元关系，在右复合的基础上可以定义关系的幂运算：

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

性质

关系的性质主要有以下五种：

• 自反性：$\mathrm{\forall }x\in A,(x,x)\in R$

在集合X上的关系R，如对任意$x\in X$，有$(x,x)\in R$，则称R是自反的。

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

在集合X上的关系R，如对任意$x\in X$，有$(x,x)\notin R$，则称R是非自反的。

• 对称性：$\mathrm{\forall }x,y\in A,(x,y)\in R⟹(y,x)\in R$

在集合X上的关系R，如果有$(x,y)\in R$且$x\ne y$必有$(y,x)\in R$，则称R是对称的。

• 反对称性（不是對稱性的否定）：$\mathrm{\forall }x,y\in A,((x,y)\in R\wedge (y,x)\in R)⟹x=y$
• 非對稱性（對稱性的否定的強型式）：$\mathrm{\forall }x,y\in A,(x,y)\in R⟹(y,x)\notin R$

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

• 传递性：$\mathrm{\forall }x,y,z\in A,((x,y)\in R\wedge (y,z)\in R)⟹(x,z)\in R$

设$R$为集合$A$上的关系，下面给出$R$的五种性质成立的充要条件：

1. $R$在$A$上自反，当且仅当$I_A\subseteq R$
2. $R$在$A$上非自反，当且仅当$R\cap I_A=\mathrm{\varnothing }$
3. $R$在$A$上对称，当且仅当$R=R^{-1}$
4. $R$在$A$上反对称，当且仅当$R\cap R^{-1}\subseteq I_A$
5. $R$在$A$上非對稱，当且仅当$R\cap R^{-1}=\mathrm{\varnothing }$
6. $R$在$A$上传递，当且仅当$R\circ R\subseteq R$

闭包

设$R$是非空集合$A$上的关系，$R$的自反（对称或传递）闭包是$A$上的关系$R^{\prime }$，满足

1. $R^{\prime }$是自反的（对称的或传递的）
2. $R\subseteq R^{\prime }$
3. 对$A$上任何包含$R$的自反（对称或传递）关系$R^{″}$有$R^{\prime }\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算法来求传递闭包。

参见

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