关系
集合可用于描述概念，是概念的外延。具有某种性质的一类对象构成一个集合。一个系统中的各对象可具有这样或那样的属性，因而形成了一些集合。集合为描述系统中的各类对象提供了数学工具。而映射的概念提供了描述事物之间的一种单值依赖关系的工具，现世世界中，事物不是孤立的，事物之间都有联系。单值依赖联系是其中比较简单的，通过这种联系，研究事物的运动规律或状态变化。世界是复杂的，运动也是复杂的。事物之间的联系是各种各样的，不仅有单值依赖联系，更有多值依赖关系。“关系”这个概念就提供了一种描述事物的多值依赖的数学工具。这样，集合、映射关系等概念是描述自然现象及其相互联系的有力工具，为建立系统和技术过程的数学模型提供了描述工具和研究方法。映射是关系的一种特例。
系统地研究“关系”这个概念及其数学性质，就是本章的任务。本章将给出关系概念的数学定义，特别给出二元关系的几种等价的定义和常用性质、二元关系的运算，其中特别讨论了在计算机科学中具有重要应用的关系闭包运算、等价关系和偏序关系。等价关系和偏序关系不仅在计算机科学中，而且在数学中都是极为重要的。
关系的概念
“关系”这个词使人们联想到一些具体的熟知的关系。例如，父子关系、兄妹关系、姊妹关系、夫妻关系、国家间的外交关系、贸易关系；整数间大于关系、小于关系、相等关系；方阵间的相似关系、对称矩阵间的合同关系，等等。这都是些具体关系，它们都谈到一些具体事物和某种性质。因此，关系是事物间的联系，至少指两个事物并且有一定的顺序。例如，父子关系是人之间的一种关系，某甲是某乙的父亲时，则说甲与乙是父子关系。甲乙之间是一种血缘关系，是有方向的。一般地,对任一对事物，如果它们具有种联系属性，则就说它有某种联系。在实际中，总是用是否具有某种联系属性来定义具体的关系的。前面说的那些具体关系，都涉及两个事物，我们说它们是二元关系。当抽去事物的具体属性和具体联系属性，就达了关系的形式定义。非形式地说，关系就是某种性质，对所涉及的事物所形成的集的每一对有次序元素对，或具有或不具有某性质。
二元关系的第一种定义
形式地，有如下的定义
定义1：设 $A,B$ 是两个集合，一个从 $A \times B$ 到 $\set{是，否}$ 的映射 $R$ ，称为从 $A$ 到 $B$ 的一个二元关系，或 $A$ 与 $B$ 间的一个二元关系。如果 $(a,b)$ 在 $R$ 下的象为“是”，则 $a$ 与 $b$ 符合关系 $R$ ，记为 $aRb$ 。如果 $(a,b)$ 在 $R$ 下的象为“否”，则说 $a$ 与 $b$ 没有或不符合关系 $R$ ，并记为 $a \cancel{R} b$ 。若 $A=B$ ，则称 $R$ 为 $A$ 上的二元关系。
令 $f: A \to B$ ，则有 $R_f:A\times B \to \set{是,否}$ ，$\forall (x,y) \in A \times B$ ，$xR_fy$ 当且仅当 $f(x)=y$ 。于是，映射 $f$ 是 $A$ 到 $B$ 的一个二元关系。映射是二元关系的特例。于是映射 $f$ 作为二元关系仍记为 $f$ ，$\forall x \in A$ ，存在唯一 $y \in B$ 使之 $f(x)=y$ ，即 $xfy$ 。但对从 $A$ 到 $B$ 的任一二元关系 $R$ 未必有此性质，即 $\forall x \in A$ ，未必有 $y \in B$ 使得 $xRy$ 。如果对某个 $x$ 有 $y \in A$ 使得 $xRy$ ，那么 $y$ 也可能不唯一，甚至有多个，乃至无穷多个。
二元关系的第二种定义
二元关系的第二种定义
在通常的应用中，某具体的二元关系总是用具体事物之间的某种联系来确定的。由于直观的联系并不总是清楚的，因此有必要给出一个精确的定义。但是，要对联系或依赖给出一个精确的陈述是有困难的。当抽去事物的属性和联系的属性时，剩下的就是一对有次序的元素对对应的是“是”还是“否”了，所以定义1是二元关系的一个抽象定义。它正是这种直观描述事物间的联系的抽象，这个定义对具体应用十分有用。
如果用 $0$ 代替“否”，用 $1$ 代替“是”，则由定义1可知，从 $A$ 到 $B$ 的一个二元关系 $R$ 就是 $A \times B$ 的一个子集的特征函数。由定理23，$2^{A \times B}$ 与 $Ch(A \times B)$ 是一一对应的，$A \times B$ 的子集与其特征函数可以等同。于是，从 $A$ 到 $B$ 的一个二元关系就可看成是 $A \times B$ 的一个子集。因此，我们有二元关系的更形式的等价定义：
定义2：设 $A$ 与 $B$ 是两个集合。$A \times B$ 的任一子集 $R$ 称为从 $A$ 到 $B$ 的一个二元关系。如果 $(a,b) \in R$ 则称 $a$ 与 $b$ 符合关系 $R$ ，并记为 $aRb$ 。如果 $(a,b) \notin R$ ，则称 $a$ 与 $b$ 不符合关系 $R$ ，并记为 $0 \cancel{R} b$ 。如果 $A = B$ ，则称 $R$ 为 $A$ 上的一个二元关系。
定义1实际上是说关系就是某种性质，而定义2告诉我们，这种性质就是 $A \times B$ 的一个子集，即满足这种性质的那些序对之集。从形式逻辑的角度来看，定义1用揭示事物的内涵的方法来定义二元关系的。而定义2是用揭示二元关系的外延的方式来定义的。定义2比定义1更抽象，在抽象讨论二元关系时，用定义2更方便。但在讨论具体问题中的具体关系时，应用定义1更方便，因为这时往往用具体性质来定义某种具体的二元关系。
全关系与空关系
按定义2，$A \times B$ 的任一子集 $R$ 都称为 $A$ 到 $B$ 的一个二元关系。特别地，$A \times B$ 也是 $A \times B$ 的一个子集，因此也是从 $A$ 到 $B$ 的一个二元关系，我们把 $A \times B$ 叫做 $A$ 到 $B$ 的全关系，而空集 $\varnothing$ 叫做 $A$ 到 $B$ 的空关系。
相等关系
集合
$$\begin{aligned} \set{(a,a) | a \in A} \tag{1}\end{aligned}$$称为 $A$ 上的恒等或相等关系，并记为 $I_A$ 。
定义域和值域
定义3：设 $R \sube A \times B$ ，集合
$$\begin{aligned} \set{x | x \in A 且 \exists y \in B 使得 (x,y) \in R} \tag{2}\end{aligned}$$称为 $R$ 的定义域，并记为 $dom(R)$ ；而集合
$$\begin{aligned} \set{y | y \in B 且 \exists x \in A 使得 (x,y) \in R} \tag{3}\end{aligned}$$称为 $R$ 的值域，并记为 $ran(R)$ 。
一般地，$dom(R)\ne A,ran(R)\ne B$ 。
二元关系的第三种定义
定义4：设 $A,B$ 是集合，一个从 $A$ 到 $2^B$ 的映射 $R$ 称为从 $A$ 到 $B$ 的一个多值部分映射。如果 $a \in A,R(a)=\varnothing$ ，则称 $R$ 在 $a$ 无定义；而如果 $R(a) \ne \varnothing$ ，则 $\forall b \in R(a)$ ，$b$ 称为 $a$ 在 $R$ 下的一个象或值。
定义5：一个从 $A$ 到 $B$ 的多值部分映射 $R$ 称为 $A$ 到 $B$ 的一个二元关系。
〔证明(定理1)〕设 $A,B$ 是集合，$M = \set{f | f:A \to 2^B}$ ，我们证明 $M$ 与 $2^{A \times B}$ 间有一个一一对应。
令 $\varphi:M \to 2^{A \times B}$ ，其定义为 $\forall f \in M$ ，令
若记 $\varphi(f)$ 为 $R_f$ ，则在 $\varphi$ 下，$f$ 对应了一个唯一的 $A$ 到 $B$ 的二元关系 $R_f$ 。若 $f,g \in M,f \ne g$ ，则 $\exists x \in A$ 使 $f(x) \ne g(x)$ ，所以 $\exists y \in B$ 使得 $y \in f(x)$ 但 $y \notin g(x)$ ，或 $y \notin f(x)$ 但 $y \in g(x)$ 。也就是 $\exists (x,y) \in A \times B$ 使 $x R_f y$ 但 $x \cancel{R}_g y$ ，或 $x \cancel{R}_f y$ 但 $x R_g y$ 。因此，$R_f \ne R_g$ ，故 $\varphi$ 是单射。
反过来，设 $R \sube A \times B$ ，令 $f:A \to 2^B$ 。$f$ 的定义如下： $\forall x \in A$ ，若 $\forall y \in B$ ，$(x,y) \notin R$ ，则 $f(x)=\varnothing$ ；否则，$f(x)=\set{y | y \in B 且 (x,y) \in R}$ 。于是，$f \in M$ 。因此
因此，$\varphi$ 是满射。
综上，$\varphi$ 是一一对应。于是，$M$ 与 $2^{A \times B}$ 的对应元可视为一样，只是表示方式不同而已。所以，定义2与定义5等价。
证毕
上面给出了二元关系的三个等价的定义。定义5恰好描述了我们的直观说法，即（二元）关系是映射概念的推广，从单值依赖联系推广到多值依赖联系。于是，二元关系就是一个多值函数。函数概念是我们熟知的，多值函数也不陌生，从中学到大学虽然从未仔细地讨论过，但也时而碰到。在数学中，特别是在计算机科学中，二元关系的这三个等价的定义均有人使用，甚至还有的作者使用另外的等价定义。
多元关系的定义
在日常生活以及数学、计算机科学中，还常常要考虑三个事物、四个事物等之间的联系。例如，在考虑城市之间的位置关系时，我们说长春在哈尔滨与沈阳之间，石家庄在北京与郑州之间，等等。在数据库中，常把一个二维表看成一个关系，表中每一行分成若干个项。于是，有必要把二元关系的概念推广到几元关系。我们发现，由定义2进行推广较方便。
定义6：设 $A_1,A_2,\cdots,A_n$ 是 $n$ 个集合，一个 $A_1 \times A_2 \times \cdots \times A_n$ 的子集 $R$ 称为 $A_1,A_2,\cdots,A_n$ 的一个 $n$ 元关系，每个 $A_i$ 称为 $R$ 的一个域。
在数据库中，把 $n$ 元关系看成一个二维表，表的每一行对应于 $n$ 元关系 $R$ 的一个 $n$ 元组，表中没有相同的行。表的每一列取一个名 字，通常称为属性，而相应的域 $A_i$ 就是对应的属性取值范围，或者说 $A_i$ 代表的属性。因此，在这里仍用 $A_1,A_2,\cdots,A_n$ 表示其属性。而 $R$ 及其属性 $A_1,A_2,\cdots,A_n$ 的表达式
$$\begin{aligned} R(A_1,A_2,\cdots,A_n) \tag{6}\end{aligned}$$就称为关系模式。
关系的性质
在实际问题中，我们感兴趣的关系往往都具有一些特殊的性质，这些性质是：自反性、反自反性、对称性、反对称性、传递性。这些性质都是对集合 $X$ 上的二元关系 $R$ 而言的，即 $R \sube X \times X$ ，而不是指 $A$ 到 $B$ 的二元关系。二元关系的这些性质是对关系的整体言的，而不是对一两个有序对而言的。
二元关系的性质
自反性
定义7： $X$ 上的二元关系称为自反的，如果 $\forall x \in X$ ，$xRx$ 。
显然，$R$ 是自反的，当且仅当 $I_X \sube R$ 。其中 $I_X$ 是 $X$ 上的恒等关系，即
$$\begin{aligned} I_X = \set{(x,x)|x \in X} \tag{7}\end{aligned}$$反自反性
定义8： $X$ 上的二元关系 $R$ 称为反自反的，如果 $\forall x \in X$ 都有 $(x,x) \notin R$ 。
显然，反自反的二元关系必不是自反的，自反的二元关系必不是反自反的。但是不是自反的二元关系，却未必是反自反的。不是反自反的二元关系，也未必是自反的。
对称性
定义9：设 $R$ 为 $X$ 上的二元关系。如果 $\forall x,y \in X$ ，只要 $xRy$ 就有 $yRx$ ，则称 $R$ 是对称的。
定义10：令 $f:A \to B$ ， $$\begin{aligned} Ker(f) = \set{(x,y) | x,y \in A 且 f(x) = f(y)} \tag{8}\end{aligned}$$
则 $Ker(f)$ 是 $A$ 上的自反且对称的二元关系。$Ker(f)$ 称为 $f$ 的核。
反对称性
定义11：设 $R$ 为 $X$ 上的二元关系。对 $X$ 的任意元素 $x,y$ ，如果 $xRy$ 且 $yRx$ ，则 $x=y$ ，那么就称 $R$ 为反对称的。
显然，恒等关系是对称的，而且也是反对称的。集合间的包含关系 $\sube$ 是反对称关系。实数集上的“小于或等于”关系 $\le$ 是反对称的。
传递性
定义12：设 $R$ 为 $X$ 上的二元关系，如果对 $X$ 上的任意 $x,y$ ，只要 $xRy$ 且 $yRz$ ，就有 $xRz$ ，则称 $R$ 为传递关系。
相容性
定义13：集合 $X$ 上的二元关系 $R$ 称为是相容的，如果 $R$ 是自反的且又是对称的。
逆
定义14：设 $R$ 为 $A$ 到 $B$ 的二元关系，则 $R$ 的逆记为 $R^{-1}$ ，$R^{-1}$ 是 $B$ 到 $A$ 的二元关系，且
$$\begin{aligned} R^{-1} = \set{(y,x) | (x,y) \in R} \tag{9}\end{aligned}$$定理2：设 $R$ 和 $S$ 是 $A$ 到 $B$ 的二元关系。如果 $R \sube S$ ，则 $R^{-1} \sube S^{-1}$ 。
〔证明(定理2)〕设 $(x,y) \in R^{-1}$ ，则 $(y,x) \in R$ 。由于 $R \sube S$ ，则 $(y,x) \in S$ ，因此 $(x,y) \in S^{-1}$ 。故 $R^{-1} \sube S^{-1}$ 。
关于二元关系性质的结论
命题1：设 $R$ 为 $X$ 上的二元关系。如果 $R=\varnothing$ ，则 $R$ 是反自反的、对称的和传递的。如果 $R \ne \varnothing$ 且 $R$ 是反自反的和对称的，则 $R$ 不是传递的。
〔证明(命题1)〕 $R=\varnothing$ 时易根据定义得 $R$ 是反自反的、对称的和传递的。当 $R \ne \varnothing$ 时，必有 $x,y \in X$ 使得 $xRy$ 。由于 $R$ 是对称的，所以又有 $yRx$ 。因此，若 $R$ 是传递的，则 $xRx$ 。这与 $R$ 是反自反的相矛盾，所以，$R$ 不是传递的。
证毕
注：在《集合论》部分中二元关系均指的非空二元关系。
命题2： $X$ 上的二元关系 $R$ 是对称的且反对称的，当且仅当 $R \sube I_X$ 。
〔证明(命题2)〕先证充分性。若 $R \sube I_X$ ，则显然 $R$ 是对称的，并且也是反对称的。现在假设 $R$ 是对称的和反对称的，则若 $xRy$ ，那么由 $R$ 的对称性知 $yRx$ ，再由反对称性便得 $x=y$ 。这表明 $\forall (x,y) \in R$ ，均有 $x=y$ ，故 $(x,x) \in R$ ，从而 $(x,y) \in I_X$ ，即 $R \sube I_X$ 。
证毕
命题3：设 $R$ 为 $X$ 上的二元关系，$R$ 是对称的当且仅当 $R=R^{-1}$ 。
〔证明(命题3)〕先证充分性。设 $R=R^{-1}$ ，则 $\forall (x,y) \in R$ ，那么有 $(x,y) \in R^{-1}$ 。由定义14，$(y,x) \in R$ ，故 $R$ 是对称的。其次，设 $R$ 是对称的。$\forall (x,y) \in R$ ，则 $(y,x) \in R$ ，由定义14得到 $(x,y) \in R^{-1}$ ，故 $R \sube R^{-1}$ ；反过来，设 $(y,x) \in R^{-1}$ ，则 $(x,y) \in R$ ，再由 $R$ 的对称性得 $(y,x) \in R$ ，故 $R^{-1} \sube R$ 。因此，$R=R^{-1}$ 。
证毕
命题4：设 $R$ 为 $X$ 上的二元关系，$R$ 是对称的当且仅当 $R \sube R^{-1}$ 。
〔证明(命题4)〕先证充分性。设 $R \sube R^{-1}$ ，则 $\forall (x,y) \in R$ ，那么有 $(x,y) \in R^{-1}$ 。由定义14，$(y,x) \in R$ ，故 $R$ 是对称的。其次，设 $R$ 是对称的。$\forall (x,y) \in R$ ，则 $(y,x) \in R$ ，由定义14得到 $(x,y) \in R^{-1}$ ，故 $R \sube R^{-1}$ 。
证毕
二元关系的集合运算
按定义2，$X$ 到 $Y$ 的一个二元关系 $R$ 就是 $X \times Y$ 的一个子集。而集合有并、交、差、对称差、余集和Cartesian积运算，所以，二元关系也有相应运算。例如，若 $R,S$ 都是 $X$ 到 $Y$ 的二元关系，则 $R \cup S = \set{(x,y) | (x,y) \in R 或 (x,y) \in S}$ 也是 $X$ 到 $Y$ 的二元运算，即 $xR \cup Sy$ ，亦即 $xRy$ 或 $xSy$ 。仿此，经其他集合运算得到的二元关系的含义自然明了。在这里，我们着重说一下二元关系的Cartesian乘积。
设 $R$ 是 $A$ 到 $B$ 的二元关系，$S$ 为 $C$ 到 $D$ 的二元关系，则定义 $R \times S$ 为 $A,B,C,D$ 间的一个四元关系：
而不是 $\set{((a,b),(c,d))|(a,b) \in R 且 (c,d) \in S}$ 。仿此，一个 $n$ 元关系与一个 $m$ 元关系的Cartesian乘积是一个 $n+m$ 元关系。
$R$ 的余集为
关系的合成运算
二元关系是集合的Cartesian乘积的任一子集，因此关系有集合运算。但关系又是映射的推广，所以关系还应有合成运算。
关系合成的定义
定义15：设 $R$ 是 $A$ 到 $B$ ，$S$ 是 $B$ 到 $C$ 的二元关系。$R$ 与 $S$ 的合成是 $A$ 到 $C$ 的一个二元关系，记成 $R \circ S$ ，并且
$$\begin{aligned} R \circ S = \set{(x,z) | (x,z) \in A \times C 且 \exists y \in B 使得 xRy 且 yRz} \tag{12}\end{aligned}$$关系合成的性质
结合律
由定义15可知，一般说来，合成运算不满足交换律，即 $R \circ S \ne S \circ R$ 。特别地，如果 $R$ 与 $S$ 都是 $X$ 上的二元关系时，$R \circ S$ 与 $S \circ R$ 也未必相等。
不过，合成运算满足结合律，即
定理3：设 $R_1,R_2,R_3$ 分别是从 $A$ 到 $B$ ，$B$ 到 $C$ ，$C$ 到 $D$ 的二元关系，则
$$\begin{aligned} (R_1 \circ R_2) \circ R_3 = R_1 \circ (R_2 \circ R_3) \tag{13}\end{aligned}$$〔证明(定理3)〕设 $(a,d) \in (R_1 \circ R_2) \circ R_3$ ，则由定义15知，至少有一个元素 $c \in C$ 使得 $(a,c) \in R_1 \circ R_2$ 且 $(c,d) \in R_3$ 。由 $(a,c) \in R_1 \circ R_2$ 及定义15又知，存在一个元素 $b \in B$ 使得 $(a,b) \in R_1$ 且 $(b,c) \in R_2$ 。由 $(b,c) \in R_2$ 及 $(c,d) \in R_3$ 和定义15知 $(b,d) \in R_2 \circ R_3$ 。而由 $(a,b) \in R_1$ 及 $(b,d) \in R_2 \circ R_3$ 和定义便得到了 $(a,d) \in R_1 \circ (R_2 \circ R_3)$ 。因此
$$\begin{aligned} (R_1 \circ R_2) \circ R_3 \sube R_1 \circ (R_2 \circ R_3) \tag{14}\end{aligned}$$反之，设 $(a,b) \in R_1 \circ (R_2 \circ R_3)$ ，则 $\exists b \in B$ 使得 $(a,b) \in R_1$ 且 $(b,d) \in R_2 \circ R_3$ 。由 $(b,d) \in R_2 \circ R_3$ 又知 $\exists c \in C$ 使得 $(b,c) \in R_2$ 且 $(c,d) \in R_3$ 。于是，由 $(a,b) \in R_1$ 及 $(b,c) \in R_2$ 得到 $(a,c) \in R_1 \circ R_2$ ，再由 $(a,c) \in R_1 \circ R_2$ 及 $(c,d) \in R_3$ 就得到 $(a,b) \in (R_1 \circ R_2) \circ R_3$ 。因此
$$\begin{aligned} R_1 \circ (R_2 \circ R_3) \sube (R_1 \circ R_2) \circ R_3 \tag{15}\end{aligned}$$所以，$(R_1 \circ R_2) \circ R_3 = R_1 \circ (R_2 \circ R_3)$ 。
证毕
合成运算与并、交运算
定理4：设 $R_1$ 是 $A$ 到 $B$ 的二元关系，$R_2$ 和 $R_3$ 是从 $B$ 到 $C$ 的二元关系，$R_4$ 是从 $C$ 到 $D$ 的二元关系，则
(1)
$$\begin{aligned}
R_1 \circ (R_2 \cup R_3) = (R_1 \circ R_2) \cup (R_1 \circ R_3)
\tag{16}\end{aligned}$$
(2)
$$\begin{aligned} R_1 \circ (R_2 \cap R_3) \sube (R_1 \circ R_2) \cap (R_1 \circ R_3) \tag{17}\end{aligned}$$(3)
$$\begin{aligned} (R_2 \cup R_3) \circ R_4 = (R_2 \circ R_4) \cup (R_3 \circ R_4) \tag{18}\end{aligned}$$(4)
$$\begin{aligned} (R_2 \cap R_3) \circ R_4 \sube (R_2 \circ R_4) \cap (R_3 \circ R_4) \tag{19}\end{aligned}$$ 〔证明(定理4)〕
(1)设 $(a,c) \in R_1 \circ (R_2 \cup R_3)$ ，则 $\exists b \in B$ 使得 $(a,b) \in R_1$ 且 $(b,c) \in R_2 \cup R_3$ 。于是，$(b,c) \in R_2$ 或 $(b,c) \in R_3$ 。所以，$(a,b) \in R_1$ 且 $(b,c) \in R_2$ ，或 $(a,b) \in R_1$ 且 $(b,c) \in R_3$ 。因此，$(a,c) \in R_1 \circ R_2$ 或 $(a,c) \in R_1 \circ R_3$ 。故 $(a,c) \in (R_1 \circ R_2) \cup (R_1 \circ R_3)$ 。即
反之，设 $(a,c) \in (R_1 \circ R_2) \cup (R_1 \circ R_3)$ ，则 $(a,c) \in R_1 \circ R_2$ 或 $(a,c) \in R_1 \circ R_3$ 。因此，$\exists b_1 \in B$ 使得 $(a,b_1) \in R_1$ 且 $(b_1,c) \in R_2$ ，或 $\exists b_2 \in B$ 使得 $(a,b_2) \in R_1$ 且 $(b_2,c) \in R_3$ 。注意 $(b_1,c) \in R_2 \cup R_3$ 且 $(b_2,c) \in R_2 \cup R_3$ ，因此不管哪种情况，总有 $\exists b \in B$ 使 $(a,b) \in R_1$ 且 $(b,c) \in R_2 \cup R_3$ 。故 $(a,c) \in R_1 \circ (R_2 \cup R_3)$ 。所以
$$\begin{aligned} (R_1 \circ R_2) \cup (R_1 \circ R_3) \sube R_1 \circ (R_2 \cup R_3) \tag{21}\end{aligned}$$ 综上所述，$R_1 \circ (R_2 \cup R_3) = (R_1 \circ R_2) \cup (R_1 \circ R_3)$ 。
(2)设 $(a,c) \in R_1 \circ (R_2 \cap R_3)$ ，则 $\exists b \in B$ 使得 $(a,b) \in R_1$ 且 $(b,c) \in R_2 \cap R_3$ 。于是，$(b,c) \in R_2$ 且 $(b,c) \in R_3$ 。所以，$(a,b) \in R_1$ 且 $(b,c) \in R_2$ ，并且 $(a,b) \in R_1$ 且 $(b,c) \in R_3$ 。因此，$(a,c) \in R_1 \circ R_2$ 且 $(a,c) \in R_1 \circ R_3$ 。故 $(a,c) \in (R_1 \circ R_2) \cap (R_1 \circ R_3)$ 。即
反之，设 $(a,c) \in (R_1 \circ R_2) \cap (R_1 \circ R_3)$ ，则 $(a,c) \in R_1 \circ R_2$ 且 $(a,c) \in R_1 \circ R_3$ 。因此，$\exists b_1 \in B$ 使得 $(a,b_1) \in R_1$ 且 $(b_1,c) \in R_2$ ，并且 $\exists b_2 \in B$ 使得 $(a,b_2) \in R_1$ 且 $(b_2,c) \in R_3$ 。注意 $(b_1,c) \in R_2$ 不能推出 $(b_1,c) \in R_2 \cap R_3$ ，$(b_2,c) \in R_3$ 也不能推出 $(b_2,c) \in R_2 \cap R_3$ ，因此无法推出 $\exists b \in B$ 使 $(a,b) \in R_1$ 且 $(b,c) \in R_2 \cap R_3$ 。所以
$$\begin{aligned} (R_1 \circ R_2) \cap (R_1 \circ R_3) \nsubseteq R_1 \circ (R_2 \cap R_3) \tag{23}\end{aligned}$$ 综上所述，$R_1 \circ (R_2 \cap R_3) \sube (R_1 \circ R_2) \cap (R_1 \circ R_3)$ 。
(3)设 $(a,c) \in (R_2 \cup R_3) \circ R_4$ ，则 $\exists b \in B$ 使得 $(a,b) \in R_2 \cup R_3$ 且 $(b,c) \in R_4$ 。于是，$(a,b) \in R_2$ 或 $(a,b) \in R_3$ 。所以，$(a,b) \in R_2$ 且 $(b,c) \in R_4$ ，或 $(a,b) \in R_3$ 且 $(b,c) \in R_4$ 。因此，$(a,c) \in R_2 \circ R_4$ 或 $(a,c) \in R_3 \circ R_4$ 。故 $(a,c) \in (R_2 \circ R_4) \cup (R_3 \circ R_4)$ 。即
反之，设 $(a,c) \in (R_2 \circ R_4) \cup (R_3 \circ R_4)$ ，则 $(a,c) \in R_2 \circ R_4$ 或 $(a,c) \in R_3 \circ R_4$ 。因此，$\exists b_1 \in B$ 使得 $(a,b_1) \in R_2$ 且 $(b_1,c) \in R_4$ ，或 $\exists b_2 \in B$ 使得 $(a,b_2) \in R_3$ 且 $(b_2,c) \in R_4$ 。注意 $(a,b_1) \in R_2 \cup R_3$ 且 $(a,b_2) \in R_2 \cup R_3$ ，因此不管哪种情况，总有 $\exists b \in B$ 使 $(a,b) \in R_2 \cup R_3$ 且 $(b,c) \in R_4$ 。故 $(a,c) \in (R_2 \cup R_3) \circ R_4$ 。所以
$$\begin{aligned} (R_2 \circ R_4) \cup (R_3 \circ R_4) \sube (R_2 \cup R_3) \circ R_4 \tag{25}\end{aligned}$$ 综上所述，$(R_2 \cup R_3) \circ R_4 = (R_2 \circ R_4) \cup (R_3 \circ R_4)$ 。
(4)设 $(a,c) \in (R_2 \cap R_3) \circ R_4$ ，则 $\exists b \in B$ 使得 $(a,b) \in R_2 \cap R_3$ 且 $(b,c) \in R_4$ 。于是，$(a,b) \in R_2$ 且 $(a,b) \in R_3$ 。所以，$(a,b) \in R_2$ 且 $(b,c) \in R_4$ ，并且 $(a,b) \in R_3$ 且 $(b,c) \in R_4$ 。因此，$(a,c) \in R_2 \circ R_4$ 且 $(a,c) \in R_3 \circ R_4$ 。故 $(a,c) \in (R_2 \circ R_4) \cap (R_3 \circ R_4)$ 。即
反之，设 $(a,c) \in (R_2 \circ R_4) \cap (R_3 \circ R_4)$ ，则 $(a,c) \in R_2 \circ R_4$ 且 $(a,c) \in R_3 \circ R_4$ 。因此，$\exists b_1 \in B$ 使得 $(a,b_1) \in R_2$ 且 $(b_1,c) \in R_4$ ，并且 $\exists b_2 \in B$ 使得 $(a,b_2) \in R_3$ 且 $(b_2,c) \in R_4$ 。注意 $(a,b_1) \in R_2$ 不能推出 $(a,b_1) \in R_2 \cap R_3$ ，$(a,b_2) \in R_3$ 也不能推出 $(a,b_2) \in R_2 \cap R_3$ ，因此无法推出 $\exists b \in B$ 使 $(a,b) \in R_2 \cap R_3$ 且 $(b,c) \in R_4$ 。所以
$$\begin{aligned} (R_2 \circ R_4) \cap (R_3 \circ R_4) \nsubseteq (R_2 \cap R_3) \circ R_4 \tag{27}\end{aligned}$$综上所述，$(R_2 \cap R_3) \circ R_4 \sube (R_2 \circ R_4) \cap (R_3 \circ R_4)$ 。
合成运算与差运算
与并、交运算不同，合成运算与差运算并没有明显的关系。一般来说，
$$\begin{aligned} R_1 \circ (R_2 \backslash R_3) \ne (R_1 \circ R_2) \backslash (R_1 \circ R_3) \tag{28}\end{aligned}$$ $$\begin{aligned} (R_2 \backslash R_3) \circ R_4 \ne (R_2 \circ R_4) \backslash (R_3 \circ R_4) \tag{29}\end{aligned}$$
合成运算与逆运算
定理5：设 $R,S$ 是集合 $X$ 上的两个二元关系，则
(1)
$$\begin{aligned}
(R \circ S)^{-1}=S^{-1} \circ R^{-1}
\tag{30}\end{aligned}$$
(2)
$$\begin{aligned}
R \circ R^{-1}是对称的。
\tag{31}\end{aligned}$$
〔证明(定理5)〕
(1)设 $(a,c) \in (R \circ S)^{-1}$ ，则 $(c,a) \in R \circ S$ 。于是，$\exists b \in X$ 使得 $(c,b) \in R$ 且 $(b,a) \in S$ ，所以 $(b,c) \in R^{-1}$ 且 $(a,b) \in S^{-1}$ 。因此 $(a,c) \in S^{-1} \circ R^{-1}$ ，即 $(R \circ S)^{-1} \sube S^{-1} \circ R^{-1}$ 。
反之，设 $(a,c) \in S^{-1} \circ R^{-1}$ ，则 $\exists b \in X$ 使得 $(a,b) \in S^{-1}$ 且 $(b,c) \in R^{-1}$ 。于是，$(b,a) \in S$ 且 $(c,b) \in R$ ，从而 $(c,a) \in R \circ S$ 。因此，$(a,c) \in (R \circ S)^{-1}$ ，故 $S^{-1} \circ R^{-1} \sube (R \circ S)^{-1}$ 。
于是，(1)得证。
(2) 由(1)，$(R \circ R^{-1})^{-1}=(R^{-1})^{-1} \circ R^{-1}=R \circ R^{-1}$ 。由命题3可知 $R \circ R^{-1}$ 是对称的。
证毕
合成运算与关系性质
定理6：设 $R$ 是 $X$ 上的二元关系，则 $R$ 是传递的当且仅当 $R \circ R \sube R$ 。
〔证明(定理6)〕先证充分性。设 $R$ 是传递的，$(a,c) \in R \circ R$ ，则 $\exists b \in X$ 使 $(a,b) \in R,(b,c) \in R$ 。由 $R$ 的传递性得到 $(a,c) \in R$ ，故 $R \circ R \sube R$ 。
再证必要性。设 $R \circ R \sube R$ ，取 $(a,b) \in R$ 且 $(b,c) \in R$ ，则 $(a,c) \in R \circ R \sube R$ ，故 $(a,c) \in R$ 。所以，$R$ 是传递的。
证毕
定理7：集合 $X$ 上的二元关系 $R$ 是对称且传递的，当且仅当 $R = R \circ R^{-1}$ 。
〔证明(定理7)〕先证充分性。设 $R$ 是对称且传递的，则由命题3和定理6可得 $R = R^{-1}$ 且 $R \circ R \sube R$ ，因此 $R \circ R^{-1} \sube R$ 。又若 $(x,y) \in R$ ，则 $(y,x) \in R^{-1} = R$ ，因此 $(y,y) \in R \circ R = R \circ R^{-1}$ ，即 $R \sube R \circ R^{-1}$ 。所以，$R = R \circ R^{-1}$ 。
再证必要性。设 $R=R \circ R^{-1}$ ，则由定理5可知 $R$ 是对称的，从而由命题3可知 $R=R^{-1}$ 。代入 $R=R \circ R^{-1}$ 可知 $R = R \circ R$ 。由定理6可知 $R$ 是传递的。
证毕
合成运算的其他性质
定理8：设 $R_1,R_2$ 是从 $A$ 到 $B$ 的二元关系，$S_1,S_2$ 是从 $B$ 到 $C$ 的二元关系，若 $R_1 \sube R_2, S_1 \sube S_2$ ，则 $R_1 \circ S_1 \sube R_2 \circ S_2$ 。
〔证明(定理8)〕设 $(x,y) \in R_1 \circ S_1$ ，则 $\exists z \in B$ 使得 $(x,z) \in R_1$ 且 $(z,y) \in S_1$ 。由 $R_1 \sube R_2, S_1 \sube S_2$ 可得 $(x,z) \in R_2,(z,y) \in S_2$ ，因此 $(x,y) \in R_2 \circ S_2$ 。所以，$R_1 \circ S_1 \sube R_2 \circ S_2$ 。
证毕
关系的幂
关系幂的定义
定义16：设 $R$ 是 $X$ 上的一个二元关系，今递归地定义 $R$ 的非负整数次幂如下：
$$\begin{aligned} R^0=I_X,R^1=R,R^2=R \circ R,\cdots,R^{n+1}=R^n \circ R \tag{32}\end{aligned}$$关系幂的性质
定理9：设 $R$ 是 $X$ 上的二元关系，则对任意的非负整数 $m,n$ ，有
$$\begin{aligned} R^m \circ R^n = R^{m+n} \tag{33}\end{aligned}$$ $$\begin{aligned} (R^m)^n=R^{mn} \tag{34}\end{aligned}$$
证毕
定理10：设 $R,S$ 是 $X$ 上的二元关系，若 $R \sube S$ ，则 $R^n \sube S^n$ ，其中 $n$ 为自然数。
〔证明(定理10)〕 $n=0$ 和 $n=1$ 的情况显然成立。当 $n>1$ 时，设 $(a,b) \sube R^n$ ，则存在 $x_0=a,x_1,x_2,\cdots,x_{n-1},x_n=b$ 使得 $(x_i,x_{i+1}) \in R,i=1,2,\cdots,n-1$ 。又由 $R \sube S$ ，可得 $(x_i,x_{i+1}) \in S$ ，因此 $(a,b) \in S^n$ 。因此 $R^n \sube S^n$ 。
证毕
定理11：设 $X$ 是一个有限集合且 $|X|=n$ ，$R$ 为 $X$ 上的任一二元关系，则存在非负整数 $s,t$ 使得 $0 \le s < t \le 2^{n^2}$ 且 $R^s=R^t$ 。
〔证明(定理11)〕因为 $|X|=n$ ，所以 $|X \times X| = n^2$ ，从而 $|2^{X \times X}| = 2^{n^2}$ ，故 $X$ 上有 $2^{n^2}$ 个不同的二元关系。但 $R^0,R,R^2,\cdots,R^{2^{n^2}}$ 是 $X$ 上的 $2^{n^2}+1$ 个二元关系，由抽屉原理便得到至少有两个是相等的，从而有非负整数 $s,t,0 \le s < t \le 2^{n^2}$ ，使得 $R^s=R^t$ 。
证毕
定理12：设 $R$ 是 $X$ 上的二元关系。如果存在非负整数 $s,t,s < t$ ，使得 $R^s=R^t$ ，则
(1) $R^{s+k}=R^{t+k}$ ，$k$ 为非负整数；
(2) $R^{s+kp+i}=R^{s+i}$ ，其中 $p=t-s$ ，而 $k,i$ 为非负整数；
(3) 令 $S=\set{R^0,R,R^2,\cdots,R^{t-1}}$ ，则对任意的非负的整数 $q$ 有 $R^q \in S$ 。
〔证明(定理12)〕(1) $R^{s+k}=R^s \circ R^k = R^t \circ R^k = R^{t+k}, k \ge 0$ 。
(2) 当 $k=0$ 时，由(1)知对任意 $i \ge 0$ 有(2)成立。假设当 $k \le m, m \ge 0$ 时(2)成立，则当 $k=m+1$ 时有
故对任意非负整数 $k,i$ ，(2)都成立。
(3) 设 $q$ 是任一非负整数。如果 $q < t$ ，则显然有 $R^q \in S$ 。若 $q \ge t$ ，则由带余除法定理 $q$ 可表示成
于是，由(2)得到
$$\begin{aligned} R^q=R^{s+kp+i}=R^{s+i} \tag{37}\end{aligned}$$再由 $0 \le i < p = t-s$ 得到 $0 \le s + i < t$ ，故得 $R^q \in S$ 。
证毕
关系的闭包
关系的另一种重要的运算是闭包运算，它是个一元运算。利用一个已知的关系得到另一个复杂的关系。引入这种运算的一个动机是想在原来的关系上扩大一些，使得所得到的关系具有所需要的性质，以适应某种需要或简化科学结论的逻辑关系。但是，这种扩大又应是尽量地小。在计算机科学中，传递闭包、自反传递闭包有极其重要的应用。
闭包的定义
一般地，若 $\mathscr{P}$ 是关系的某些性质的集合，则关系 $R$ 的 $\mathscr{P}$—闭包就是包含 $R$ 就是包含 $R$ 且具有 $\mathscr{P}$ 中所有性质的所有关系的交。
传递闭包
传递闭包的定义
定义17：设 $R$ 是 $X$ 上的一个二元关系。$X$ 上的一切包含 $R$ 的传递关系的交称为 $R$ 的传递闭包，用 $R^+$ 表示。即
$$\begin{aligned} R^+=\bigcap_{\substack{R \sube R' \\ (R'是传递的)}}R' \tag{38}\end{aligned}$$于是，$R+$ 是包含 $R$ 的那些关系中最小的（在包含关系 $\sube$ 下）的那个。
传递闭包的表示
定理13：设 $R$ 为 $X$ 上的二元关系，则
$$\begin{aligned} R^+=\bigcup_{n=1}^{\infin}R^n=R \cup R^2 \cup R^3 \cup \cdots \tag{39}\end{aligned}$$ 〔证明(定理13)〕首先证明 $R^+ \sube \bigcup_{n=1}^{\infin} R^n$ 。由定义17，只需证明 $\bigcup_{n=1}^{\infin}R^n$ 是包含 $R$ 的传递关系即可。而 $R \sube \bigcup_{n=1}^{\infin}R^n$ 是显然的。今证 $\bigcup_{n=1}^{\infin}R^n$ 是传递的。为此，设 $(a,b) \in \bigcup_{n=1}^{\infin}R^n$ ，且 $(b,c) \in \bigcup_{n=1}^{\infin}R^n$ ，则存在正整数 $m,n$ 使得 $(a,b) \in R^m$ 且 $(b,c) \in R^n$ 。于是，$(a,c) \in R^m \circ R^n = R^{m+n}$ ，从而 $(a,c) \in \bigcup_{n=1}^{\infin}R^n$ 。所以，$\bigcup_{n=1}^{\infin}R^n$ 是传递的。
其次，证明 $\bigcup_{n=1}^{\infin}R^n \sube R^+$ 。为此，设 $(a,b) \in \bigcup_{n-1}^{\infin}R^n$ ，则存在某个正整数 $m$ ，使得 $(a,b) \in R^m$ 。若 $m=1$ ，则 $(a,b) \in R \sube R^+$ ；若 $m>1$ ，则 $\exists b_1,b_2,\cdots,b_{m+1} \in X$ ，使得 $(a,b_1) \in R, (b_1,b_2) \in R, \cdots, (b_{m-1},b) \in R$ 。但 $R \sube R^+$ ，所以，$(a,b) \in R^+,(b_i,b_{i+1}) \in R^+,i=1,2,\cdots,m-2,(b_{m-1},b) \in R^+$ 。由定理15知 $R^+$ 是传递的，所以 $(a,b) \in R^+$ 。于是，$\bigcup_{n=1}^{\infin}R^n \sube R^+$ 。
因此，$R^+ = \bigcup_{n=1}^{\infin}R^n$ 。
证毕
定理14：设 $X$ 为 $n$ 元集，$R$ 为 $X$ 上的二元关系，则
$$\begin{aligned} R^+=\bigcup_{i=1}^{n}R^i \tag{40}\end{aligned}$$〔证明(定理14)〕只需证明对任一自然数 $k > n$ ，有 $R^k \sube \bigcup_{n=1}^{\infin}R^i$ 。为此，设 $(a,b) \in R^k$ ，则存在 $b_1,b_2,\cdots,b_{k-1} \in X$ 使得 $(a,b_1) \in R,(b_1,b_2) \in R, \cdots, (b_{k-2},b_{k-1}) \in R, (b_{k-1},b) \in R$ 。$a,b_1,b_2,\cdots,b_{k-1},b$ 是 $X$ 的 $k+1$ 个元素，而 $X$ 仅有 $n$ 个元素，而 $n < k$ ，所以 $a,b_1,b_2,\cdots,b_{k-1},b$ 中必有两个相等的元素。设 $b_i=b_j, 0 \le i < j \le k$ ，其中 $b_0=a,b_k=b$ 。于是，我们有 $(a,b_1) \in R,\cdots,(b_{i-1},b_i) \in R , (b_j,b_{j+1}) \in R,\cdots,(b_{k-1}b) \in R$ ，故 $(a,b) \in R^{p_1},p_1=k-(j-i) < k$ 。若 $p_1 > n$ ，则重复上述论述又可找到一个 $p_2 < p_1$ 使得 $(a,b) \in R^{p_2}$ 。如此进行，必有 $m \le n$ 使得 $(a,b) \in R^m$ 。所以。$R^k \sube \bigcup_{n=1}^{\infin}R^i$ 。因此
$$\begin{aligned} R^+=R \cup R^2 \cup \cdots \cup R^n \tag{41}\end{aligned}$$证毕
传递闭包的性质
定理15：关系 $R$ 的传递闭包 $R^+$ 是传递关系。
〔证明(定理15)〕设 $R$ 是 $X$ 上的二元关系，$aR^+b$ 且 $bR^+c$ 。由定义17，对每个包含 $R$ 的传递关系 $R'$ ，必有 $aR'b$ 且 $bR'c$ 。由 $R'$ 的传递性得到 $aR'c$ 。由于 $\forall R'$ 都有 $(a,c) \in R'$ ，因此 $(a,c) \in \bigcap_{R \sube R'}R'$ 。即 $aR^+c$ 。因此，$R^+$ 是传递的。
证毕
定理16： $R$ 是传递关系当且仅当 $R^+ = R$ 。
〔证明(定理16)〕先证必要性。由定义17易得 $R$ 是传递关系时 $R^+=R$ 。再证充分性。若 $R^+=R$ ，由定理15知 $R^+$ 是传递关系，则 $R$ 也是传递关系。
证毕
定理17：设 $R,S$ 是 $X$ 上的二元关系，则
(1)
其中 $\varnothing$ 为空集，即空关系。
(2)
$$\begin{aligned} R \sube R+ \tag{43}\end{aligned}$$(3)
$$\begin{aligned} (R^+)^+=R^+ \tag{44}\end{aligned}$$(4)
$$\begin{aligned} (R \cup S)^+ \supe R^+ \cup S^+ \tag{45}\end{aligned}$$ 〔证明(定理17)〕(1)由定义12，空关系 $\varnothing$ 本身就是传递关系，再由定理16可知 $\varnothing^+=\varnothing$ 。
(2) 由定理13易得。
(3) 由 定理15得 $R^+$ 是传递关系，再由定理16可得 $(R^+)^+=R^+$ 。
(4) $\forall (a,b) \in R^+ \cup S^+$ ，则 $(a,b) \in R^+$ 或 $(a,b) \in S^+$ 。如果 $(a,b) \in R^+$ ，则由定理13，存在正整数 $k$ 使得 $(a,b) \in R^k$ 。因此，存在 $a=x_0,x_1,x_2,\cdots,x_{k-1},b=x_k$ 使得 $(x_i,x_{i+1}) \in R$ 对 $i=0,1,2,\cdots,k-1$ 成立。由于 $R \sube R \cup S$ ，因此 $(x_i,x_{i+1}) \in R \cup S$ 对 $i=0,1,2,\cdots,k-1$ 也成立。故 $(a,b) \in (R \cup S)^k$ ，即 $(a,b) \in \bigcup_{n=1}^{\infin}(R\cup S)^n$ ，由定理13可得 $(a,b) \in (R \cup S)^+$ 。对于 $(a,b) \in S^+$ ，由类似的推导可得 $(a,b) \in (R \cup S)^+$ 。因此，$(R \cup S)^+ \supe R^+ \cup S^+$ 。
自反传递闭包
自反传递闭包的定义
定义18：设 $R$ 为 $X$ 上的二元关系。$X$ 上包含 $R$ 的所有自反且传递的二元关系的交称为 $R$ 的自反传递闭包，记为 $R^*$ 。
自反传递闭包的表示
定理18：设 $R$ 是 $X$ 上二元关系，则
$$\begin{aligned} R^*=R^0 \cup R^+ \tag{46}\end{aligned}$$其中 $R^0=I_X$ 。
〔证明(定理18)〕 $\forall x \in X$ ，有 $(x,x) \in I_X=R^0$ ，即 $(x,x) \in R^0 \cup R^+$ 。所以 $R^0 \cup R^+$ 是自反的。又因为定理15得 $R^+$ 是传递的，所以对任意 $(a,b) \in R^+ ,(b,c) \in R^+$ 有 $(a,c) \in R^+$ 。而对 $(a,b) \in R^0 \cup R^+,(b,c) \in R^0 \cup R^+$ ，若 $(a,b) \in R^0$ 且 $(b,c) \in R^0$ ，则 $a=b,b=c$ ，即 $a=c$ ，所以 $(a,c) \in R^0 \sube R^0 \cup R^+$ ；若 $(a,b) \in R^0$ 且 $(b,c) \in R^+$ ，则 $a=b$ ，因此 $(a,c) = (b,c) \in R^+ \sube R^0 \cup R^+$ ；若 $(a,b) \in R^+$ 且 $(b,c) \in R^0$ ，则 $b=c$ ，得 $(a,c)=(a,b) \in R^+ \sube R^0 \cup R^+$ ；若 $(a,b) \in R^+$ 且 $(b,c) \in R^+$ ，则由 $R^+$ 的传递性可知 $(a,c) \in R^+ \sube R^0 \cup R^+$ 。故 $R^0 \cup R^+$ 也是传递的。所以 $R^0 \cup R^+$ 是自反且传递的，因此 $R^* \sube R^0 \cup R^+$ 。
现在证明 $R^0 \cup R^+ \sube R^*$ 。为此，设 $(a,b) \in R^0 \cup R^+$ ，则当 $a=b$ 时，$(a,b) \in R^0$ ；若 $a \ne b$ ，则 $(a,b) \in R^+$ ，此时对每个包含 $R$ 的传递关系 $R'$ 有 $(a,b) \in R'$ 。于是，$(a,b) \in R^0 \cup R'$ 。其次，包含 $R$ 的每个自反传递关系 $S$ 必是包含 $R$ 的传递关系。因此 $(a,b)$ 属于每个包含 $R$ 的自反传递关系，故 $(a,b) \in R^*$ 。从而 $R^0 \cup R^+ \sube R^*$ 。因此
证毕
于是
$$\begin{aligned} R^*=R^0 \cup R^+ = \sum_{i=0}^{\infin}R^n \tag{48}\end{aligned}$$定理19：设 $X$ 为 $n$ 元集，$R$ 为 $X$ 上的二元关系，则 $R^*=\bigcup_{i=0}^{n}R^i$ 。
〔证明(定理19)〕由定理18知 $R^* = R^0 \cup R^+$ ，再由定理14可知 $R^+ = \bigcup_{i=1}^{n}R^i$ ，因此 $R^* = \bigcup_{i=0}^{n}R^i$ 。
证毕
自反传递闭包的性质
定理20：关系 $R$ 的自反传递闭包 $R^*$ 是自反传递关系。
〔证明(定理20)〕设 $R$ 是 $X$ 上的二元关系，$aR^*b$ 且 $bR^*c$ 。由定义18，对每个包含 $R$ 的自反传递关系 $R'$ ，必有 $aR'b$ 且 $bR'c$ 。由 $R'$ 的自反传递性得到 $aR'c$ 。由于 $\forall R'$ 都有 $(a,c) \in R'$ ，因此 $(a,c) \in \bigcap_{R \sube R'}R'$ 。即 $aR^*c$ 。因此，$R^*$ 是传递的。而 $\forall x \in X$ ，由于 $R'$ 是自反传递的，故 $xR'x$ 对所有 $R'$ 都满足，因此，$(x,x) \in \bigcap_{R \sube R'}R'$ 。所以 $R^*$ 是自反的。
证毕
定理21： $R$ 是自反传递关系当且仅当 $R^*=R$ 。
〔证明(定理21)〕先证必要性。由定义18易得 $R$ 是自反传递关系时 $R^*=R$ 。再证充分性。当 $R^*=R$ 时，由定理20可知 $R^*$ 是自反传递关系，因此 $R$ 也是自反传递关系。
证毕
定理22：设 $R$ 为 $X$ 上的二元关系，则
(1)
$$\begin{aligned}
R \circ R^* = R^* \circ R = R^+
\tag{49}\end{aligned}$$
(2)
$$\begin{aligned}
(R^*)^*=R^*
\tag{50}\end{aligned}$$
(2) 由定理20可知 $R^*$ 本身也是自反传递关系，因此由定理21可得 $(R^*)^*=R^*$ 。
证毕
自反闭包
自反闭包的定义
定义19： $X$ 上二元关系 $R$ 的自反闭包记为 $r(R)$ 。$r(R)$ 定义为 $X$ 上包含 $R$ 的所有自反关系的交。
自反闭包的表示
定理23：设 $R$ 是 $X$ 上的二元关系，则
$$\begin{aligned} r(R)=R^0 \cup R = I_X \cup R \tag{53}\end{aligned}$$〔证明(定理23)〕 $\forall x \in X$ ，有 $(x,x) \in R^0 = I_X$ ，因此 $(x,x) \in R^0 \cup R$ ，即 $R^0 \cup R$ 是自反的。因此，$r(R) \sube R^0 \cup R$ 。$\forall (x,y) \in R^0 \cup R$ ，则 $(x,y) \in R^0$ 或 $(x,y) \in R$ 。设 $R'$ 为包含 $R$ 的一自反关系。若 $(x,y) \in R^0$ ，则 $x=y$ ，则由于 $R'$ 是自反的，$(x,y) \in R'$ ；若 $(x,y) \in R$ ，则由于 $R'$ 包含 $R$ ，$(x,y) \in R'$ 。因此对任一 $R'$ 都有 $(x,y) \in R'$ 。因此，$(x,y)$ 属于所有 $R'$ 的交，即 $R^0 \cup R \sube r(R)$ 。综上所述，$r(R) = R^0 \cup R$ 。
证毕
自反闭包的性质
定理24：关系 $R$ 的自反闭包 $r(R)$ 是自反关系。
〔证明(定理24)〕设 $R$ 是 $X$ 上的二元关系。对每个包含 $R$ 的自反关系 $R'$ ，$\forall x \in X$ ，有 $xR'x$ ，因此 $(x,x) \in \bigcap_{R \sube R'}R'$ ，即 $(x,x) \sube r(R)$ ，因此 $r(R)$ 是自反的。
证毕
定理25： $R$ 是自反关系当且仅当 $r(R)=R$ 。
〔证明(定理25)〕先证必要性。由定义19易得 $R$ 是自反传递关系时 $r(R)=R$ 。再证充分性。当 $r(R)=R$ 时，由定理24可知 $r(R)$ 是自反关系，因此 $R$ 也是自反关系。
证毕
对称闭包
对称闭包的定义
定义20： $X$ 上二元关系 $R$ 的对称闭包记为 $s(R)$ 。$s(R)$ 定义为 $X$ 上包含 $R$ 的所有对称关系的交。
对称闭包的表示
定理26：设 $R$ 是 $X$ 上的二元关系，则
$$\begin{aligned} s(R) = R \cup R^{-1} \tag{54}\end{aligned}$$〔证明(定理26)〕若 $(x,y) \in X \times X$ 且 $(x,y) \in R \cup R^{-1}$ ，则 $(x,y) \in R$ 或 $(x,y) \in R^{-1}$ 。当 $(x,y) \in R$ 时，$(y,x) \in R^{-1} \sube R \cup R^{-1}$ ；当 $(x,y) \in R^{-1}$ 时，$(y,x) \in R \sube R \cup R^{-1}$ 。不管怎么样，$(y,x) \in R \cup R^{-1}$ ，因此 $R \cup R^{-1}$ 是对称关系。由定义20可知 $s(R) \sube R \cup R^{-1}$ 。同时对于任一包含 $R$ 的自反关系 $R'$ 来说，$\forall (x,y) \in R \cup R^{-1}$ ，若 $(x,y) \in R$ ，则由于 $R'$ 包含 $R$ 可知 $(x,y) \in R'$ ；若 $(x,y) \in R^{-1}$ ，则 $(y,x) \in R$ ，由 $R'$ 包含 $R$ 可知 $(y,x) \in R'$ ，又因为 $R'$ 是对称的，得 $(x,y) \in R'$ 。不管那种情况都有 $(x,y) \in R'$ ，所以 $(x,y)$ 属于所有 $R'$ 的交。故 $(x,y) \in s(R)$ ，即 $R \cup R^{-1} \sube s(R)$ 。综上所述，$R \cup R^{-1} = s(R)$ 。
证毕
对称闭包的性质
定理27：关系 $R$ 的对称闭包 $r(R)$ 是对称关系。
〔证明(定理27)〕设 $R$ 是 $X$ 上的二元关系。对每个包含 $R$ 的对称关系 $R'$ ，对 $(x,y) \in R'$ ，有 $(y,x) \in R'$ ，因此对 $(x,y) \in \bigcap_{R \sube R'}R'$ ，有 $(y,x) \in \bigcap_{R \sube R'}R'$ 即 $(x,x) \sube r(R)$ ，因此 $s(R)$ 是对称的。
证毕
定理28： $R$ 是对称关系当且仅当 $s(R)=R$ 。
〔证明(定理28)〕先证必要性。由定义20易得 $R$ 是对称传递关系时 $r(R)=R$ 。再证充分性。当 $s(R)=R$ 时，由定理27可知 $s(R)$ 是对称关系，因此 $R$ 也是对称关系。
证毕
等价闭包
等价闭包的定义
定义21： $X$ 上二元关系 $R$ 的等价闭包记为 $e(R)$ 。$e(R)$ 定义为 $X$ 上包含 $R$ 的所有自反对称传递关系的交。
等价闭包的表示
定理29：设 $R$ 为 $X$ 上的一个二元关系，则
$$\begin{aligned} e(R)=(R \cup R^{-1})^* \tag{55}\end{aligned}$$〔证明(定理29)〕由(48)可知 $R \sube R \cup R^{-1} \sube (R \cup R^{-1})^*$ 。而根据(54)可知 $(R \cup R^{-1})^* = s(R)^*$ ，所以 $(R \cup R^{-1})^*$ 是是自反对称传递的。因此 $e(R) \sube (R \cup R^{-1})^*$ 。其次，设 $(x,y) \in (R \cup R^{-1})^*$ 。若 $x=y$ ，则 $(x,y) \in e(R)$ ；若 $x \ne y$ ，则由(48)可知存在一个自然数 $m$ 使得 $(x,y) \in (R \cup R^{-1})^m$ 。于是，$\exists z_1,z_2,\cdots,z_{m-1} \in X$ 使得 $(x,z_1) \in R \cup R^{-1},(z_1,z_2) \in R \cup R^{-1},\cdots,(z_{m-1},y) \in R \cup R^{-1}$ 。若 $S$ 是包含 $R$ 的任一的自反对称传递关系，则由定义20和(54)可得 $R \cup R^{-1} \sube S$ ，所以有 $(x,y) \in S$ 。对每个自反对称传递关系均满足该关系，因此 $(x,y) \in e(R)$ ，故 $(R \cup R^{-1})^* \sube e(R)$ 。综上所述，$e(R) = (R \cup R^{-1})^*$ 。
闭包的一些结论
定理30：设 $R$ 是 $X$ 上的二元关系，则
(1)
$$\begin{aligned}
r(s(R))=s(r(R))
\tag{56}\end{aligned}$$
(2)
$$\begin{aligned}
r(R^+)=r(R)^+=R^*
\tag{57}\end{aligned}$$
(3)
$$\begin{aligned}
s(R)^+ \supe s(R^+)
\tag{58}\end{aligned}$$
要证明这个定理，先来证明两个引理。
引理1：设 $R$ 是 $X$ 上的二元关系，则
$$\begin{aligned} (R^0 \cup R)^{-1} = R^0 \cup R^{-1} \tag{59}\end{aligned}$$ 〔证明(引理1)〕取 $(x,y) \in (R^0 \cup R)^{-1}$ ，有 $(y,x) \in R^0 \cup R$ ，即 $(y,x) \in R^0$ 或 $(y,x) \in R$ 。若 $(y,x) \in R^0$ ，则 $x=y$ ，此时有 $(x,y) \in R^0$ ；若 $(y,x) \in R$ ，则 $(x,y) \in R^{-1}$ 。因此，$(x,y) \in R^0 \cup R^{-1}$ ，即 $(R^0 \cup R)^{-1} \sube R^0 \cup R^{-1}$ 。
取 $(x,y) \in R^0 \cup R^{-1}$ ，有 $(x,y) \in R^0$ 或 $(x,y) \in R^{-1}$ 。若 $(x,y) \in R^0$ ，则 $x=y$ ，此时有 $(y,x) \in R^0$ ；若 $(x,y) \in R^{-1}$ ，则 $(y,x) \in R$ 。综上所述，$(y,x) \in R^0 \cup R$ ，即 $(x,y) \in (R^0 \cup R)^{-1}$ 。因此，$R^0 \cup R^{-1} \sube (R^0 \cup R)^{-1}$ 。
综上所述，$(R^0 \cup R)^{-1} = R^0 \cup R^{-1}$ 。
证毕
引理2：设 $R$ 是 $X$ 上的 $n$ 元关系，则
$$\begin{aligned} (R^0 \cup R)^n = \bigcup_{i=0}^{n}R^i \tag{60}\end{aligned}$$〔证明(引理2)〕对 $n=1$ ，显然上式成立。现假设 $n=k$ 时成立，现证明 $n=k+1$ 时成立。由定理4可得
$$\begin{aligned} (R^0 \cup R)^{k+1} =& (R^0 \cup R)^k \circ (R^0 \cup R) = \left(\bigcup_{i=0}^{k}R^i\right) \circ (R^0 \cup R) \\ =& \bigcup_{i=0}^{k}(R^i \circ (R^0 \cup R)) = \bigcup_{i=0}^{k}((R^i \circ R^0) \cup (R^i \circ R)) \text{（定理4）}\\ =& \bigcup_{i=0}^{k}(R^i \cup R^{i+1}) = \bigcup_{i=0}^{k+1}R^i \tag{61}\end{aligned}$$证毕
现在我们来证明定理30。
〔证明(定理30)〕
(1)由(53)、
(54)和引理1可得
(2) $r(R^+) = (R^+)^0 \cup R^+ = R^0 \cup R^+ = R^*$ 。而由引理2得 $r(R)^+ = (R^0 \cup R)^+ = \bigcup_{n=1}^{\infin}(R^0 \cup R)^n = \bigcup_{n=1}^{\infin}\left(\bigcup_{k=0}^{n}R^k\right) = \bigcup_{n=0}^{\infin}R^n = R^*$ 。
(3)由定理13和定理10可知由 $R \sube s(R)$ 可得到 $R^+ \sube s(R)^+$ 。从而，$s(R^+) \sube s(s(R)^+) = s(R)^+$ （ $s(R)$ 为对称关系，则 $s(R)^+$ 也为对称关系，故由定理28可知 $s(s(R)^+)=s(R)^+$ ）。因此，$s(R^+) \sube s(R)^+$ 。
证毕
关系矩阵和关系图
关系这个概念对数学、计算机科学以及其他学科极其重要。因此，如何描述或表示关系，使得直观、形象、便于计算机处理就显得十分重要。本节介绍有穷集合上二元关系的矩阵表示和图表示。关系的图表示直观形象，有启发性。关系的矩阵表示便于计算机存储与处理。
关系矩阵的定义
定义22：设 $X$ 是一个 $n$ 元集，并且其元素编了号，不妨设 $X=\set{x_1,x_2,\cdots,x_m}$ 。类似地，设 $y=\set{y_1,y_2,\cdots,y_n}$ ，令 $R$ 是 $X$ 到 $Y$ 的一个二元关系。由 $R$ 定义一个 $m \times n$ 矩阵 $B=(b_{ij})$ 如下： $\forall (x_i,y_j) \in X \times Y$
$$\begin{aligned} b_{ij} = \begin{cases} 1,若x_iRy_j \\[5pt] 0,若x_i \cancel{R} y_j \end{cases} \tag{63}\end{aligned}$$矩阵 $B$ 称为关系 $R$ 的矩阵。
我们看到从 $X$ 到 $Y$ 的二元关系的矩阵是以 $0$ 或 $1$ 为项的矩阵，这种以 $0,1$ 为项的矩阵称为布尔矩阵。其次，在建立 $R$ 的矩阵时，首 要对 $X$ 和 $Y$ 的元素进行编号。不同的编号方法得到的矩阵，一般是不相等的，但都能忠实地反映 $R$ 的全部信息。不同编号下所得到的关系矩阵尽管不一样，但可以互相转化。用线性代数的术语来描述，就是在行和列的同样交换下可从一种表示变为另一种表示。确切地，有
命题5：设 $X$ 和 $Y$ 是两个有限集，$|X|=m,|Y|=n$ ，$\pi_1$ 为 $X,Y$ 的一种编号法，$\pi_2$ 为 $X,Y$ 的另一编号法。令 $B_1$ 为在 $\pi_1$ 下 $X$ 到 $Y$ 的关系 $R$ 的矩阵，$B_2$ 为在 $\pi_2$ 下 $R$ 的矩阵，则存在 $m \times m,n \times n$ 置换矩阵 $P_1,P_2$ 使得
$$\begin{aligned} B_1 = P_1B_2P_2 \tag{64}\end{aligned}$$所谓置换矩阵就是每行每列仅有一个 $1$ 的布尔矩阵。当 $R$ 为 $X(|X|=n)$ 上的二元关系时，$B$ 是一个 $n \times n$ 的布尔方阵。此时 $P_1=P_2^T$ 。
〔证明(命题5)〕该命题的证明会在高等代数内容补全后给出。
于是,对具体的关系 $R$ ，采用某种编号法可使 $R$ 的矩阵有较简单形式，例如，对角分块矩阵。究竟能成什么形式的简单矩阵，以及如何找这样的编号方法,要根据 $R$ 的具体情况而定。
由定义，$R$ 的矩阵就是 $R$ 作为 $X \times Y$ 的子集的特征函数,是定义1的翻版。
关系矩阵与关系性质
命题6：设 $B$ 为 $X$ 上关系 $R$ 的矩阵，则
(1) $R$ 是自反的，当且仅当 $B$ 的对角线上的全部元素都为 $1$ ；
(2) $R$ 是反自反的当且仅当 $B$ 的对角线上的全部元素都为 $0$ ；
(3) $R$ 是对称的当且仅当 $B$ 是对称矩阵；
(4) $R$ 是反对称的当且仅当 $b_{ij}$ 与 $b_{ji}$ （ $i \ne j$ ）不同时为为 $1$ ；
(5) $R$ 是传递的当且仅当如果 $b_{ij}=1$ 且 $b_{jk}=1$ ，则 $b_{ik}=1$ ；
(6) $R^{-1}$ 的矩阵是 $B^T$ 。
〔证明(命题6)〕这个命题的结论容易由二元关系的性质和定义22得出。
证毕
关系矩阵运算
由于布尔矩阵是代数对象，便于代数运算。于是，对关系的研究转变为布尔矩阵代数研究。布尔矩阵便于计算机存储和计算机处理。为了对布尔矩阵进行代数研究，我们需要定义布尔矩阵的代数运算。矩阵的运算往往借助于元素集上的代数运算而定义的。为此，令 $B=\set{0,1}$ ，在 $B$ 上定义“逻辑加” $\lor$ ，“逻辑乘” $\land$ ，及“补” $^c$ 。具体定义见图1的表(a)(b)(c)。于是，得到一个代数系 $(B,\lor,\land,^c)$ ，称为布尔代数。在近世代数-布尔代数中，将详细地讨论这个代数系的性质及其应用。在这里仅用 $B$ 中的代数运算来定义 $B$ 上的布尔矩阵的代数运算。
图1 布尔运算表
设 $B,C$ 是两个布尔矩阵，其中 $B$ 是 $m \times p$ 的布尔矩阵，$C$ 是 $p \times n$ 的布尔矩阵。$B$ 与 $C$ 的逻辑乘是 $B$ 与 $C$ 的对应元素的逻辑乘，其结果记为 $B \land C$ ，即
$$\begin{aligned} B \land C = (b_{ij} \land b_{ij}) \tag{65}\end{aligned}$$而 $B$ 与 $C$ 的逻辑加是 $B$ 与 $C$ 的对应元素进行逻辑加，所得到的布尔矩阵记为 $B \lor C$ 。于是，
$$\begin{aligned} B \lor C = (b_{ij} \lor c_{ij}) \tag{66}\end{aligned}$$还可以定义 $B$ 的逻辑补是将 $B$ 的每个元素进行逻辑补，所得到的布尔矩阵记为 $B^c$ 。于是
$$\begin{aligned} B^c = (b_{ij}^c) \tag{67}\end{aligned}$$最后，设 $B$ 为 $m \times p$ 布尔矩阵，$C$ 为 $p \times n$ 布尔矩阵。类似于矩阵的通常乘法，我们定义 $B$ 与 $C$ 的布尔乘法 $\circ$ 。$B$ 与 $C$ 的布尔乘积记为 $B \circ C$ 。令 $B \circ C = D$ ，则按定义
$$\begin{aligned} d_{ij} = (b_{i1} \land c_{1j}) \lor (b_{i2} \land c_{2j}) \lor \cdots \lor (b_{ip} \land c_{pj}) \\[5pt] i=1,2,\cdots,m,j=1,2,\cdots,n \tag{68}\end{aligned}$$若 $B$ 是 $n \times n$ 布尔阵，则 $B \circ B$ 简记为 $B^{(2)}$ 。一般地，$B^{(k)}=B^{(k-1)} \circ B$ 。
关系矩阵运算的性质
关系矩阵与布尔代数和布尔乘积
定理31：设 $A,B,C$ 为 $n \times n$ 布尔矩阵，则
$$\begin{aligned}
A \lor B = B \lor A
\tag{69}\end{aligned}$$
$$\begin{aligned}
A \land B = B \land A
\tag{70}\end{aligned}$$
$$\begin{aligned}
(A \lor B) \lor C = A \lor (B \lor C)
\tag{71}\end{aligned}$$
$$\begin{aligned}
(A \land B) \land C = A \land (B \land C)
\tag{72}\end{aligned}$$
$$\begin{aligned}
(A \circ B) \circ C = A \circ (B \circ C)
\tag{73}\end{aligned}$$
$$\begin{aligned}
A \land (B \lor C) = (A \land B) \lor (A \land C)
\tag{74}\end{aligned}$$
$$\begin{aligned}
A \lor (B \land C) = (A \lor B) \land (A \lor C)
\tag{75}\end{aligned}$$
$$\begin{aligned}
A \circ (B \lor C) = (A \circ B) \lor (A \circ C)
\tag{76}\end{aligned}$$
$$\begin{aligned}
(B \lor C) \circ A = (B \circ A) \lor (C \circ A)
\tag{77}\end{aligned}$$
〔证明(定理31)〕这些等式通过定理34都可以对应到集合运算和关系运算中的结论上。其中(69)↔集合及其运算-(25)、(70)↔集合及其运算-(38)、(71)↔集合及其运算-(26)、(72)↔集合及其运算-(39)、(73)↔(13)、(74)↔集合及其运算-(51)、(74)↔集合及其运算-(52)、(76)↔(16)、(77)↔(18)。
证毕
关系矩阵与关系的交、并、补运算
定理32：设 $R,S$ 为 $X$ 到 $Y$ 的二元关系，其矩阵分别为 $B_R$ 和 $B_S$ 。$R \cup S$ 和 $R \cap S$ 的矩阵分别记为 $B_{R \cup S},B_{R \cap S}$ ，则
$$\begin{aligned} B_{R \cup S}=B_R \lor B_S \tag{78}\end{aligned}$$ $$\begin{aligned} B_{R \cap S}=B_R \land B_S \tag{79}\end{aligned}$$ $$\begin{aligned} B_{R^c}=B_R^c \tag{80}\end{aligned}$$
〔证明(定理32)〕设 $X=\set{x_1,x_2,\cdots,x_m},Y=\set{y_1,y_2,\cdots,y_n},B_R = (b_{R,ij}),B_S=(b_{S,ij}),B_{R \cup S} = (b_{R \cup S,ij}),B_{R \cap S} = (b_{R \cap S,ij})$ 。
当 $b_{R \cup S,ij}=1$ 时，由定义22可知 $(x_i,y_j) \in R \cup S$ ，则 $(x_i,y_j) \in R$ 或 $(x_i,y_j) \in S$ 。因此由定义22可知 $b_{R,ij}=1$ 或 $b_{S,ij}=1$ ，则根据图1可知 $b_{R,ij} \lor b_{S,ij} = 1 = b_{R \cup S,ij}$ 。当 $b_{R \cup S,ij}=0$ 时，由定义22可知 $(x_i,y_j) \notin R \cup S$ ，则 $(x_i,y_j) \notin R$ 且 $(x_i,y_j) \notin S$ 。因此由定义22可知 $b_{R,ij}=0$ 且 $b_{S,ij}=0$ ，则根据图1可知 $b_{R,ij} \lor b_{S,ij} = 0 = b_{R \cup S,ij}$ 。综上，$b_{R \cup S,ij} = b_{R,ij} \lor b_{S,ij}$ 。因此由(65)可得 $B_{R \cup S}=B_R \lor B_S$ 。
当 $b_{R \cap S,ij}=1$ 时，由定义22可知 $(x_i,y_j) \in R \cap S$ ，则 $(x_i,y_j) \in R$ 且 $(x_i,y_j) \in S$ 。因此由定义22可知 $b_{R,ij}=1$ 且 $b_{S,ij}=1$ ，则根据图1可知 $b_{R,ij} \land b_{S,ij} = 1 = b_{R \cap S,ij}$ 。当 $b_{R \cap S,ij}=0$ 时，由定义22可知 $(x_i,y_j) \notin R \cap S$ ，则 $(x_i,y_j) \notin R$ 或 $(x_i,y_j) \notin S$ 。因此由定义22可知 $b_{R,ij}=0$ 或 $b_{S,ij}=0$ ，则根据图1可知 $b_{R,ij} \land b_{S,ij} = 0 = b_{R \cap S,ij}$ 。综上，$b_{R \cap S,ij} = b_{R,ij} \land b_{S,ij}$ 。因此由(66)可得 $B_{R \cap S}=B_R \land B_S$ 。
当 $b_{R^c,ij}=1$ 时，由定义22可知 $(x_i,y_j) \in R^c$ ，则 $(x_i,y_j) \notin R$ ，因此由定义22可知 $b_{R,ij} = 0$ 。根据图1可知 $b_{R,ij}^c = 1 = b_{R^c}$ 。当 $b_{R^c,ij}=0$ 时，由定义22可知 $(x_i,y_j) \notin R^c$ ，则 $(x_i,y_j) \in R$ ，因此由定义22可知 $b_{R,ij} = 1$ 。根据图1可知 $b_{R,ij}^c = 0 = b_{R^c}$ 。因此由(67)可得 $B_{R^c}=B_R^c$ 。
证毕
关系矩阵与关系的合成
定理33：设 $X,Y,Z$ 是有限集，$|X|=m,|Y|=p,|Z|=n$ 。$R$ 是 $X$ 到 $Y$ 的二元关系，$S$ 是 $Y$ 到 $Z$ 的二元关系，$R,S,R \circ S$ 的矩阵分别为 $B_R,B_S,B_{R \circ S}$ ，则
$$\begin{aligned} B_{R \circ S} = B_R \circ B_S \tag{81}\end{aligned}$$〔证明(定理33)〕设 $B_R = (b_{R,ij}),B_S=(b_{S,ij}),B_{R \circ S} = (b_{R \circ S,ij})$ ，由(68)，$B_R \circ B_S$ 的第 $i$ 行第 $j$ 列的元素为
$$\begin{aligned} b_{R \circ S,ij} = (b_{R,i1} \land b_{S,1j}) \lor (b_{R,i2} \land b_{S,2j}) \lor \cdots \lor (b_{R,ip} \land b_{S,pj}) \tag{82}\end{aligned}$$所以，若 $b_{R \circ S,ij}=1$ ，则 $x_iR \circ S z_j$ ，于是 $\exists y_k \in Y$ 使得 $x_iRy_k$ 且 $y_kSz_j$ ，从而 $b_{R,ik}=1$ 且 $b_{S,kj}=1$ ，故 $\bigvee_{k=1}^p(b_{R,ik} \land b_{S,kj})=1=b_{R \circ S,ij}$ 。若 $b_{R \circ S,ij}=0$ ，则 $x_i R \circ S y_j$ 不成立，即 $\forall y_k \in Y$ ，$x_iRy_k$ 与 $y_k S z_j$ 不同时成立。从而对 $k=1,2,\cdots,p$ ，$b_{R,ik} \land b_{S,kj} = 0$ ，即 $\bigvee_{k=1}^p(b_{R,ik} \land b_{S,kj}) = 0 = b_{R \circ S,ij}$ 。综上，一定有 $b_{R \circ S,ij} = \bigvee_{k=1}^p(b_{R,ik} \land b_{S,kj})$ ，因此由由(68)得 $B_{R \circ S} = B_R \circ B_S$ 。
证毕
关系矩阵运算与关系运算同构
定理34：定义在关系矩阵上的代数系统 $(B,\lor,\land,^c,\circ)$ 与定义在关系上的代数系统 $(R,\cup,\cap,^c,\circ)$ 同构。
〔证明(定理34)〕定义 $\varphi:R \to B$ ，$\varphi$ 定义为(63)，易得 $\varphi$ 是一个一一对应。则由定理32、定理33和定义25可得 $(B,\lor,\land,^c,\circ)$ 与 $(R,\cup,\cap,^c,\circ)$ 同构。
证毕
关系矩阵与传递闭包
用关系矩阵计算传递闭包
定理35：设 $R$ 是 $X$ 上的二元关系，$|X|=n$ ，$B$ 是 $R$ 的矩阵，$B_{R^+}$ 是 $R^+$的矩阵，简记为 $B^+$ ，则
$$\begin{aligned} B^+=B \lor B^{(2)} \lor \cdots \lor B^{(n)} \tag{83}\end{aligned}$$证毕
Warshall算法
为了由 $B$ 用上述公式计算 $B^+$ ，1962年，Warshall曾提出了如下的有效算法，其非形式描述如下：
算法1（Warshall算法）
输出： $B^+$
这个算法结束时，$A$ 中就是矩阵 $B^+$ 的全部元素。
仔细分析Warshall算法发现，当执行算法第4步时，参数 $i,k$ 是定值，只有 $j$ 的值在改变。如果 $a_{ik}=1$ 则
$$\begin{aligned} a_{ik} \land a_{kj} = 1 \land a_{kj} = a_{kj} \tag{84}\end{aligned}$$从而对一切 $j=1,2,\cdots,n$
$$\begin{aligned} a_{ij} \lor (a_{ik} \land a_{kj}) = a_{ij} \lor a_{kj} \tag{85}\end{aligned}$$如果 $a_{ik} = 0$ ，则
$$\begin{aligned} a_{ij} \lor (a_{ik} \land a_{kj}) = a_{ij} \lor (0 \land a_{kj}) = a_{ij} \lor 0 = a_{ij} \tag{86}\end{aligned}$$所以不用改变。因此可以把第四步改进为：如果 $a_{ik}=1$ ，则对一切的 $j=1,2,\cdots,n$ ，置 $a_{ij} \gets a_{ij} \lor a_{kj}$ 。由此得到改进的Warshall算法：
算法2（改进的Warshall算法）
输出： $B^+$
易见，修改后的算法要比原来的好些。以后统称为Warshall算法。
如果 $B$ 是对角分块矩阵，则 $B^+$ 还可以进一步简化。事实上，若
$$\begin{aligned} B = \begin{pmatrix} B_{n_1} & 0 & \cdots & 0 \\[5pt] 0 & B_{n_2} & \cdots & 0 \\[5pt] 0 & 0 & \ddots & 0 \\[5pt] 0 & 0 & 0 & B_{n_k} \end{pmatrix} \tag{87}\end{aligned}$$其中 $B_{n_i}$ 为 $n_i \times n_i$ 布尔矩阵，$n_i < n, \sum_{i=1}^{k}n_i=n$ ，则
$$\begin{aligned} B^(i) = \begin{pmatrix} B_{n_1}^{(i)} & 0 & \cdots & 0 \\[5pt] 0 & B_{n_2}^{(i)} & \cdots & 0 \\[5pt] 0 & 0 & \ddots & 0 \\[5pt] 0 & 0 & 0 & B_{n_k}^{(i)} \end{pmatrix} \tag{88}\end{aligned}$$于是，只须对每个低阶的子块调用Warshall算法即可。这样就可节省许多计算工作。但 $B$ 并不永远可能化成对角分块的。
Warshall算法正确性
我们根据改进的Warshall算法来说明Warshall算法的正确性。由定义12，传递关系满足只要 $iRk,kRj$ 就有 $iRj$ 。我们将这其中的 $k$ 中间结点。Warshall算法的本质就是遍历每个顶点 $k$ ，对以 $k$ 为中间结点的每一对 $i,j$ 建立传递关系。如果 $a_{ik}=0$ ，则 $i \cancel{R} k$ ，不予以考虑。如果 $a_{ik}=1$ ，此时再以 $j$ 遍历顶点，如果 $a_{kj}=1$ ，则必须要在 $i,j$ 中建立通路满足传递关系，即令 $a_{ij}=1$ ；如果 $a_{kj}=0$ ，也不予以考虑，$a_{ij}$ 不变。这个逻辑就写作如果 $a_{ik}=1$ ，则对一切的 $j=1,2,\cdots,n$ ，置 $a_{ij} \gets a_{ij} \lor a_{kj}$ 。那么遍历完 $k$ 之后，以每个节点为中间节点的关系都满足了传递关系，这个时候的关系就是包含 $R$ 的最小传递关系，即传递闭包。
关系图
关系除了用矩阵表示外，还可用图来表示。设 $X$ 和 $Y$ 为有限集，$R$ 是 $X$ 到 $Y$ 的二元关系。当用图表示 $R$ 时，先把 $X$ 与 $Y$ 的元素在纸上用点表示，并在其旁边标上这个元素的名字。然后把 $R$ 的任一序对 $(x,y)$ 用从代表 $x$ 的点画一条指向代表 $y$ 的点的矢线表示。这样就得到了一个由点、线组成的“有向图”，称为关系 $R$ 的图。注意，若 $(x,x) \in R$ 则在代表 $x$ 的点画一个又指向此点的线，称为环，见图2。
图2 关系图的的画法
关系图也完全包含了关系的全部信息，而且直观、形象，有启发性。关系
的一些性质很容易从图中看出：关系 $R$ 是自反的，当且仅当 $R$ 的图的每个顶点
均有一个环； $R$ 是反自反的，当且仅当况的图中没有环； $R$ 是对称的，当且仅当任两不同顶点间有矢线，则必有两条方向相反的矢线；关系 $R$ 是传递的，当且仅当从某顶点沿矢线经两条矢线可到另一点，则从某点到另一点有条矢线。
如果关系图分成不相连的几个部分，则关系的矩阵必能写成对角分块形式。这时，只要把连在一起的块顶点代表的元素编成相连续的号码即可。于是，如何判断一个有限关系能否在某种编号下，其矩阵为对角分块阵，以及怎样找出这个编号方法的问题，就全部解决了。
等价关系与集合的划分
前面几节对关系进行了一般的讨论。讨论了关系的性质、运算和关系的表示。本节讨论等价关系，它具有很好的性质，在数学和计算机科学中有着极其重要的应用。
等价关系与等价类
等价关系的定义
定义23（等价关系）：集合 $X$ 上的二元关系 $R$ 称为等价关系，如果 $R$ 同时具有以下三个性质：
1°. $R$ 是自反的，即 $\forall x \in X, xRx$ 。
2°. $R$ 是对称的，即如果 $xRy$ ，则 $yRx$ 。
3°. $R$ 是传递的，即如果 $xRy$ 且 $yRz$ ，则 $xRz$ 。
用 $\cong$ 在抽象讨论时，习惯上常用符号“ $\cong$ ”表示等价关系。
等价类的定义
定义24：设 $\cong$ 是 $X$ 上的一个等价关系，$x \in X$ ，$X$ 的子集 $E_x = \set{y | y \in X 且 x \cong y}$ 称为 $x$ 关于 $\cong$ 的等价类，或简称为 $x$ 的等价类。
$x$ 的等价类常也记为 $[x]$ ，即 $[x]=\set{y | y \in X 且 x \cong y}$ 。
划分
定义25：设 $X$ 为集合，$X$ 的一些非空子集形成的集族 $\mathbf{A}$ 称为 $X$ 的一个划分。如果 $\mathbf{A}$ 具有性质
1°. $\forall A,B \in \mathbf{A}$ ，若 $A \ne B$ ，则 $A \cap B = \varnothing$ 。
2°. $\bigcup_{A \in \mathbf{A}}A=X$ 。
如果 $\mathbf{A}$ 是 $X$ 的一个划分，则当 $|\mathbf{A}|=k$ 时，$\mathbf{A}$ 被称为 $X$ 的一个 $k$—划分。
等价关系与等价类的性质
等价类之集是一个划分
定理36：设 $\cong$ 是 $X$ 上的一个等价关系，则 $\cong$ 的所有等价类的集合是 $X$ 的一个划分。
〔证明(定理36)〕设 $\cong$ 的所有等价类构成的集合（族）记为 $\mathbf{A}$ 。$\forall x \in X$ ，由于 $\cong$ 是自反的，所以 $x \cong x$ ，由定义24可得 $x \in [x]$ ，故 $\mathbf{A}$ 中的每个等价类是 $X$ 的非空子集。其次，设 $A,B$ 为 $\mathbf{A}$ 的任两元素，即 $\cong$ 的两个等价类。如果 $A \ne B$ ，且 $A \cap B \ne \varnothing$ ，从而 $\exists x \in A \cap B$ 。$\forall y \in A$ ，由定义24可知 $x \cong y$ ，从而也有 $y \in B$ ，故 $A \sube B$ 。类似地，$\forall z \in B$ ，有 $x \cong z$ ，所以也得 $z \in A$ ，故 $B \sube A$ 。因此，$A = B$ 。这与假设 $A \ne B$ 矛盾，从而 $A \cap B = \varnothing$ 。于是，两个等价类相等，或不相交。其次，$\forall x \in X,[x]=\set{y| y \in X, x \cong y}$ 是 $\cong$ 的一个等价类，所以 $[x] \in \mathbf{A}$ 。因此，$\forall x \in X,x \in \bigcup_{A \in \mathbf{A}}A$ 。所以，$\bigcup_{A \in \mathbf{A}}A=X$ 。于是，$\mathbf{A}$ 是 $X$ 的一个划分。
证毕
等价关系的划分表示
定理37：设 $\mathbf{A}$ 是集 $X$ 的一个划分。令
$$\begin{aligned} \cong = \bigcup_{A \in \mathbf{A}}A \times A \tag{89}\end{aligned}$$则 $\cong$ 是 $X$ 上的一个等价关系且 $\mathbf{A}$ 就是 $\cong$ 等价类之集。
要证明该定理，先证明两个引理。
引理3：设 $\mathbf{A}$ 是集 $X$ 的一个划分。令 $\cong = \bigcup_{A \in \mathbf{A}}A \times A$ 。则 $\forall x,y \in X$ ，$x \cong y$ 当且仅当 $\exists A \in \mathbf{A}$ 使得 $x$ 与 $y$ 都属于 $A$ 。
〔证明(引理3)〕若 $x \cong y$ ，则 $(x,y) \in \bigcup_{A \in \mathbf{A}}A \times A$ ，则 $\exists A \in \mathbf{A}$ 使得 $(x,y) \in A \times A$ ，因此 $x \in A$ 且 $y \in A$ 。反之，若 $\exists A \in \mathbf{A}$ 使得 $x,y$ 都属于 $A$ ，则 $(x,y) \in A \times A \sube \bigcup_{A \in \mathbf{A}}A \times A$ ，因此 $x \cong y$ 。
证毕
引理4：设 $\mathbf{A}$ 是集 $X$ 的一个划分，$\cong$ 是定义在 $X$ 上的关系。若 $\forall x,y \in X$ ，$x \cong y$ 当且仅当 $\exists A \in \mathbf{A}$ 使得 $x$ 与 $y$ 都属于 $A$ ，则 $\cong$ 是一个等价关系。
〔证明(引理4)〕由于 $\mathbf{A}$ 是集合 $X$ 的一个划分，由定义25得 $\bigcup_{A \in \mathbf{A}}A=X$ ，则 $\forall x \in X$ 有 $\exists A \in \mathbf{A}$ 使得 $x \in A$ ，则 $x$ 与 $x$ 都属于 $A$ ，因此 $x \cong x$ ，即 $\cong$是自反的 。若 $x \cong y$ ，则由引理3知 $\exists A \in \mathbf{A}$ 使得 $x,y$ 都属于 $A$ ，则也有 $y \cong x$ ，因此 $\cong$ 是对称的。若 $x \cong y,y \cong z$ ，则由引理3知 $\exists A \in \mathbf{A}$ 使得 $x,y$ 都属于 $A$ 且 $\exists A' \in \mathbf{A}$ 使得 $y,z$ 都属于 $A'$ ，但是由定义25可知如果 $A \ne A'$ 则 $A \cap A' =\varnothing$ ，而 $y \in A$ 且 $y \in A'$ ，所以必有 $A=A'$ 。因此，$x,y,z$ 都属于 $A$ ，此时有 $x \cong z$ ，因此 $\cong$ 是传递的。即 $\cong$ 是 $X$ 上的一个等价关系。
证毕
现在来证明定理37。
〔证明(定理37)〕由引理3和引理4可得 $\cong$ 是一个等价关系。由于 $\mathbf{A}$ 是集合 $X$ 的一个划分，由定义25得 $\bigcup_{A \in \mathbf{A}}A=X$ ，则 $\forall x \in X$ 有 $\exists A \in \mathbf{A}$ 使得 $x \in A$ 。从而 $\forall y \in A$ 有 $x \cong y$ （因为 $x$ 和 $y$ 都属于 $A$ 且有引理3）。因此由定义24得 $y \in [x]$ 。即 $A \sube [x]$ 。而 $\forall y \in [x]$，有 $x \cong y$ ， 由引理3知 $y \in A$ ，所以 $[x] \sube A$ 。因此，$A = [x]$ 。因此，$\mathbf{A}$ 是 $\cong$ 的所有等价类之集。
证毕
等价关系的充要条件
定理38：集合 $X$ 上的二元关系 $\cong$ 是一个等价关系，当且仅当存在 $X$ 的一个划分 $\mathbf{A}$ 使得 $x \cong y$ 的充分必要条件是 $\exists A \in \mathbf{A}$ 使 $x,y \in A$ 。
先证明一个引理。
引理5：若两个等价关系的等价类之集相等，则这两个等价关系也相等。
〔证明(引理5)〕假设这两个等价关系为 $\cong$ 和 $\cong'$ ，$\cong$ 和 $\cong'$ 的等价类之集相等。假设这两个关系不相等，则必存在 $x,y$ 使得 $x \cong y$ 且 $x \cancel{\cong}' y$ ，或者 $x \cancel{\cong} y$ 且 $x \cong' y$ 。如果 $x \cong y$ 且 $x \cancel{\cong}' y$ ，则有 $y \in [x]_{\cong}$ 且 $y \notin [x]_{\cong'}$ ，则必然 $[x]_{\cong} \ne [x]_{\cong'}$ 。这与 $\cong$ 与 $\cong'$ 的等价类之集相等矛盾。对于 $x \cancel{\cong} y$ 且 $x \cong' y$ 的情况也类似。因此 $\cong = \cong'$ 。
证毕
现在证明定理38。
〔证明(定理38)〕先证必要性。如果集合 $X$ 上的二元关系 $\cong$ 是一个等价关系，则由定理36可得 $\cong$ 的所有等价类是集合 $X$ 的一个划分。记这个划分为 $\mathbf{A}$ ，$\mathbf{A}$ 就是 $\cong$ 的等价类之集。由引理5和定理37可得 $\cong$ 可表示为 $\cong = \bigcup_{A \in \mathbf{A}}A \times A$ 。因此由引理3可得 $x \cong y$ 的充分必要条件是 $\exists A \in \mathbf{A}$ 使得 $x$ 与 $y$ 都属于 $A$ 。再证充分性。若 $x \cong y$ 的充分必要条件是 $\exists A \in \mathbf{A}$ 使得 $x$ 与 $y$ 都属于 $A$ ，由引理4可得 $\cong$ 是一个等价关系。
证毕
等价关系与划分一一对应
定理39：集合 $X$ 上的等价关系与集合 $X$ 上的划分一一对应。
〔证明(定理39)〕设集合 $X$ 上的等价关系为 $\cong$ ，划分为 $\mathbf{A}$ 。定义 $\varphi: \cong \to \mathbf{A}$ 满足 $\varphi(\cong)$ 是 $\cong$ 的等价类之集。由引理5可得 $\varphi$ 是单射。而由定理37可得 $\varphi$ 是满射。因此，$\varphi$ 是一一对应。
证毕
商集
综上，我们得到： $X$ 上的等价关系与 $X$ 的划分是一一对应，互相确定的。等价关系 $\cong$ 确定的划分是 $\cong$ 的所有等价类之集 $\set{[x] | x \in X}$ 。$X$ 的划分 $\mathbf{A}$ 所确定的等价关系是 $\mathbf{A}$ 中的元素—— $X$ 的子集上全关系的并 $\bigcup_{A \in \mathbf{A}}A \times A$ 。因此，每个等价关系都能被解成 $X$ 的若干个不相交子集上的全关系的并。
于是，在 $X$ 上的等价关系 $\cong$ 下，$X$ 被分成若干非空不相交的子集组成的集，即等价类的全体，构成了 $X$ 的一个划分。这个划分是按等价关系来分的。所以，有
定义26：设 $\cong$ 是 $X$ 上的等价关系。由 $\cong$ 所确定的 $X$ 的划分—— $\cong$ 的所有等价类之集称为 $X$ 对 $\cong$ 的商集，并记为 $X \backslash \cong$ 。于是
$$\begin{aligned} X \backslash \cong = \set{[x]|x \in X,[x]是X的等价类} \tag{90}\end{aligned}$$等价关系的性质
定理40：设 $R,S$ 是 $X$ 上的等价关系，则 $R \circ S$ 是等价关系的充分必要条件是
$$\begin{aligned} R \circ S = S \circ R \tag{91}\end{aligned}$$〔证明(定理40)〕先证必要性。设 $R \circ S$ 是等价关系，则由 $R$ 和 $S$ 也是等价关系和命题3、(30)便得到
$$\begin{aligned} R \circ S = (R \circ S)^{-1} = S^{-1} \circ R^{-1} = S \circ R \tag{92}\end{aligned}$$再证充分性。设 $R \circ S = S \circ R$ ，由 $R$ 和 $S$ 是等价关系便可得到 $R \circ S$ 是自反的。实际上，设 $\forall x \in X$ ，有 $xRx,xSx$ ，因此由定义15可知 $xR\circ Sx$ 。又由命题3可知 $R=R^{-1},S=S^{-1}$ ，由(30)可得
$$\begin{aligned} (R \circ S)^{-1} = S^{-1} \circ R^{-1} = S \circ R = R \circ S \tag{93}\end{aligned}$$因此再由命题3可知 $R \circ S$ 是对称的。最后，由定理6可知 $R^2 \sube R,S^2 \sube S$ ，再由定理8可知 $R^2 \circ S^2 \sube R \circ S$ 。因此，由定理3可得
$$\begin{aligned} (R \circ S)^2 = (R \circ S) \circ (R \circ S) = R^2 \circ S^2 \sube R \circ S \tag{94}\end{aligned}$$从而由定理6可知 $R \circ S$ 是传递的。综上，$R \circ S$ 是等价关系。
证毕
推论1：设 $R,S$ 是 $X$ 上的等价关系，则 $R \circ S$ 是等价关系的充分必要条件是
$$\begin{aligned} R \circ S \sube S \circ R \tag{95}\end{aligned}$$〔证明(推论1)〕先证必要性。由定理40易得。再证充分性。设 $R \circ S \sube S \circ R$ 。由定理40，只需证 $S \circ R \sube R \circ S$ 即可（因为如果 $S \circ R \sube R \circ S$ ，则可得 $R \circ S = S \circ R$ ，此时由定理40可知 $R \circ S$ 是等价关系）。由于 $R,S$ 是等价关系，因此由命题3可知 $R=R^{-1},S=S^{-1}$ 。因此由(30)和定理2可得
$$\begin{aligned} S \circ R = S^{-1} \circ R^{-1} = (R \circ S)^{-1} \sube (S \circ R)^{-1} \sube R^{-1} \circ S^{-1} \sube R \circ S \tag{96}\end{aligned}$$
证毕
定理41：设 $R,S$ 是 $X$ 上的等价关系，则
$$\begin{aligned} R \circ S = (R \cup S)^+ \tag{97}\end{aligned}$$〔证明(定理41)〕由于 $R \sube R \cup S, S \sube R \cup S$ ，因此由定理8和(39)可知 $R \circ S \sube (R \cup S)^2 \sube (R \cup S)^+$ 。任取 $(x,y) \in (R \cup S)^+$ ，由(39)可知存在 $n$ 使得 $(x,y) \in (R \cup S)^n$ ，则 $\exists z_1,z_2,\cdots,z_{n-1}$ 使得 $(x,z_1) \in R \cup S, (z_1,z_2) \in R \cup S,\cdots,(z_{n-1},y) \in R \cup S$ ，即 $(x,z_1) \in R$ 或 $(x,z_1) \in S$ 、 $(z_1,z_2) \in R$ 或 $(z_1,z_2) \in S$ 、···、 $(z_{n-1},y) \in R$ 或 $(z_{n-1},y) \in S$ 。由定理3可知，必存在自然数 $k,l,k+l=n$ 使得 $(x,y) \in R^k \circ S^l$ 。由于 $R,S$ 是等价关系，由定理6可知 $R^2 \sube R,S^2 \sube S$ ，因此反复使用定理8可得 $R^k \sube R,S^l \sube S$ 。由定理8可得 $R^k \circ S^l \sube R \circ S$ ，因此 $(x,y) \in R \circ S$ ，即 $(R \cup S)^+ \sube R \circ S$ 。综上所述，$R \circ S = (R \cup S)^+$ 。
证毕
映射按等价关系分解
等价关系的另一个重要应用是利用给定的映射导出另一个等价关系，可以把映射分解成两个“规格化”了的映射的合成。这种分解，在近世代数中具有基本重要的意义。
映射的导出关系
定义27：设 $f:X \to Y$ 。在 $X$ 上定义二元关系 $E_f$ 如下：$\forall a,b \in X$
$$\begin{aligned} aE_fb当且仅当f(a)=f(b) \tag{98}\end{aligned}$$称 $E_f$ 为由 $f$ 导出的关系。
命题7：设 $f:X \to Y$ ，由 $f$ 导出的关系 $E_f$ 是等价关系。
〔证明(命题7)〕由定义，$\forall a \in X,f(a)=f(a)$ ，所以 $aE_fa$ ，故 $E_f$ 是自反的。又若 $a,b \in X$ 且 $aE_fb$ ，则 $f(a)=f(b)$ ，从而 $f(b)=f(a)$ ，所以 $bE_fa$ ，故 $E_f$ 是对称的。如果 $aE_fb$ 且 $bE_fc$ ，则 $f(a)=f(b)$ 且 $f(b)=f(c)$ ，所以 $f(a)=f(c)$ 。于是 $aE_fc$ ，故 $E_f$ 是传递的。因此，$E_f$ 是 $X$ 上的等价关系。
证毕
定义28：由 $f$ 导出的等价关系常叫做 $f$ 的核。$f$ 的核常记为 $Ker(f)$ 。显然
$$\begin{aligned} X \backslash Ker(f) = \set{f^{-1}(y) | y \in Y,f^{-1}(y) \ne \varnothing} \tag{99}\end{aligned}$$自然映射
定义29：设 $\cong$ 是 $X$ 上的一个等价关系。$\gamma : X \to X \backslash \cong$ ，其定义为
$$\begin{aligned} \gamma(a) = [a] \tag{100}\end{aligned}$$其中 $[a]$ 为 $a$ 关于 $\cong$ 的等价类。映射 $\gamma$ 称为 $X$ 到商集 $X \backslash \cong$ 的自然映射。
由定义26可知 $X$ 到 $X \backslash \cong$ 的映射是满映射。
映射按等价关系分解
定理42：设 $f:X \to Y$ ，则 $f$ 可分解为 $X$ 到 $X \backslash Ker(f)$ 的自然映射 $\gamma$ 与 $X \backslash Ker(f)$ 到 $Y$ 的某个单射 $\bar{f}$ 的合成，即
$$\begin{aligned} f= \bar{f} \circ \gamma \tag{101}\end{aligned}$$ 〔证明(定理42)〕令 $\bar{f}:X \backslash Ker(f) \to Y$ ，$\bar{f}$ 的具体定义如下：$\forall A \in X \backslash Ker(f),\bar{f}(A)=f(a),a \in A$ 。即 $\forall a \in X,\bar{f}([a])=f(a)$ 。因为 $A$ 是一个等价类，所以 $\forall a,b \in A$ 均有 $f(a)=f(b)$ ，故 $\bar{f}(A)$ 与 $A$ 中的 $a$ 的选择无关，由 $A$ 唯一确定。所以，$\bar{f}$ 是 $X \backslash Ker(f)$ 到 $Y$ 的映射。其次，设 $A,B$ 是商集 $X \backslash Ker(f)$ 任两不等的元素，则 $A \cap B = \varnothing$ 。所以 $\forall a \in A$ 及 $\forall b \in B$ ，$f(a) \ne f(b)$ 。因此，$\bar{f}(A) \ne \bar{f}(B)$ ，故 $\bar{f}$ 是单射。
又 $\forall a \in X$
所以 $f = \bar{f} \circ \gamma$ 。
证毕
推论2： $\bar{f}$ 是一一对应的当且仅当 $f$ 是满射。
〔证明(推论2)〕由定理42可知 $f=\bar{f} \circ \gamma$ 。先证必要性，设 $\bar{f}$ 是一一对应。由定义29可知 $\gamma$ 是满射，因此由定理8可知 $\bar{f} \circ \gamma$ 是满射，即 $f$ 是满射。再证充分性，设 $f$ 是满射，则由定理9可知 $\bar{f}$ 是满射。
证毕
定理43：定理42中的单射 $\bar{f}$ 是唯一的。
〔证明(定理43)〕设还有 $\beta: X \backslash Ker(f) \to Y$ ，且能使得
$$\begin{aligned} f=\beta \circ \gamma \tag{103}\end{aligned}$$则 $\forall a \in X$
$$\begin{aligned} \beta \circ \gamma(a) = \beta(\gamma(a)) = f(a) = \bar{f}(\gamma(a)) \tag{104}\end{aligned}$$由于 $\gamma$ 是满射，所以 $\forall A \in X \backslash Ker(f)$ ，$\exists a \in X$ 使得 $\gamma(a) = A$ 。因此，$\beta(A)=\bar{f}(A)$ 。所以，$\bar{f}=\beta$ ，即 $\bar{f}$ 是唯一的。
证毕
定理42和定理43等价于说存在唯一的单射 $\bar{f}$ 使得图3为一个交换图。
图3
相容
定义30：设 $f:X \to Y$ ，$\cong$ 是 $X$ 上的一个等价关系。如果 $\forall a,b \in X$ ，只要 $a \cong b$ ，则必有 $f(a)=f(b)$ ，那么就说 $f$ 与 $\cong$ 相容。
设 $f:X \to Y$ ，$\cong$ 是 $X$ 上的等价关系，并且 $f$ 与 $\cong$ 相容，用 $[a]_{\cong}$ 表示 $X$ 的元素 $a$ 关于 $\cong$ 的等价类。$\bar{f}:X \backslash \cong \to Y$ ，其定义为 $\forall [a]_{\cong}$
$$\begin{aligned} \bar{f}([a]_{\cong})=f(a) \tag{105}\end{aligned}$$$\gamma$ 是 $X$ 到 $X \backslash \cong$ 的自然映射，则有
$$\begin{aligned} f = \bar{f} \circ \gamma \tag{106}\end{aligned}$$ 因为 $\forall a \in X,\bar{f} \circ \gamma(a) = \bar{f}(\gamma(a)) = \bar{f}([a]_{\cong}) = f(a)$ 。但这时的 $\bar{f}$ 可以不是单射了。$\bar{f}$ 是单射当且仅当 $\cong = Ker(f)$ 。
事实上，当 $\bar{f}$ 是单射时，若 $(a,b) \in Ker(f)$ ，则 $f(a)=f(b)$ ，从而 $\bar{f}([a]_{\cong})=\bar{f}([b]_{\cong})$ 。于是，$[a]_{\cong}=[b]_{\cong}$ 。所以 $a \cong b$ 。因此，$Ker(f) \sube \cong$ 。但 $f$ 与 $\cong$ 相容，由定义30得到若 $a \cong b$ ，则有 $f(a)=f(b)$ ，即 $(a,b) \in Ker(f)$ 。因此 $\cong \sube Ker(f)$ 。所以 $\cong = Ker(f)$ 。
偏序关系与偏序集
另一种极为重要的关系是序关系。它反映了事物之间的次序，在集合论中极为重要。当一个集合上引入了某种序关系后，我们就说该集有了序结构。序结构是数学的重要结构之一。最基本的序关系，是偏序关系。
序的定义
偏序关系的定义
定义31：集合 $X$ 上的二元关系 $R$ 称为偏序关系，如果 $R$ 同时满足以下三个性质：
1°. $R$ 是自反的，即 $\forall x \in X, xRx$ 。
2°. $R$ 是反对称的，即如果 $xRy,yRx$ ，则 $x=y$ 。
3°. $R$ 是传递的，即如果 $xRy,yRz$ ，则 $xRz$ 。
当抽象地讨论 $X$ 上的偏序关系时，常用符号“ $\le$ ”表示偏序关系。如果 $a \le b$ ，则读为“ $a$ 小于或等于 $b$ ”。当然，$\le$ 未必是数之间的小于或等于关系。
我们约定 $x \le y$ 且 $x \ne y$ 时,就记为 $x < y$ 。
注意,若 $\le$ 是 $X$ 上的偏序关系，则一般说来，只对 $X$ 中部分元间才有此关系。若 $\exists a,b \in X$ 使得 $a \nleq b$ 且 $b \nleq a$ ，则称 $a$ 与 $b$ 不可比较。如果 $x,y \in X$ ，$x \le y$ 或 $y \le x$ ，则称 $x$ 与 $y$ 可比较。
偏序集的定义
定义32（偏序集）：设 $\le$ 是 $X$ 上的一个偏序关系，则称二元组 $(X,\le)$ 为偏序集。
如果根据上下文，已经清楚地知道 $X$ 是对哪个偏序关系构成的偏序集时，那么就简单地说 $X$ 是一个偏序集。所应注意的是同一个集合 $X$ 上可以定义不同的偏序关系。 $X$ 对不同的偏序关系构成的偏序集，应是不同的偏序集。说“ $X$ 是一个偏序集”与说“ $X$ 是一个集合”在意义上是不同的。前者说明 $X$ 的元素间赋予了某种偏序关系，于是 $X$ 中具有某种“序结构”。而 $X$ 是一个集合，只不过是一组元素，无所谓结构，元素间更无次序。
全序关系与全序集的定义
定义33（全序集）：集合 $X$ 的偏序关系 $\le$ 叫做全序关系，如果 $\forall x,y \in X$ ，$x \le y$ 与 $y \le x$ 至少有一个成立。全序集关系也称为线性序关系。$X$ 与全序关系 $\le$ 构成的二元组 $(X,\le)$ 称为全序集。
拟序的定义
定义34：集合 $X$ 上的二元关系 $R$ 称为拟序关系，如果 $R$ 是反自反的和传递的。拟序关系通常记为 $<$ 。如果 $x < y$ ，则读作“ $x$ 小于 $y$ ”。
由于拟序关系是反自反和传递的,所以若 $x < y$ 且 $y < x$ ，则 $x < x$ ，这与反自反相矛盾。所以，在拟序关系中，$x < y$ 与 $y < x$ 不能都成立。因此，在此意义上，拟序是反对称的。
拟序关系 $<$ 与偏序关系 $\le$ 之间满足
$$\begin{aligned} \le = < \cup I_X 或 < = \le \backslash I_X \tag{107}\end{aligned}$$盖住关系与Hasse图
定义35：设 $X,\le$ 是一个偏序集。我们称 $y$ 盖住 $x$ ，如果 $x < y$ 且对每个 $z \in X$ ，若 $x \le z \le y$ ，则 $x=z$ 或 $y=z$ 。如果 $y$ 盖住 $x$ ，则记为 $x \stackrel{\propto}{\sub} y$ ，并且 $y$ 被称为 $x$ 的后继，而 $x$ 称为 $y$ 的前驱。
于是，盖住关系 $\stackrel{\propto}{\sub}$ 是 $X$ 上的关系。
偏序关系 $\le$ 是自反的，所以 $\le$ 的关系图中每个顶点都有一个环，显然可略去每个顶点的环。其次，由于偏序关系是传递的，那么只要在前驱与后继间联线即可。其次，由于反对称性，若 $x < y,x \ne y$ ，则点 $y$ 画在 $x$ 的上方，这样就不必用矢线了。按上述方法画出的图称为 $(X,\le)$ 的Hasse图。
实际上，$(X,\le)$ 的Hasse图就是 $\stackrel{\propto}{\sub}$ 的关系图。$\forall x,y \in X$ ，$x$ 与 $y$ 间有矢线从 $x$ 指向 $y$ 当且仅当 $y$ 盖住 $x$ 。若规定 $y$ 盖住 $x$ ，则 $y$ 画在 $x$ 的上方，那么得到的就是 $(X,\le)$ 的Hasse图。
特殊元素
上界与下界
定义36：设 $(X,\le)$ 是一个偏序集，$B \sube X$ 。如果存在一个元素 $a \in X$ 使得对 $B$ 中的每一元素 $x$ 有 $x \le a$ ，则称 $a$ 为 $B$ 的一个上界。如果存在一个元素 $b$ ，使得对 $B$ 的每一个元素 $x$ 有 $b \le x$ ，则称 $b$ 为 $B$ 的一个下界。
自然,偏序集 $X$ 的子集 $B$ 在 $X$ 中可能没有上界，如果有上界，则上界可能在 $B$ 中，也可能不在 $B$ 中。如果有上界，则上界未必是唯一的，有时甚至可能有无穷多个。对下界，也有类似的可能情况。
最大元素与最小元素
定义37：设 $(X,\le)$ 是一个偏序集，$B \sube X$ 。如果存在一个元素 $a \in B$ 使得 $\forall x \in B$ 有 $x \le a$ ，则称 $a$ 是 $B$ 中的最大元素。如果存在一个元素 $b \in B$ 使得 $\forall x \in B$ 有 $b \le x$ ，则称 $b$ 是 $B$ 中最小元素。
易见， $B$ 的最大元素是属于 $B$ 的上界。当然，偏序集 $(X,\le)$ 的子集 $B$ 中未必有最大元素，但 $B$ 若有最大元素，则最大元素必是唯一的。对最小元素，情况也类似。
应该注意的是，子集 $B$ 有上（下）界时，$B$ 未必有最大（小）元素。
在Hasse图中，只有 $B$ 中每两个元素之间都有线或通过线连接的情况下才存在最大元素或最小元素。其中最大元素就是 $B$ 的Hasse图中最顶端的元素，最小元素就是 $B$ 的Hasse图中最低端的元素。
上确界与下确界
定义38：设 $(X,\le)$ 是一个偏序集，$B \sube X$ 。如果 $B$ 有上界且 $B$ 的一切上界之集有最小元素，则这个最小上界称为 $B$ 的上确界，记为 $\sup B$ 。类似地，如果 $B$ 有下界且 $B$ 的一切下界之集有最大元素，则这个最大下界称为 $B$ 的下确界，记为 $\inf B$ 。
极大元素与极小元素
定义39：设 $(X,\le)$ 是一个偏序集，$A \sube X$ 。$A$ 中元素 $s$ 称为 $A$ 的极大元素，如果 $A$ 中没有元素 $l$ 使得 $l \ne s$ 且 $s \le l$ 。如果 $A$ 中有元素 $d$ ，使得 $\forall x \in A$ ，若 $x \ne d$ ，则 $x \nleq d$ ，那么 $d$ 被称为 $A$ 的极小元素。
在Hasse图中，$A$ 中每个链的最顶端元素都是极大元素。每个链的最底端元素都是极小元素。
链与反链
定义40：设 $(X,\le)$ 是一个偏序集，$A \sube X$ 。如果 $\forall a,b \in A$ ，$a \le b$ 与 $b \le a$ 必有一个成立，则称 $A$ 为 $X$ 的链。如果对 $A$ 中任两不同元素 $a$ 与 $b$ ，$a \le b$ 与 $b \le a$ 均不成立，则称 $A$ 为 $X$ 中的一个反链。$|A|$ 称为链（反链）的长度。
定理44：设 $(X,\le)$ 是一个偏序集。如 $X$ 中每个链的长至多为 $n$ ，则 $X$ 的全部元素能被分成 $n$ 个非空不相交反链之并。
〔证明(定理44)〕施归纳于 $n$ ：
当 $n=1$ 时，$X$ 中最长链的长度为 $1$ 。所以 $X$ 中任两不同元素不能比较。从而，$X$ 就是反链，故定理的结论成立。
假设当 $n=k \ge 1$ 时，定理成立。往证当 $n=k+1$ 时也成立。为此，设 $(X,\le)$ 中最长链的长度为 $k+1$ ，则 $X$ 中有极大元素。令 $M$ 为 $X$ 的所有极大元素之集，则 $M \ne \varnothing$ 且 $X \ne M$ （因为 $X$ 中存在长度大于 $1$ 的链）。考虑偏序集 $(X \backslash M,\le)$ 。则 $X \backslash M$ 中最长链的长度为 $k$ 。由归纳假设，$X \backslash M$ 可分解为 $k$ 个反链之并。由极大元素的定义，$M$ 也是个反链（否则若 $M$ 中有两个元素满足偏序关系，则这两个元素的后继必不是极大元素，这与 $M$ 的定义矛盾），所以 $X$ 可被分成 $k+1$ 个反链之并。
由数学归纳法原理，定理得证。
证毕
推论3：设 $(X,\le)$ 是一个偏序集，$|X|=mn+1$ ，则 $X$ 中或存在一个长至少为 $n+1$ 的链，或存在一个长至少为 $m+1$ 的反链。
〔证明(推论3)〕假设结果不成立，则 $X$ 中每个链长度小于等于 $n$ ，而且每个反链的长度小于等于 $m$ 。设 $X$ 中的最长链长度为 $k$ ，则 $k \le n$ 。由定理44，$X$ 能被分成 $k$ 个不相交反链之并。由假设每个反链之长小于等于 $m$ ，所以 $|X| \le km \le mn$ 。这与假设 $|X|=mn+1$ 相矛盾。因此结论成立。
证毕
良序集与数学归纳法
良序集
良序集的定义
定义41：如果一个全序集的每个非空子集总含有最小元素，则称这个全序集为良序集。
例1：自然数 $\N$ 对通常的“小于等于关系” $\le$ 构成的全序集 $(\N,\le)$ 是良序集。
例2：整数集 $\Z$ 对数的通常“小于等于关系” $\le$ 构成的全序集 $(Z,\le)$ 不是良序集。因为 $Z$ 作为本身的子集，就没有最小元素。
例3：设 $\Z$ 为整数集。将 $\Z$ 的元素排列如下：
$$\begin{aligned} 0,-1,1,-2,2,-3,3,\cdots,-n,n,\cdots \tag{108}\end{aligned}$$按上述序列定义 $\Z$ 上的二元关系 $\preccurlyeq:\forall m,n \in \Z$ ，$m \preccurlyeq n$ 当且仅当在(108)中不排在 $n$ 后。则 $\preccurlyeq$ 是 $\Z$ 上的全序关系，且全序集 $(Z,\preccurlyeq)$ 是良序集。
例4：所有负整数之集对通常的“小于等于关系”构成的全序集不是良序集。
例5：空集是良序集，因为空集作为一个全序集，它不包含任何非空子集。
例6：任何有限全序集是良序集。
命题8：良序集的任一子集是仍是良序集。
〔证明(命题8)〕设 $(L,\le)$ 是一个良序集，$M \sube L$ ，则 $(M,\le)$ 是一个全序集。对 $M$ 的任一子集 $A \ne \varnothing$ ，$A$ 也是 $L$ 的非空子集，所以 $A$ 有最小元素，它也是 $A$ 对 $(M,\le)$ 的最小元素。所以，$M$ 是良序集。
证毕
Zorn引理、Hausdorff极大原理和良序定理
定理45（Zorn引理）：若偏序集 $(A,\le)$ 的任一全序子集都有上界，则 $A$ 有极大元素。
定理46（Hausdorff极大原理）：任一偏序集 $(X,\le)$ 都有一条极大链。即存在一条链 $M$ ，$\forall x \in X$ ，$M \cup \set{x}$ 都不是链。
定理47（良序定理）：任何一个集合都可以良序化。
〔证明(Zorn引理,Hausdorff极大原理,良序定理)〕可以证明Zorn引理、Hausdorff极大原理、良序定理和选择公理等价，证明见[点此查看]。
证毕
数学归纳法
简单归纳法与强归纳法
数学归纳法是数学证明的一种标准证明方法，前面已经多次使用过。数学归纳法原理分为两种：简单归纳法原理和强归纳法原理。
原理1（简单归纳法）：假定 $S(n)$ 是关于自然数 $n$ 的某个命题，我们要证明 $S(n)$ 对一切自然数为真，只需
(1)证明 $S(0)$ 为真。
(2)证明若 $S(n),n \ge 0$ 为真，则 $S(n+1)$ 为真。
原理2（强归纳法）：假定 $S(n)$ 是关于自然数 $n$ 的某个命题，我们要证明 $S(n)$ 对一切自然数为真，只需
(1) 证明 $S(0)$ 为真。
(2) 证明若 $S(0),S(1),S(2),\cdots,S(n)$ 为真，则 $S(n+1)$ 为真。
实际上，数学归纳法可以从任意自然数 $n_0$ 开始归纳，只不过归纳的结果为 $S(n)$ 对一切 $\ge n_0$ 的自然数成立。
数学归纳法的性质
定理48：简单归纳法原理与强归纳法原理等价。
〔证明(定理48)〕设简单归纳法原理成立，往证强归纳法原理成立。为此，作命题 $Q(k)$ ：任给自然数 $k$ ，只有有穷个自然数满足
$$\begin{aligned} k_1 < k_2 < \cdots < k_j < k \tag{109}\end{aligned}$$注意这是命题 $Q(k)$ 的定义。显然 $Q(1)$ 成立。今设 $Q(n)$ 成立，往证 $Q(n+1)$ 也成立。注意没有自然数满足 $n < a < n+1$ ，因此，由 $Q(n)$ 为真得存在有穷个自然数满足
$$\begin{aligned} n_1 < n_2 < \cdots n_l < n \tag{110}\end{aligned}$$从而令 $n=n_{l+1}$ 。于是，得
$$\begin{aligned} n_1 < n_2 < \cdots < n_{l+1} < n+1 \tag{111}\end{aligned}$$ 因此 $Q(n+1)$ 也成立。由简单归纳法原理得 $\forall n \in \N$ ，$Q(n)$ 真。
假如强归纳法原理不成立，则若 $P(n)$ 为关于自然数 $n$ 的一个命题，$P(1)$ 为真且对任给自然数 $n$ ，如果 $\forall k < n,k \in \N$ ，$P(k)$ 为真，则 $P(n)$ 为真，但不是对所有 $P(m)$ ，$P(m)$ 真。于是，$\exists n' \in \N$ 使之 $P(n')$ 为假。假如对 $\forall k < n',k \in \N$ ，$P(k)$ 真，则由强归纳法的条件可知 $P(n')$ 为真，这与 $P(n')$ 为假矛盾。而若 $\forall k < n',k \in \N$ ，$P(k)$ 不都为真，由简单归纳法推出来的命题 $Q$ 可知只有有穷个自然数小于 $n'$ 。因此可设所有小于 $n'$ 且使 $P(m)$ 不真的 $m$ 为
显然 $n_1 > 1$ ，因为由强归纳法的条件知 $P(1)$ 为真。于是对于 $\forall k < n,k \in \N$ 可得 $P(k)$ 为真。再由强归纳法的条件知 $P(n_1)$ 为真。这与 $P(n_1)$ 为假相矛盾。因此强归纳法原理成立。
反过来，设强归纳法成立，则简单归纳法成立。实际上，简单归纳法的条件是蕴含强归纳法的条件的。即若 $S(n),n \ge 0$ 为真，则 $S(n+1)$ 为真实际上可以推出若 $S(0),S(1),S(2),\cdots,S(n)$ 为真，则 $S(n+1)$ 为真（前者是后者的一个特殊情况）。所以，某一命题在满足简单归纳法的条件的情况下，也满足强归纳法的条件，而由强归纳法成立可以知该命题成立，所以任一命题在满足简单归纳法条件的时候也能推出该命题成立。这其实就是著名的三段论推理法，其中大前提是简单归纳法条件成立则强归纳法条件成立，小前提是强归纳法条件成立则命题成立，所以，简单归纳法条件成立则命题成立。
证毕
定理49：简单归纳法原理与自然数集 $\N$ 对通常的“小于等于关系” $\le$ 构成良序集等价。
〔证明(定理49)〕假设简单归纳法原理成立，往证 $(N,\le)$ 是一个良序集，即要证 $\N$ 的任一非空子集 $A$ 有最小元素。用反证法，假设 $A$ 没有最小元素。那么 $\forall a \in A$ ，$\exists b \in A$ 且 $b < a$ 。设命题 $P(n)$ ：$n$ 不在 $A$ 中。显然，$P(0)$ 为真，因为若 $0$ 在 $A$ 中而 $0$ 是最小的自然数，所以 $A$ 的最小元就是 $0$ 。现假设对所有的 $0 \le k < n,k \in \N$ ，$P(k)$ 成立。若 $n \in A$ ，则根据 $A$ 没有最小元的假设，存在 $m < n$ 且 $m \in A$ ，而又根据 $0 \le k < n,k \in \N$ ，$P(k)$ 成立的假设可知 $P(m)$ 成立，即 $m \notin A$ ，这产生矛盾。所以 $n \notin A$ ，即 $P(n)$ 成立。由定理48可知简单归纳法和强归纳法等价，所以由强归纳法可得 $P(n)$ 对于 $n \in \N$ 都成立。而 $A \sube \N$ ，因此，$A$ 中没有元素，与 $A$ 是 $\N$ 的非空子集矛盾。所以 $A$ 总有最小元素，因此 $(\N,\le)$ 是良序集。
现在假设已知 $(\N,\le)$ 是良序集，往证简单归纳法原理成立。为此，用反证法，即假定简单归纳法原理不成立。于是，必有一个关于自然数 $n$ 的命题 $P(n)$ ， $P(0)$ 成立且若 $P(n)$ 成立，$P(n+1)$ 也成立。但并不是对所有 $m \in \N$ ，$P(m)$ 为真。于是，有一自然数 $n' \in \N$ 使 $P(n')$ 为假。令 $A$ 为使 $P(m)$ 为假的那些自然数之集，则 $A$ 非空。由于 $(N,\le)$ 是良序集，所以 $A$ 中有最小自然数 $n_1$ 。由 $P(0)$ 为真, 得 $n_1 > 0$ ，从而 $n_1 - 1 \ge 0$ 。于是，$P(n_1 - 1)$ 真。而 $n_1-1 < n_1$ ，由假设可得 $P(n_1-1)$ 真，则有 $P(n_1-1+1)=P(n_1)$ 真。这与关于 $n_1$ 的假设相矛盾，故简单归纳法原理成立。
证毕
我的一生中只有一个盛大的夏天，那个夏天之后月亮就陨落了。我用以后的每个夏天去临摹那轮月亮，我嫉妒它的仅有，又爱慕它的温柔。
― Hermann Hesse, 《克林索尔的最后夏天》