关系

本章主线：二元关系 → 关系的性质与运算 → 等价关系与集合划分 → 偏序关系 → 图与算法中的关系结构。

1 从笛卡尔积到关系

设有两个集合 $A,B$ ，它们的笛卡尔积为 $A\times B=\{(a,b)\mid a\in A,\ b\in B\}$ 。

笛卡尔积列出了所有可能的有序对。例如，若 $A=\{1,2,3\}$ ， $B=\{a,b\}$ ，则

A\times B=\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}.

现在从这些有序对中选出一部分，例如

R=\{(1,a),(2,a),(3,b)\}.

由于 $R\subseteq A\times B$ ，因此 $R$ 是从集合 $A$ 到集合 $B$ 的一个二元关系。

一般地，若 $R\subseteq A\times B$ ，则称 $R$ 是从 $A$ 到 $B$ 的二元关系。

2 关系的基本记法

若 $(x,y)\in R$ ，也可以写成 $xRy$ 。

若 $(x,y)\notin R$ ，则写成 $x\not R y$ 。

例如，在整数集合上定义关系 $R$ ： $xRy\Longleftrightarrow x<y$ 。

于是 $2R5$ ，因为 $2<5$ ；而 $5\not R2$ ，因为 $5<2$ 不成立。

关系既可以用有序对集合定义，也可以用条件定义。

3 集合上的关系

若 $R\subseteq A\times A$ ，则称 $R$ 是集合 $A$ 上的关系。

例如，设 $A=\{1,2,3\}$ ，并定义

R=\{(1,1),(1,2),(2,2),(3,3)\}.

因为 $R\subseteq A\times A$ ，所以 $R$ 是集合 $A$ 上的关系。

之后讨论自反性、对称性、传递性时，默认研究的是同一个集合上的关系。

4 关系的定义域和值域

设 $R\subseteq A\times B$ 。

关系中作为第一项出现的元素组成定义域：

\operatorname{dom}(R)=\{x\in A\mid \exists y\in B,\ (x,y)\in R\}.

关系中作为第二项出现的元素组成值域：

\operatorname{ran}(R)=\{y\in B\mid \exists x\in A,\ (x,y)\in R\}.

例如，若 $R=\{(1,a),(2,a),(3,b)\}$ ，则 $\operatorname{dom}(R)=\{1,2,3\}$ ， $\operatorname{ran}(R)=\{a,b\}$ 。

5 关系的表示方法

5.1 有序对集合

直接列出关系中的全部有序对，例如 $R=\{(1,1),(1,2),(2,3)\}$ 。

5.2 条件描述

通过条件定义关系，例如 $xRy\Longleftrightarrow x\mid y$ ，表示 $x$ 整除 $y$ 。

5.3 关系矩阵

设 $A=\{a_1,a_2,\dots,a_n\}$ ，定义矩阵 $M$ ：

M_{ij}= \begin{cases} 1,&(a_i,a_j)\in R,\\ 0,&(a_i,a_j)\notin R. \end{cases}

关系矩阵与图的邻接矩阵形式相同。

5.4 有向图

把集合中的元素看作顶点。若 $xRy$ ，就在 $x$ 到 $y$ 之间连一条有向边。

因此，集合上的二元关系可以表示为一张有向图。

6 关系的基本性质

6.1 自反性

设 $R$ 是集合 $A$ 上的关系。

若每个元素都与自身有关系，即 $\forall x\in A,\ xRx$ ，则称 $R$ 具有自反性。

等价地，对任意 $x\in A$ ，都有 $(x,x)\in R$ 。

例如，相等关系 $=$ 具有自反性，因为 $x=x$ ；关系 $\le$ 也具有自反性，因为 $x\le x$ 。

关系 $<$ 不具有自反性，因为 $x<x$ 不成立。

判断自反性时，需要检查集合中每个元素是否都有自环。

6.2 反自反性

若每个元素都不与自身有关系，即 $\forall x\in A,\ x\not R x$ ，则称 $R$ 具有反自反性。

例如，严格小于关系 $<$ 具有反自反性，因为 $x\nless x$ 。

“不自反”与“反自反”不同：

不自反：至少存在一个元素没有自环；
反自反：所有元素都没有自环。

6.3 对称性

若 $xRy$ 总能推出 $yRx$ ，则称 $R$ 具有对称性。

形式化地， $\forall x,y\in A,\ xRy\Longrightarrow yRx$ 。

