二元关系

任何一組有序對; (在甲組上)甲的有序元素對的集合,即甲×甲的子集; (在兩組甲和乙之間)有序對的集合,其中甲中的第一個元素和乙中的第二個元素
(重定向自关系图

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

定义

 为集合, 的任何子集称作  的二元关系,特别是当 时,称作 上的二元关系,一般记作 。若 ,  是从  的二元关系;若 ,那么  上的二元关系

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

 

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

  = {(), (), ()}

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

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

 

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

集合的關係

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

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

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

特殊的二元关系

 是一个集合,则

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

关系矩阵

     上的关系,令

 

0,1矩阵

 

称为 关系矩阵,记作 

关系图

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

运算

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

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

性质

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

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

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

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

闭包

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

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

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

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

  1.  
  2.  
  3.  

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

 

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

参见