二元关系

数学上，二元关系（，或简称关系）用於讨论两种物件的连系。诸如算术中的「大於」及「等於」、几何学中的「相似」或集合论中的「为……之元素」、「为……之子集」。

定义 

實際上是以列舉二元有序对的方式去定義二元關係  ，也就是一個集合滿足
 對所有的  存在  且存在  使 
或是以正式的邏輯符號表述為

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

 = {(球，甲), (糖，乙), (车，丁)}

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

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

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

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

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

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

特殊的二元关系 

设是一个集合，则

 空集称作上的空关系
 称作上的全域关系（完全關係）
 称作上的恒等关系

关系矩阵 

设及，是 和上的关系，令

则0,1矩阵

称为的关系矩阵，记作。

关系图 

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

运算 

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

 设为二元关系，中所有有序对的第一元素构成的集合称为的定义域，记作。形式化表示为

 设为二元关系，中所有有序对的第二元素构成的集合称为的值域，记作。形式化表示为

 设为二元关系，的定义域和值域的并集称作的域，记作，形式化表示为

 设为二元关系，的逆关系，简称的逆，记作，其中

 设为二元关系，與的合成關係记作，其中

 设为二元关系，是一个集合。在上的限制记作，其中

 设为二元关系，是一个集合。在下的像记作，其中

 设为上的二元关系，在右复合的基础上可以定义关系的幂运算：

性质 

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

 自反性：
在集合X上的关系R，如对任意，有，则称R是自反的。
 非自反性（自反性的否定的強型式）：
在集合X上的关系R，如对任意，有，则称R是非自反的。
 对称性：
在集合X上的关系R，如果有且必有，则称R是对称的。
 反对称性（不是對稱性的否定）：
 非對稱性（對稱性的否定的強型式）：
非對稱性是 滿足非自反性的反對稱性。
 传递性：

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

 在上自反，当且仅当
 在上非自反，当且仅当
 在上对称，当且仅当
 在上反对称，当且仅当
 在上非對稱，当且仅当
 在上传递，当且仅当

闭包 

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

 是自反的（对称的或传递的）
 
 对上任何包含的自反（对称或传递）关系有

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

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

 
 
 

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

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

参见 

 有序对
 二元集合
 笛卡儿积
 偏序关系
 等价关系
 相容关系

数学关系