二元关系

集合与集合上的二元关系是，当中，称为的图，是笛卡儿积的子集。若则称与有关系，并记作或。

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

例子：有四件物件{球，糖，车，枪}及四个人{甲，乙，丙，丁}。若甲拥有球，乙拥有糖，及丁拥有车－即无人有枪及丙一无所有－则二元关系为“……拥有……”便是

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

其中的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人）组成的集合。比如有序对（球，甲）以_球甲表示，代表球为甲拥有。

不同的关系可以有相同的图。以下的关系

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

中人人皆是物主，所以与不同，但两者有相同的图。

话虽如此，我们很多时候索性把定义为而“有序对”亦即是“”。

二元关系可看作成二元函数，这种二元函数把输入元及视为独立变数并求真伪值（包括“有序对是或非二元关系中的一元”此一问题）。

若，则称为上的关系。

设是一个集合，则

1. 空集称作上的空关系

   称作上的全域关系（完全关系）

   称作上的恒等关系

设及，是 上的关系，令

则0,1矩阵

称为的关系矩阵，记作。

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

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

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

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

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

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

设为二元关系，与的合成关系记作，其中

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

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

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

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

自反性：

在集合X上的关系R，如对任意，有，则称R是自反的。

非自反性（自反性的否定的强型式）：

在集合X上的关系R，如对任意，有，则称R是非自反的。

对称性：

在集合X上的关系R，如果有且必有，则称R是对称的。

反对称性（不是对称性的否定）：

非对称性（对称性的否定的强型式）：

非对称性是 满足反自反性的反对称性。

传递性：

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

1. 在上自反，当且仅当

   在上非自反，当且仅当

   在上对称，当且仅当

   在上反对称，当且仅当

   在上非对称，当且仅当

   在上传递，当且仅当

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

1. 是自反的（对称的或传递的）

   

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

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

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

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

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