例如，定义 $xRy\Longleftrightarrow x-y$ 是偶数。若 $x-y$ 是偶数，则 $y-x=-(x-y)$ 也是偶数，因此该关系具有对称性。

无向图中的相邻关系也具有对称性。

关系 $\le$ 不具有对称性，因为 $2\le 3$ ，但 $3\le 2$ 不成立。

6.4 反对称性

若 $xRy$ 且 $yRx$ 能够推出 $x=y$ ，则称 $R$ 具有反对称性。

形式化地， $\forall x,y\in A,\ (xRy\land yRx)\Longrightarrow x=y$ 。

关系 $\le$ 具有反对称性，因为若 $x\le y$ 且 $y\le x$ ，则 $x=y$ 。

集合包含关系 $\subseteq$ 也具有反对称性，因为若 $A\subseteq B$ 且 $B\subseteq A$ ，则 $A=B$ 。

反对称性并不表示“关系不能对称”，而是表示两个不同元素不能同时双向相关。

相等关系既具有对称性，也具有反对称性。

6.5 对称与反对称的区别

对称性要求 $xRy\Longrightarrow yRx$ 。

反对称性要求 $xRy\land yRx\Longrightarrow x=y$ 。

对于不同元素 $x\ne y$ ：

对称关系允许 $(x,y)$ 与 $(y,x)$ 成对出现；
反对称关系不允许 $(x,y)$ 与 $(y,x)$ 同时出现。

6.6 传递性

若 $xRy$ 且 $yRz$ 能够推出 $xRz$ ，则称 $R$ 具有传递性。

形式化地， $\forall x,y,z\in A,\ (xRy\land yRz)\Longrightarrow xRz$ 。

例如，关系 $\le$ 具有传递性，因为 $x\le y$ 且 $y\le z$ 可以推出 $x\le z$ 。

整除关系也具有传递性。若 $a\mid b$ 且 $b\mid c$ ，则存在整数 $k_1,k_2$ ，使得 $b=ak_1$ ， $c=bk_2$ ，从而 $c=a(k_1k_2)$ ，因此 $a\mid c$ 。

“认识”关系通常不具有传递性。甲认识乙，乙认识丙，不能推出甲认识丙。

7 关系的运算

7.1 逆关系

设 $R\subseteq A\times B$ 。

交换每个有序对的两个分量，得到逆关系：

R^{-1}=\{(y,x)\mid (x,y)\in R\}.

例如，若 $R=\{(1,a),(2,b)\}$ ，则 $R^{-1}=\{(a,1),(b,2)\}$ 。

若关系具有对称性，则 $R=R^{-1}$ 。

7.2 关系的复合

设 $R\subseteq A\times B$ ， $S\subseteq B\times C$ 。

若存在 $y\in B$ ，使得 $xRy$ 且 $ySz$ ，则称 $x$ 与 $z$ 通过 $R,S$ 建立了复合关系。

关系复合记作 $S\circ R$ ，定义为

S\circ R=\{(x,z)\mid \exists y,\ xRy\land ySz\}.

关系复合对应图中的路径拼接：若 $x\to y$ 且 $y\to z$ ，则复合后得到 $x\to z$ 。

传递性可以写成 $R\circ R\subseteq R$ 。

8 等价关系

8.1 定义

设 $R$ 是集合 $A$ 上的关系。

若 $R$ 同时满足自反性、对称性和传递性，则称 $R$ 是集合 $A$ 上的等价关系。

等价关系用来描述“哪些元素应被看作同一类”。

8.2 相等关系

定义 $xRy\Longleftrightarrow x=y$ 。

它满足：

$x=x$ ，所以具有自反性；
若 $x=y$ ，则 $y=x$ ，所以具有对称性；
若 $x=y$ 且 $y=z$ ，则 $x=z$ ，所以具有传递性。

因此，相等关系是等价关系。

8.3 模意义下的同余

固定正整数 $m$ ，定义 $xRy\Longleftrightarrow x\equiv y\pmod m$ 。

这等价于 $m\mid(x-y)$ 。

自反性来自 $m\mid(x-x)$ 。

对称性来自：若 $m\mid(x-y)$ ，则 $m\mid(y-x)$ 。

传递性来自：若 $m\mid(x-y)$ 且 $m\mid(y-z)$ ，则 $m\mid[(x-y)+(y-z)]$ ，因此 $m\mid(x-z)$ 。

所以模 $m$ 同余是等价关系。

8.4 无向图中的连通关系

在无向图 $G=(V,E)$ 中定义： $uRv\Longleftrightarrow u$ 与 $v$ 之间存在路径。

