二元关系

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

定义

實際上是以列舉二元有序对的方式去定義二元關係 ${\displaystyle R}$  ，也就是一個集合滿足

• 對所有的 ${\displaystyle r\in R}$  存在 ${\displaystyle x}$  且存在 ${\displaystyle y}$  使 ${\displaystyle r=(x,\,y)}$ 

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

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

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

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

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

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

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

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

集合的關係

集合${\displaystyle X}$ 与集合${\displaystyle Y}$ 上的二元关系則定義為 ${\displaystyle R=(X,Y,G(R))}$  ，当中 ${\displaystyle G(R)\subseteq X\times Y}$  ( 請參見笛卡儿积 ) ，称为 ${\displaystyle R}$  的图。若 ${\displaystyle (x,y)\in G(R)}$  则称 ${\displaystyle x}$  与 ${\displaystyle y}$  有关系 ${\displaystyle R}$  ，并记作 ${\displaystyle xRy}$  或 ${\displaystyle R(x,y)}$  。

但经常地我们把关系与其图等价起来，即若 ${\displaystyle R\subseteq X\times Y}$  则 ${\displaystyle R}$  是一个关系。

话虽如此，我们很多時候索性把集合間的關係 ${\displaystyle R}$  定义为 ${\displaystyle G(R)}$  而 “有序对 ${\displaystyle (x,y)\in G(R)}$  ” 即是 “ ${\displaystyle (x,y)\in R}$  ”。

特殊的二元关系

设${\displaystyle A}$ 是一个集合，则

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

关系矩阵

设${\displaystyle X=\{x_{1},x_{2},\ldots ,x_{n}\}}$ 及${\displaystyle Y=\{y_{1},y_{2},\ldots ,y_{m}\}}$ ，${\displaystyle R}$ 是${\displaystyle X}$  和${\displaystyle Y}$ 上的关系，令

${\displaystyle r_{ij}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\notin R\end{cases}}}$ 

则0,1矩阵

${\displaystyle (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}}}$ 

称为${\displaystyle R}$ 的关系矩阵，记作${\displaystyle M_{R}}$ 。

关系图

设${\displaystyle A=\{x_{1},x_{2},\ldots ,x_{n}\}}$ ，${\displaystyle R}$ 是${\displaystyle A}$ 上的关系，令图${\displaystyle G=(V,E)}$ ，其中顶点集合${\displaystyle V=A}$ ，边集合为${\displaystyle E}$ ，且对于任意的${\displaystyle x_{i},x_{j}\in V}$ ，满足${\displaystyle (x_{i},x_{j})\in E}$ 当且仅当${\displaystyle (x_{i},x_{j})\in R}$ 。则称图${\displaystyle G}$ 是关系${\displaystyle R}$ 的关系图，记作${\displaystyle G_{R}}$ 。

运算

关系的基本运算有以下几种：

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

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

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

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

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

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

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

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

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

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

• 设${\displaystyle R}$ 为二元关系，${\displaystyle A}$ 是一个集合。${\displaystyle R}$ 在${\displaystyle A}$ 上的限制记作${\displaystyle R\upharpoonright A}$ ，其中

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

• 设${\displaystyle R}$ 为二元关系，${\displaystyle A}$ 是一个集合。${\displaystyle A}$ 在${\displaystyle R}$ 下的像记作${\displaystyle R[A]}$ ，其中

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

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

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

性质

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

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

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

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

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

• 对称性：${\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\in R}$ 

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

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

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

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

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

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

闭包

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

1. ${\displaystyle R'}$ 是自反的（对称的或传递的）
2. ${\displaystyle R\subseteq R'}$ 
3. 对${\displaystyle A}$ 上任何包含${\displaystyle R}$ 的自反（对称或传递）关系${\displaystyle R''}$ 有${\displaystyle R'\subseteq R''}$ 

一般将${\displaystyle R}$ 的自反闭包记作${\displaystyle r(R)}$ ，对称闭包记作${\displaystyle s(R)}$ ，传递闭包记作${\displaystyle t(R)}$ 。

下列三个定理给出了构造闭包的方法：

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

对于有限集合${\displaystyle A}$ 上的关系${\displaystyle R}$ ，存在一个正整数${\displaystyle r}$ ，使得

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

求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度；但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。

参见

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