Brstjjy

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

定义

集合X{displaystyle X}与集合Y{displaystyle Y}上的二元关系是R=(X,Y,G(R)){displaystyle R=(X,Y,G(R))}，当中G(R){displaystyle G(R)}，称为R{displaystyle R}的图，是笛卡兒積X×Y{displaystyle Xtimes Y}的子集。若(x,y)∈G(R){displaystyle (x,y)in G(R)}则称x{displaystyle x}与y{displaystyle y}有关系R{displaystyle R}，并记作xRy{displaystyle xRy}或R(x,y){displaystyle R(x,y)}。

但经常地我们把关系与其图等价起来，即若R⊆X×Y{displaystyle Rsubseteq Xtimes Y}则R{displaystyle R}是一个关系。

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

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

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

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

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

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

话虽如此，我们很多時候索性把R{displaystyle R}定义为G(R){displaystyle G(R)}而“有序对(x,y)∈G(R){displaystyle (x,y)in G(R)}”亦即是“(x,y)∈R{displaystyle (x,y)in R}”。

二元关系可看作成二元函数，這種二元函数把输入元x∈X{displaystyle xin X}及y∈Y{displaystyle yin Y}視為獨立變數並求真偽值（包括「有序对(x,y){displaystyle (x,y)}是或非二元关系中的一元」此一問題）。

若X=Y{displaystyle X=Y}，則稱R{displaystyle R}為X{displaystyle X}上的關係。

特殊的二元关系

设A{displaystyle A}是一个集合，则

1. 空集∅{displaystyle varnothing }称作A{displaystyle A}上的空关系
   


2. 
   EA=A×A{displaystyle E_{A}=Atimes A}称作A{displaystyle A}上的全域关系（完全關係）


3. 
   IA={(x,x)|x∈A}{displaystyle I_{A}={(x,x)|xin A}}称作A{displaystyle A}上的恒等关系
   

关系矩阵

设X={x1,x2,…,xn}{displaystyle X={x_{1},x_{2},ldots ,x_{n}}}及Y={y1,y2,…,ym}{displaystyle Y={y_{1},y_{2},ldots ,y_{m}}}，R{displaystyle R}是X{displaystyle X} Y{displaystyle Y}上的关系，令

