二元关系

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

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

参见

编辑