该关系具有：

自反性：每个顶点到自身存在长度为 $0$ 的路径；
对称性：无向路径可以反向行走；
传递性：两条首尾相接的路径可以拼接。

因此，无向图中的连通关系是等价关系。

9 等价类

设 $R$ 是集合 $A$ 上的等价关系。

对任意 $a\in A$ ，定义 $a$ 的等价类：

[a]=\{x\in A\mid xRa\}.

等价类由所有与 $a$ 等价的元素组成。

例如，在模 $3$ 同余关系中：

[0]=\{\dots,-6,-3,0,3,6,\dots\},

[1]=\{\dots,-5,-2,1,4,7,\dots\},

[2]=\{\dots,-4,-1,2,5,8,\dots\}.

每个整数都属于其中一个等价类。

10 等价类为何不会部分重叠

设两个等价类 $[a]$ 与 $[b]$ 有公共元素 $x$ 。

由 $x\in[a]$ 得 $xRa$ ，由 $x\in[b]$ 得 $xRb$ 。

因为关系具有对称性，所以 $aRx$ ；再由传递性， $aRx$ 且 $xRb$ 可以推出 $aRb$ 。

现在任取 $y\in[a]$ ，则 $yRa$ 。又因为 $aRb$ ，由传递性可得 $yRb$ ，所以 $y\in[b]$ 。

因此 $[a]\subseteq[b]$ 。同理可得 $[b]\subseteq[a]$ ，于是 $[a]=[b]$ 。

由此得到：

两个等价类要么完全相同，要么没有公共元素。

11 等价关系与集合划分

11.1 集合划分

集合 $A$ 的划分是若干非空子集组成的集合族，并满足：

各子集两两不相交；
所有子集的并集为 $A$ 。

例如，集合 $A=\{1,2,3,4,5\}$ 的一种划分是

\bigl\{\{1,3\},\{2,4\},\{5\}\bigr\}.

每个元素恰好属于其中一个子集。

11.2 等价关系产生集合划分

设 $R$ 是 $A$ 上的等价关系。

因为 $R$ 具有自反性，所以对每个 $a\in A$ ，都有 $aRa$ ，因此 $a\in[a]$ 。

所以每个元素都属于某个等价类。

又因为不同等价类要么相同，要么不相交，所以所有不同的等价类构成 $A$ 的一个划分。

这个由等价类组成的集合记作 $A/R$ ，称为 $A$ 关于关系 $R$ 的商集。

11.3 集合划分产生等价关系

反过来，设集合 $A$ 被划分为若干互不相交的非空子集：

A=A_1\cup A_2\cup\cdots\cup A_k.

定义关系 $xRy\Longleftrightarrow x,y$ 属于同一个子集 $A_i$ 。

该关系具有：

自反性：每个元素都与自身位于同一个子集中；
对称性：若 $x,y$ 位于同一个子集中，则 $y,x$ 也位于同一个子集中；
传递性：若 $x,y$ 位于同一个子集中，且 $y,z$ 位于同一个子集中，则两个子集都包含 $y$ ，由划分的互不相交性可知它们必须相同，因此 $x,z$ 位于同一个子集中。

所以该关系是等价关系。

因此：

\boxed{\text{等价关系}\Longleftrightarrow\text{集合划分}}

12 并查集的数学本质

设全集为 $V=\{1,2,\dots,n\}$ 。

并查集维护的是集合 $V$ 的一个动态划分。

初始时，每个元素单独构成一个等价类：

\{1\},\{2\},\dots,\{n\}.

执行 merge(x,y) 表示加入关系 $x\sim y$ 。

由于等价关系必须满足传递性， $x$ 与 $y$ 所在的两个等价类需要整体合并。

执行 find(x) 表示寻找 $x$ 所属等价类的代表元。

判断 find(x)==find(y)，等价于判断 $[x]=[y]$ ，也就是判断 $x\sim y$ 。

因此，并查集维护的是：

\boxed{\text{等价关系诱导出的集合划分}}

代表元只是程序为每个等价类选出的标识，并不是等价类本身固有的数学结构。

13 偏序关系

13.1 定义

设 $R$ 是集合 $A$ 上的关系。

若 $R$ 同时满足自反性、反对称性和传递性，则称 $R$ 是 $A$ 上的偏序关系。

集合 $A$ 与偏序关系 $R$ 组成偏序集，记作 $(A,R)$ 。

