二元关系

数学上，二元关系用于讨论两个数学对象的联系。诸如算术中的「大于」及「等于」，几何学中的"相似"，或集合论中的"为...之元素"或"为...之子集"。二元关系有时会简称关系，但一般而言关系不必是二元的。

二元关系定义

集合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的子集）。

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

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

二元关系性质

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

自反性：

在集合X上的关系R，如对任意

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

在集合X上的关系R，如对任意

对称性：

在集合X上的关系R，如果有

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

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

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

传递性：

实例

例1：

设A={1,2,3},R₁,R₂和R₃是A上的关系，其中：R₁={<1,1>,<2,2>}；R₂={<1,1>,<2,2>,<3,3>,<1,2>}；R₃={<1,3>}，则R₁不是自反的，R₃是反自反的，R₂是自反的但不是反自反的。

例2：

设A={1,2,3},R₁,R₂,R₃和R₄是A上的关系，其中：R₁={<1,1>,<2,2>}；R₂={<1,1>,<1,2>,<2,1>}；R₃={<1,2>,<1,3>}；R₄={<1,2>,<2,1>,<1,3>}，则R₁既是对称的也是反对称的。R₂是对称的但不是反对称的。R₃是反对称的但不是对称的。R₄既不是对称的也不是反对称的。

例3：

设A={1,2,3}，R₁,R₂和R₃是A上的关系，其中：R₁={<1,1>,<2,2>}；R₂={<1,2>,<2,3>}；R₃={<1,3>}，则R₁和R₃是A上的传递关系，R₂不是A上的传递关系。

二元关系关系矩阵

设

二元关系关系图

设R集合A到B上的二元关系，令图G=(V,E)，其中顶点集合

二元关系关系的运算

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

设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，使得

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

二元关系二元关系的数目

在一个有n个元素的集合（简称n元素集）上，一共有

注：

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