二元关系

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

数学上,二元关系(英语: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算法来求传递闭包。

参见