二元关系

集合${\displaystyle X}$与集合${\displaystyle Y}$上的二元关系是${\displaystyle R=(X,Y,G(R))}$，当中${\displaystyle G(R)}$，称为${\displaystyle R}$的图，是笛卡兒積${\displaystyle X\times Y}$的子集。若${\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 R}$的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人） 组成的集合。比如有序对（球，甲）以_球${\displaystyle R}$_甲表示， 代表球为甲拥有。

不同的关系可以有相同的图。以下的关系

({球，糖，车，枪}, {甲，乙，丁}, {(球，甲), (糖，乙), (车，丁)})

中人人皆是物主，所以与${\displaystyle R}$不同，但两者有相同的图。

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

二元关系可看作成二元函数，這種二元函数把输入元${\displaystyle x\in X}$及${\displaystyle y\in Y}$視為獨立變數並求真偽值（包括「有序对${\displaystyle (x,y)}$是或非二元关系中的一元」此一問題）。

若${\displaystyle X=Y}$，則稱${\displaystyle R}$為${\displaystyle X}$上的關係。

设${\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}=\{(x,y)|(y,x)\in R\}}$

• 设${\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算法来求传递闭包。

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