二元关系

维基百科,自由的百科全书

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

定义

實際上是以列舉二元有序对的方式去定義二元關係 ,也就是一個集合滿足

  • 對所有的 存在 且存在 使

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

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

= {(), (), ()}

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

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

由於習慣上 通常都是寫為 ,更一般來說,不引起混淆的話會把 簡寫成

集合的關係

集合与集合上的二元关系則定義為 ,当中 ( 請參見笛卡儿积 ) ,称为 。若 则称 有关系 ,并记作

但经常地我们把关系与其图等价起来,即若 是一个关系。

话虽如此,我们很多時候索性把集合間的關係 定义为 而 “有序对 ” 即是 “ ”。

特殊的二元关系

是一个集合,则

  1. 空集称作上的空关系
  2. 称作上的全域关系完全關係
  3. 称作上的恒等关系

关系矩阵

上的关系,令

0,1矩阵

称为关系矩阵,记作

关系图

上的关系,令,其中顶点集合,边集合为,且对于任意的,满足当且仅当。则称图是关系关系图,记作

运算

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

  • 为二元关系,中所有有序对的第一元素构成的集合称为定义域,记作。形式化表示为
  • 为二元关系,中所有有序对的第二元素构成的集合称为值域,记作。形式化表示为
  • 为二元关系,定义域值域的并集称作,记作,形式化表示为
  • 为二元关系,逆关系,简称,记作,其中
  • 为二元关系,合成關係记作,其中
  • 为二元关系,是一个集合。上的限制记作,其中
  • 为二元关系,是一个集合。下的记作,其中
  • 上的二元关系,在右复合的基础上可以定义关系的幂运算

性质

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

  • 自反性:
在集合X上的关系R,如对任意,有,则称R是自反的。
  • 非自反性(自反性的否定的強型式):
在集合X上的关系R,如对任意,有,则称R是非自反的。
  • 对称性:
在集合X上的关系R,如果有必有,则称R是对称的。
  • 反对称性(不是對稱性的否定):
  • 非對稱性(對稱性的否定的強型式):
非對稱性是 滿足非自反性的反對稱性。
  • 传递性:

为集合上的关系,下面给出的五种性质成立的充要条件:

  1. 上自反,当且仅当
  2. 上非自反,当且仅当
  3. 上对称,当且仅当
  4. 上反对称,当且仅当
  5. 上非對稱,当且仅当
  6. 上传递,当且仅当

闭包

是非空集合上的关系,的自反(对称或传递)闭包上的关系,满足

  1. 是自反的(对称的或传递的)
  2. 上任何包含的自反(对称或传递)关系

一般将的自反闭包记作,对称闭包记作传递闭包记作

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

对于有限集合上的关系,存在一个正整数,使得

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

参见