二元关系：用于讨论两个数学对象的联系

更新时间：2023-11-17 16:55

数学上，二元关系（binary relation）用于讨论两个数学对象的联系。诸如算术中的「大于」及「等于」，几何学中的"相似"，或集合论中的"为·..之元素"或"为·..之子集"。二元关系有时会简称关系，但一般而言关系不必是二元的。其中 R 的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人）组成的集合。称为R的关系矩阵，记作M。严格偏序（反自反的传递关系）的数目和偏序的一样多。全序即是那些同时是全预序的偏序。那些不符合对称性的二元关系也可组成四元组（某关系、补集、逆、逆的补集）。

定义

集合 X 与集合 Y 上的二元关系是，其中，称为R 的图，是笛卡儿积的子集。若，则称x 是 R-关系于y ，并记作 xRy 或 R(x,y)。否则称a与b无关系R。

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

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

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

其中 R 的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人）组成的集合。比如有序对（球，甲），所以我们可写作"球R甲"，表示球为甲所拥有。

不同的关系可以有相同的图。以下的关系 ({球，糖，车，枪}, {甲，乙，丁}, {(球，甲), (糖，乙), (车，丁)} 中人人皆是物主，所以与 R 不同，但两者有相同的图。

话虽如此，我们很多时候索性把R 定义为 G(R)，而 "有序对" 亦即是 ""。

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

若，则称 R为 X 上的关系。

特殊的二元关系

注：下文我们将采用把二元关系R定义为子集的做法。

设A是一个集合，则

空集∅称作A上的空关系（因为∅也是的子集）。

称作A上的全域关系。

称作A上的恒等关系

性质

关系的性质主要有以下五种：自反性，反自反性，对称性，反对称性和传递性。

自反性：

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

反自反性（自反性的否定的强形式）：

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

对称性：

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

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

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

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

传递性：

实例

例1：

设,和是A上的关系，其中

则是自反的，是反自反的，既不是自反的也不是反自反的。

例2：

设,和是A上的关系，其中

则既是对称的也是反对称的。是对称的但不是反对称的。是反对称的但不是对称的。既不是对称的也不是反对称的。

例3：

设，和是A上的关系，其中

则和是A上的传递关系，是A上的传递关系。

关系矩阵

设及，R是X与Y上的二元关系，令

则0,1矩阵称为R的关系矩阵，记作。

关系图

设R集合A到B上的二元关系，令图，其中顶点集合，边集合为E ，且对于任意的，规定当且仅当。则称图G是关系R的关系图。

关系的运算

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

设R为二元关系。

R中所有有序对的第一元素构成的集合称为R的定义域，记作dom(R)，即。

R中所有有序对的第二元素构成的集合称为R的值域，记作ran(R) ，即。

R的定义域和值域的并集称作R的域，记作fld(R)，即

R的逆关系，简称R的逆，记作，其中

设S也是一个二元关系。R和S的合成记作，其定义为。

若R是一个集合A上的二元关系，可以在自然数范围内定义R的n次幂。首先规定，再递归定义。可以证明有成立。

与关系性质的连系

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

R在A上自反当且仅当

R在A上反自反当且仅当

R在A上对称当且仅当

R在A上反对称当且仅当

R在A上非对称当且仅当

R在A上传递当且仅当

关系的闭包

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

(1) R'是自反的（对称的或传递的）

(2)

(3) 对A上任何包含R的自反（对称或传递）关系R''有

一般将R的自反闭包记作r(R)，对称闭包记作s(R) ，传递闭包记作t(R)。

下列给出了构造闭包的方法：

对于有限集合A 上的关系R ，存在一个正整数s，使得，且s不超过A的元素数。

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