[科普中国]-二元关系- · 科普中国网

定义

集合X与集合Y上的二元关系是R=(X,Y,G(R))，其中G(R)，称为R的图，是笛卡儿积X×Y的子集。若 (x,y) ∈G(R) ，则称x是R-关系于y，并记作xRy或R(x,y)。否则称x与y无关系R。但经常地我们把关系与其图等同起来，即：若R⊆X×Y，则R是一个关系。

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

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

不同的关系可以有相同的图。以下的关系 ({球，糖，车，枪}, {甲，乙，丁}, {(球,甲), (糖,乙), (车,丁)} 中人人皆是物主，所以与R不同，但两者有相同的图。话虽如此，我们很多时候索性把R定义为G(R)，而 "有序对 (x,y) ∈G(R)" 亦即是 "(x,y) ∈R"。

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

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

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

设A是一个集合，则：

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

EA = A × A称作A上的全域关系。

IA = {(x,，x)： x∈A} 称作A上的恒等关系****。1

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

自反性：。

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

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

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

对称性：。

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

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

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

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

传递性：。

实例

例1：

设A={1,2,3},R1,R2和R3是A上的关系，其中：R1={,}；R2={,,,}；R3={}，则R1不是自反的，R3是反自反的，R2是自反的但不是反自反的。

例2：

设A={1,2,3},R1,R2,R3和R4是A上的关系，其中：R1={,}；R2={,,}；R3={,}；R4={,,}，则R1既是对称的也是反对称的。R2是对称的但不是反对称的。R3是反对称的但不是对称的。R4既不是对称的也不是反对称的。

例3：

设A={1,2,3}，R1,R2和R3是A上的关系，其中：R1={,}；R2={,}；R3={}，则R1和R3是A上的传递关系，R2不是A上的传递关系。2

关系矩阵设及，R是X与Y上的二元关系，令，则0,1矩阵称为R的关系矩阵，记作MR。3

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

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

设R为二元关系。

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

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

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

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

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

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

与关系性质的联系

设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''有。6

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

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

；

。

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

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

二元关系的数目在一个有n个元素的集合（简称n元素集）上，一共有个可能的二元关系。

|| ||

注：

反自反关系和自反关系的数目一样多。

严格偏序（反自反的传递关系）的数目和偏序的一样多。

全序即是那些同时是全预序的偏序。透过容斥原理的想法，可知那些既不是偏序也不是全预序的预序数目是：预序的数目，减去偏序的数目，再减去全预序的数目，最後加上全序的数目，即0, 0, 0, 3, 85, ...

等价关系的数目是集合划分的数目，即贝尔数。

各个二元关系之间可组成二元组（某关系及其补集），除了在n=0时，空关系的补集即其自身。那些不符合对称性的二元关系也可组成四元组（某关系、补集、逆、逆的补集）。