二元关系

实际上是以列举二元有序对的方式去定义二元关系 ${\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算法来求传递闭包。

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