偏序关系用来描述元素之间的先后、包含或支配关系。

13.2 数值大小关系

实数上的关系 $\le$ 满足：

$x\le x$ ；
若 $x\le y$ 且 $y\le x$ ，则 $x=y$ ；
若 $x\le y$ 且 $y\le z$ ，则 $x\le z$ 。

因此， $\le$ 是偏序关系。

13.3 集合包含关系

幂集 $\mathcal P(S)$ 上的包含关系 $\subseteq$ 满足：

$A\subseteq A$ ；
若 $A\subseteq B$ 且 $B\subseteq A$ ，则 $A=B$ ；
若 $A\subseteq B$ 且 $B\subseteq C$ ，则 $A\subseteq C$ 。

因此， $\subseteq$ 是偏序关系。

13.4 整除关系

在正整数集合上定义 $aRb\Longleftrightarrow a\mid b$ 。

整除关系具有自反性、反对称性和传递性，因此是偏序关系。

14 可比较与不可比较

在偏序集中，两个元素不一定能够比较。

若 $xRy$ 或 $yRx$ ，则称 $x,y$ 可比较；否则称它们不可比较。

例如，在集合包含关系中， $\{1\}\subseteq\{1,2\}$ ，所以二者可比较。

但 $\{1\}$ 与 $\{2\}$ 互不包含，因此不可比较。

若偏序集中任意两个元素都可比较，则称该关系为全序关系。

整数上的 $\le$ 是全序关系，而集合包含关系通常不是全序关系。

15 严格偏序

由非严格偏序 $\le$ 可以定义严格关系 $<$ ：

x<y\Longleftrightarrow x\le y\land x\ne y.

严格偏序通常满足反自反性和传递性。

在 DAG 中，若只考虑长度至少为 $1$ 的路径，则“可达”可以看作严格偏序。

16 偏序与 DAG

设 $G$ 是一张有向无环图。

定义 $uRv\Longleftrightarrow u=v$ ，或存在从 $u$ 到 $v$ 的有向路径。

该关系具有：

自反性： $uRu$ ；
传递性：路径可以拼接；
反对称性：若 $uRv$ 且 $vRu$ ，并且 $u\ne v$ ，则图中存在有向环，与 DAG 矛盾。

因此，DAG 的可达关系构成偏序关系。

拓扑排序可以看作将偏序关系扩展成一个全序关系。

17 等价关系与偏序关系的区别

等价关系满足自反性、对称性和传递性。

偏序关系满足自反性、反对称性和传递性。

等价关系回答：

哪些元素应归为同一类？

偏序关系回答：

元素之间是否存在先后、包含或支配关系？

常见对应关系：

并查集：等价关系；
无向图连通分量：等价关系；
强连通分量：等价关系；
DAG：偏序关系；
拓扑排序：偏序的线性扩展；
二维偏序：偏序关系；
集合包含：偏序关系。

19 与后续内容的联系

映射是满足存在性与唯一性条件的特殊关系，参见映射；
等价关系产生集合划分，是并查集、连通分量与强连通分量的数学基础；
偏序关系连接整除结构、DAG 与拓扑排序，参见图论的基本数学结构；
关系复合与映射复合都满足结合律，并将在代数运算结构中获得统一解释。

20 本章思考题

在整数集合上定义 $xRy\Longleftrightarrow x-y$ 是奇数。判断该关系是否具有自反性、对称性和传递性。
在整数集合上定义 $xRy\Longleftrightarrow x\le y$ 。判断该关系是否具有对称性和反对称性。
设 $A=\{1,2,3\}$ ， $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ 。判断 $R$ 是否为等价关系。
在整数集合上定义模 $4$ 同余关系，写出 $0,1,2,3$ 的等价类。
设集合划分为 $\{\{1,3\},\{2,4,6\},\{5\}\}$ ，写出该划分诱导出的等价关系。
证明无向图中的连通关系是等价关系。
说明有向图中的“单向可达”为什么通常不是等价关系。
说明强连通分量中的“互相可达”为什么是等价关系。
判断正整数集合上的整除关系是否为全序关系。
解释为什么拓扑排序可能不唯一。
说明并查集中的代表元是否是等价类本身的一部分结构。
思考路径压缩为什么不会改变集合划分。

数学 > 数学语言与证明

#数学/数学语言与证明 #数学/关系

关系

http://miqiu.space/posts/be7ca45e/

作者

Miqiu

发布于

2026年7月1日

许可协议

命题逻辑与证明方法上一篇

离散结构下一篇