二元关系

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

定义[编辑]

实际上是以列举二元有序对的方式去定义二元关系 $R$ ，也就是一个集合满足

对所有的 $r\in R$ 存在 $x$ 且存在 $y$ 使 $r=(x,\,y)$

(\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$ 是一个集合，则

空集 $\varnothing$ 称作 $A$ 上的空关系
$E_{A}=A\times A$ 称作 $A$ 上的全域关系（完全关系）
$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$ 的五种性质成立的充要条件：

$R$ 在 $A$ 上自反，当且仅当 $I_{A}\subseteq R$
$R$ 在 $A$ 上非自反，当且仅当 $R\cap I_{A}=\emptyset$
$R$ 在 $A$ 上对称，当且仅当 $R=R^{-1}\$
$R$ 在 $A$ 上反对称，当且仅当 $R\cap R^{-1}\subseteq I_{A}$
$R$ 在 $A$ 上非对称，当且仅当 $R\cap R^{-1}=\emptyset$
$R$ 在 $A$ 上传递，当且仅当 $R\circ R\subseteq R$

闭包[编辑]

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

$R'$ 是自反的（对称的或传递的）
$R\subseteq R'$
对 $A$ 上任何包含 $R$ 的自反（对称或传递）关系 $R''$ 有 $R'\subseteq R''$

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

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

$r(R)=R\cup R^{0}$
$s(R)=R\cup R^{-1}$
$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算法来求传递闭包。

参见[编辑]