rij={1(xi,yj)∈R0(xi,yj)∉R{displaystyle r_{ij}={begin{cases}1&(x_{i},y_{j})in R\0&(x_{i},y_{j})notin Rend{cases}}}

则0,1矩阵

(rij)=[r11r12⋯r1mr21r22⋯r2m⋮⋮⋮⋮rn1rn2⋯rnm]{displaystyle (r_{ij})={begin{bmatrix}r_{11}&r_{12}&cdots &r_{1m}\r_{21}&r_{22}&cdots &r_{2m}\vdots &vdots &vdots &vdots \r_{n1}&r_{n2}&cdots &r_{nm}end{bmatrix}}}

称为R{displaystyle R}的关系矩阵，记作MR{displaystyle M_{R}}。

关系图

设A={x1,x2,…,xn}{displaystyle A={x_{1},x_{2},ldots ,x_{n}}}，R{displaystyle R}是A{displaystyle A}上的关系，令图G=(V,E){displaystyle G=(V,E)}，其中顶点集合V=A{displaystyle V=A}，边集合为E{displaystyle E}，且对于任意的xi,xj∈V{displaystyle x_{i},x_{j}in V}，满足(xi,xj)∈E{displaystyle (x_{i},x_{j})in E}当且仅当(xi,xj)∈R{displaystyle (x_{i},x_{j})in R}。则称图G{displaystyle G}是关系R{displaystyle R}的关系图，记作GR{displaystyle G_{R}}。

运算

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

• 设R{displaystyle R}为二元关系，R{displaystyle R}中所有有序对的第一元素构成的集合称为R{displaystyle R}的定义域，记作dom(R){displaystyle {mbox{dom}}(R)}。形式化表示为

dom(R)={x|∃y, (x,y)∈R}{displaystyle {mbox{dom}}(R)={x|exists y,~(x,y)in R}}

• 设R{displaystyle R}为二元关系，R{displaystyle R}中所有有序对的第二元素构成的集合称为R{displaystyle R}的值域，记作ran(R){displaystyle {mbox{ran}}(R)}。形式化表示为

ran(R)={y|∃x, (x,y)∈R}{displaystyle {mbox{ran}}(R)={y|exists x,~(x,y)in R}}

• 设R{displaystyle R}为二元关系，R{displaystyle R}的定义域和值域的并集称作R{displaystyle R}的域，记作fld(R){displaystyle {mbox{fld}}(R)}，形式化表示为

fld(R)=dom(R)∪ran(R){displaystyle {mbox{fld}}(R)={mbox{dom}}(R)cup {mbox{ran}}(R)}

• 设R{displaystyle R}为二元关系，R{displaystyle R}的逆关系，简称R{displaystyle R}的逆，记作R−1{displaystyle R^{-1}}，其中

R−1={(x,y)|(y,x)∈R}{displaystyle R^{-1}={(x,y)|(y,x)in R}}

• 设F,G{displaystyle F,G}为二元关系，G{displaystyle G}與F{displaystyle F}的合成關係记作F∘G{displaystyle Fcirc G}，其中

F∘G={(x,y)|∃t, (x,t)∈F∧(t,y)∈G}{displaystyle Fcirc G={(x,y)|exists t,~(x,t)in Fwedge (t,y)in G}}

• 设R{displaystyle R}为二元关系，A{displaystyle A}是一个集合。R{displaystyle R}在A{displaystyle A}上的限制记作R↾A{displaystyle Rupharpoonright A}，其中

R↾A={(x,y)|(x,y)∈R∧x∈A}{displaystyle Rupharpoonright A={(x,y)|(x,y)in Rwedge xin A}}

• 设R{displaystyle R}为二元关系，A{displaystyle A}是一个集合。A{displaystyle A}在R{displaystyle R}下的像记作R[A]{displaystyle R[A]}，其中

R[A]=ran(R↾A){displaystyle R[A]={mbox{ran}}(Rupharpoonright A)}

• 设R{displaystyle R}为A{displaystyle A}上的二元关系，在右复合的基础上可以定义关系的幂运算：

R0=IA {displaystyle R^{0}=I_{A} }
Rn+1=Rn∘R {displaystyle R^{n+1}=R^{n}circ R }

性质

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

• 自反性：∀x∈A, (x,x)∈R{displaystyle forall xin A,~(x,x)in R}
  

在集合X上的关系R，如对任意x∈X{displaystyle xin X}，有(x,x)∈R{displaystyle (x,x)in R}，则称R是自反的。

• 非自反性（自反性的否定的強型式）：∀x∈A,  (x,x)∉R{displaystyle forall xin A,~~(x,x)notin R}
  

在集合X上的关系R，如对任意x∈X{displaystyle xin X}，有(x,x)∉R{displaystyle (x,x)notin R}，则称R是非自反的。

• 对称性：∀x,y∈A, (x,y)∈R⟹(y,x)∈R{displaystyle forall x,yin A,~(x,y)in Rimplies (y,x)in R}
  

在集合X上的关系R，如果有(x,y)∈R{displaystyle (x,y)in R}且x≠y{displaystyle xneq y}必有(y,x)∈R{displaystyle (y,x)in R}，则称R是对称的。

• 反对称性（不是對稱性的否定）：∀x,y∈A, ((x,y)∈R∧(y,x)∈R)⟹x=y{displaystyle forall x,yin A,~((x,y)in Rwedge (y,x)in R)implies x=y}
  


• 非對稱性（對稱性的否定的強型式）：∀x,y∈A, (x,y)∈R⟹(y,x)∉R{displaystyle forall x,yin A,~(x,y)in Rimplies (y,x)notin R}
  

非對稱性是 滿足反自反性的反對稱性。

• 传递性：∀x,y,z∈A, ((x,y)∈R∧(y,z)∈R)⟹(x,z)∈R{displaystyle forall x,y,zin A,~((x,y)in Rwedge (y,z)in R)implies (x,z)in R}
  

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

1. 
   R{displaystyle R}在A{displaystyle A}上自反，当且仅当IA⊆R{displaystyle I_{A}subseteq R}
   


2. 
   R{displaystyle R}在A{displaystyle A}上非自反，当且仅当R∩IA=∅{displaystyle Rcap I_{A}=emptyset }
   


3. 
   R{displaystyle R}在A{displaystyle A}上对称，当且仅当R=R−1 {displaystyle R=R^{-1} }
   


4. 
   R{displaystyle R}在A{displaystyle A}上反对称，当且仅当R∩R−1⊆IA{displaystyle Rcap R^{-1}subseteq I_{A}}
   


5. 
   R{displaystyle R}在A{displaystyle A}上非對稱，当且仅当R∩R−1=∅{displaystyle Rcap R^{-1}=emptyset }
   


6. 
   R{displaystyle R}在A{displaystyle A}上传递，当且仅当R∘R⊆R{displaystyle Rcirc Rsubseteq R}
   

闭包

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

1. 
   R′{displaystyle R'}是自反的（对称的或传递的）


2. R⊆R′{displaystyle Rsubseteq R'}


3. 对A{displaystyle A}上任何包含R{displaystyle R}的自反（对称或传递）关系R″{displaystyle R''}有R′⊆R″{displaystyle R'subseteq R''}
   

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

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

1. r(R)=R∪R0{displaystyle r(R)=Rcup R^{0}}


2. s(R)=R∪R−1{displaystyle s(R)=Rcup R^{-1}}


3. t(R)=R∪R2∪R3∪⋯{displaystyle t(R)=Rcup R^{2}cup R^{3}cup cdots }

对于有限集合A{displaystyle A}上的关系R{displaystyle R}，存在一个正整数r{displaystyle r}，使得

t(R)=R∪R2∪⋯∪Rr{displaystyle t(R)=Rcup R^{2}cup cdots cup R^{r}}

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

参见

• 有序对


• 二元集合


• 笛卡儿积


• 偏序关系


• 等价关系


• 相容关系