离散数学（四）—

离散数学（四）——关系

一、关系的基本概念

1.有序对与笛卡尔积

以往我们总是见到“一个点处在平面 $𝑅 \times 𝑅$ 上”之类的表述，粗略地理解为一个由两个垂直的实数轴张成的平面。笛卡尔积实际是生成一个以有序对作为元素的集合，放到平面几何中来说，上述的粗略理解倒也正确。

定义 1.（有序对）

有序对由两个元素 $𝑎, 𝑏$ 构成，记成 $⟨ 𝑎, 𝑏 ⟩$ 。与集合的无序性不同，尖括号内元素的次序会影响结果。准确地说：

𝑎 \neq 𝑏 \leftrightarrow ⟨ 𝑎, 𝑏 ⟩ \neq ⟨ 𝑏, 𝑎 ⟩

注 1.（有序对的另一种记法）

有序对也可以用圆括号书写，比如

(𝑎, 𝑏)

，这就是通常见到的“坐标”形式。

而两个集合 $𝐴, 𝐵$ 间的笛卡尔积记成 $𝐴 \times 𝐵$ ，定义为：

𝐴 \times 𝐵 = {⟨ 𝑎, 𝑏 ⟩ | 𝑎 \in 𝐴 \land 𝑏 \in 𝐵}

显然在大多数情况下 $𝐴 \times 𝐵 \neq 𝐵 \times 𝐴$ 。笛卡尔积既不满足交换律也不满足结合律。但是，笛卡尔积与集合并有分配律：

𝐴 \times (𝐵 \cup 𝐶) = (𝐴 \times 𝐵) \cup (𝐴 \times 𝐶)

(𝐵 \cup 𝐶) \times 𝐴 = (𝐵 \times 𝐴) \cup (𝐶 \times 𝐴)

2.关系

一个关系我们通常用大写字母 $𝑅$ 来表示，它亦是一种集合，取的是两个集合的笛卡尔积的子集，即 $𝑅 \subseteq 𝐴 \times 𝐵$ 。如果 $𝐴 = 𝐵$ ，那么我们称 $𝑅$ 是集合 $𝐴$ 上的关系。

对于 $𝐴 \times 𝐵$ 中的元素 $⟨ 𝑎, 𝑏 ⟩$ ，如果它是 $𝑅$ 中的元素，那么就称 $𝑎$ 和 $𝑏$ 具有关系 $𝑅$ ，可以记为 $𝑎 𝑅 𝑏$ 。可以结合比较常见的关系——比如实数域上的相等 $=$ ——来理解。而从“相等”这个概念出发，我们引申出恒等关系，这种关系只存在于一个集合 $𝐴$ 及其自身的笛卡尔积 $𝐴 \times 𝐴$ 中，记作 $Δ_{𝐴}$ ：

Δ_{𝐴} = {⟨ 𝑎, 𝑎 ⟩ | 𝑎 \in 𝐴}

关系除了可以用集合的表示方法来表示之外，在元素较少的情况下也可以用有向图来表示。例如，有序对 $⟨ 3, 4 ⟩$ 在图中表示为顶点 $3$ 指向顶点 $4$ 的一条有向边。当然我们也能用更加“数学化”的关系矩阵来描述。假设集合 $𝐴 = {𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛}}, 𝐵 = {𝑏_{1}, 𝑏_{2}, \dots, 𝑏_{𝑘}}$ ，而它们有一个关系 $𝑅 \subseteq 𝐴 \times 𝐵$ ，由此唯一确定一个 $𝑛 \times 𝑘$ 的布尔矩阵 $𝑴_{𝑅}$ 。记这个矩阵第 $𝑖$ 行 $𝑗$ 列的元素为 $𝑚_{𝑖 𝑗}$ ，那么若 $𝑎_{𝑖}$ 与 $𝑏_{𝑗}$ 具有关系 $𝑅$ ，则 $𝑚_{𝑖 𝑗} = 1$ ，否则 $𝑚_{𝑖 𝑗} = 0$ 。

例如，恒等关系只是一个集合上的关系，因此恒等关系的关系矩阵必然是一个方阵；而恒等关系中都是自己对自己的关系，因此恒等关系矩阵的对角线上都是 $1$ 、其余都为 $0$ ，也即是一个单位矩阵。

二、关系的基本运算

1.逆关系

所谓的逆关系，就是将关系 $𝑅$ 中的每一个元素 $⟨ 𝑎, 𝑏 ⟩$ 都替换为 $⟨ 𝑏, 𝑎 ⟩$ ，记为 $𝑅^{- 1}$ ，即：

𝑅^{- 1} = {⟨ 𝑏, 𝑎 ⟩ | ⟨ 𝑎, 𝑏 ⟩ \in 𝑅}

显然，对一个关系逆运算两次可以回到自身，即 ${(𝑅^{- 1})}^{- 1} = 𝑅$ 。

并且，逆运算保持子集关系，即假设关系 $𝑅, 𝑆 \subseteq 𝐴 \times 𝐵$ ，若 $𝑅 \subseteq 𝑆$ ，则 $𝑅^{- 1} \subseteq 𝑆^{- 1}$ 。

另外，逆运算与集合的交或并是可交换的：

{(𝑅 \cup 𝑆)}^{- 1} = 𝑅^{- 1} \cup 𝑆^{- 1}

{(𝑅 \cap 𝑆)}^{- 1} = 𝑅^{- 1} \cap 𝑆^{- 1}

>所谓可交换性，是指两种运算间，不论先做哪种运算，最后得到的结果都相同。

2.复合

假设两个关系 $𝑅 \subseteq 𝐴 \times 𝐵, 𝑆 \subseteq 𝐵 \times 𝐶$ ，显然我们能通过 $𝑅, 𝑆$ 得到一个新的关系使其是 $𝐴$ 到 $𝐶$ 的关系、剔除掉中间的集合 $𝐵$ 。称这种运算为复合，记为 $𝑆 ⚬ 𝑅$ ：

𝑆 ⚬ 𝑅 = {⟨ 𝑎, 𝑐 ⟩ | \exists 𝑏 \in 𝐵 (⟨ 𝑎, 𝑏 ⟩ \in 𝑅 \land ⟨ 𝑏, 𝑐 ⟩ \in 𝑆)}

>按照常规的思维来说，既然是取 $𝑅$ 的第一个元素、 $𝑆$ 的第二个元素，应该记作 $𝑅 ⚬ 𝑆$ 才对。因此请注意这里关系复合的记法与常规思维的不同。

关系复合不满足交换律，但满足结合律，即 $𝑇 ⚬ (𝑆 ⚬ 𝑅) = (𝑇 ⚬ 𝑆) ⚬ 𝑅$ 。

关系复合还保持子集关系。假设有四个关系 $𝑅, 𝑆, 𝑈, 𝑊$ ，且 $𝑅 \subseteq 𝑆, 𝑈 \subseteq 𝑊$ ，那么 $𝑈 ⚬ 𝑅 \subseteq 𝑊 ⚬ 𝑆$ 。

同时，如果 $𝑅 \subseteq 𝐴 \times 𝐵$ ，那么 $Δ_{𝐵} ⚬ 𝑅 = 𝑅 = 𝑅 ⚬ Δ_{𝐴}$ 。另外：

{(𝑆 ⚬ 𝑅)}^{- 1} = 𝑅^{- 1} ⚬ 𝑆^{- 1}

{\begin{cases} 𝑇 ⚬ (𝑅 \cup 𝑆) = (𝑇 ⚬ 𝑅) \cup (𝑇 ⚬ 𝑆) \\ (𝑅 \cup 𝑆) ⚬ 𝑇 = (𝑅 ⚬ 𝑇) \cup (𝑆 ⚬ 𝑇) \end{cases}

{\begin{cases} 𝑇 ⚬ (𝑅 \cap 𝑆) \subseteq 𝑇 ⚬ 𝑅 \\ 𝑇 ⚬ (𝑅 \cap 𝑆) \subseteq 𝑇 ⚬ 𝑆 \\ (𝑅 \cap 𝑆) ⚬ 𝑇 \subseteq 𝑅 ⚬ 𝑇 \\ (𝑅 \cap 𝑆) ⚬ 𝑇 \subseteq 𝑆 ⚬ 𝑇 \end{cases} ⟹

⟹ {\begin{cases} 𝑇 ⚬ (𝑅 \cap 𝑆) \subseteq (𝑇 ⚬ 𝑅) \cap (𝑇 ⚬ 𝑆) \\ (𝑅 \cap 𝑆) ⚬ 𝑇 \subseteq (𝑅 ⚬ 𝑇) \cap (𝑆 ⚬ 𝑇) \end{cases}

3.用关系矩阵表示关系的运算

假设有两个关系 $𝑅, 𝑆$ ，分别对应关系矩阵 $𝑴_{𝑅}, 𝑴_{𝑆}$ ，这两个矩阵中的元素分别记为 $𝑟_{𝑖 𝑗}, 𝑠_{𝑖 𝑗}$ 。

(1) $𝑅 \cup 𝑆$

只需将两个关系矩阵做逻辑或运算即可，即 $𝑴_{𝑅 \cup 𝑆} = 𝑴_{𝑅} \lor 𝑴_{𝑆} = [𝑟_{𝑖 𝑗} \lor 𝑠_{𝑖 𝑗}]$ ，即将两个矩阵对应位置的元素作或运算即可。

(2) $𝑅 \cap 𝑆$

只需将两个关系矩阵做逻辑与运算即可，即 $𝑴_{𝑅 \cap 𝑆} = 𝑴_{𝑅} \land 𝑴_{𝑆} = [𝑟_{𝑖 𝑗} \land 𝑠_{𝑖 𝑗}]$ ，即将两个矩阵对应位置的元素作与运算即可。

(3) $𝑅 - 𝑆$

$𝑅 - 𝑆$ 的关系矩阵使用特殊的减法运算： $𝑴_{𝑅 - 𝑆} = 𝑴_{𝑅} ⊖ 𝑴_{𝑆} = [𝑟_{𝑖 𝑗} ⊖ 𝑠_{𝑖 𝑗}]$ ，这个减法定义为只有 $1$ 减去 $0$ 才等于 $1$ 。即：

0 ⊖ 0 = 0, 0 ⊖ 1 = 0, 1 ⊖ 1 = 0, 1 ⊖ 0 = 1

(4) $𝑅^{- 1}$

逆关系的关系矩阵就是原关系矩阵的转置，即 $𝑴_{𝑅^{- 1}} = 𝑴_{𝑅}^{𝑇} = [𝑟_{𝑗 𝑖}]$ 。

(5) $𝑆 ⚬ 𝑅$

关系复合是将两个矩阵作逻辑积运算： $𝑴_{𝑆 ⚬ 𝑅} = 𝑴_{𝑅} 𝑜 \cdot 𝑴_{𝑆}$ 。所谓矩阵逻辑积，实际就是普通的矩阵乘法，但是将数乘换做逻辑与、加和换做逻辑或。

三、关系的性质

接下来我们总假设关系 $𝑅$ 是一个集合 $𝐴$ 上的关系，即 $𝑅 \subseteq 𝐴 \times 𝐴$ 。

1.自反性

如果对于任意 $𝑎 \in 𝐴$ ，都存在 $⟨ 𝑎, 𝑎 ⟩ \in 𝑅$ ，那么就说 $𝑅$ 是自反的。反之，如果都不存在 $⟨ 𝑎, 𝑎 ⟩ \in 𝑅$ ，则说是反自反的。

我们发现上述定义是针对 $𝐴$ 中的全体元素说的，因此自反性和反自反性都是非常严格的定义。一个关系是自反的那么必不反自反，如果反自反则必不自反，也就是自反性和反自反性是互斥的(除非 $𝐴$ 是空集！)。但是由于这两种性质非常严格，一个关系可以既不自反也不反自反。

实数域上常见的自反关系显然有相等，以及带有“相等”的大于等于、小于等于，这些符号两边的数字相等则式子为真；常见的反自反关系有大于和小于，符号两边的数字相等则式子不成立。

显然，自反与反自反与恒等关系间存在联系。若一个关系是自反的，那么恒等关系必是它的子集，即 $Δ_{𝐴} \subseteq 𝑅$ ；如果一个关系是反自反的，那么恒等关系与这个关系没有交集，即 $Δ_{𝐴} \cap 𝑅 = ⌀$ 。

当我们用关系矩阵来表示这个关系的时候，如果其对角线上都是 $1$ ，那么这是一个自反关系；如果都是 $0$ ，则是一个反自反关系。否则既不自反也不反自反。

2.对称性

现在讨论全体的 $⟨ 𝑎, 𝑏 ⟩ \in 𝑅$ 。如果 $⟨ 𝑏, 𝑎 ⟩$ 也属于 $𝑅$ ，那么称 $𝑅$ 是对称的；而在 $𝑎 \neq 𝑏$ 的情况下，如果 $⟨ 𝑏, 𝑎 ⟩$ 都属于 $𝑅$ ，那么称 $𝑅$ 是反对称的。更加公理化的定义是：

定义 2.（对称性与反对称性）

𝑅 是对称的 当且仅当 \forall 𝑎 \in 𝐴 \forall 𝑏 \in 𝐴 (⟨ 𝑎, 𝑏 ⟩ \in 𝑅 \to ⟨ 𝑏, 𝑎 ⟩ \in 𝑅)

𝑅 是反对称的 当且仅当 \forall 𝑎 \in 𝐴 \forall 𝑏 \in 𝐴 (⟨ 𝑎, 𝑏 ⟩ \in 𝑅 \land ⟨ 𝑏, 𝑎 ⟩ \in 𝑅 \to 𝑎 = 𝑏)

当然从关系矩阵的角度来看对称性和反对称性更加直观。对于对称性，上述定义要求对称关系的关系矩阵是一个对称矩阵，即关于对角线对称，即转置矩阵与原矩阵相等 $𝑴_{𝑅} = 𝑴_{𝑅}^{𝑇}$ ；而对于反对称性，则是要求非对角线上两个对称的元素 $𝑟_{𝑖 𝑗}$ 和 $𝑟_{𝑗 𝑖}$ 都不能同时为 $1$ 。注意到 $𝑎 \neq 𝑏$ ，这是让我们不用关心对角线元素，也就是说自反性不影响反对称性。

从集合的角度而言，如果 $𝑅 = 𝑅^{- 1}$ 则关系是对称的，这对应上述的转置矩阵与原矩阵相等；而如果关系与其逆关系的交集是恒等关系的子集，即 $𝑅 \cap 𝑅^{- 1} \subseteq Δ_{𝐴}$ ，即可判定它是反对称的。

对称性和反对称性也是非常严格的，两者互斥(除非 $𝐴$ 是空集！)，但是一个关系可以既不对称也不反对称。实数域上的典型对称关系是相等和不相等，而其他的大于、大于等于等都是反对称关系。

3.传递性

传递性比较类似于关系与其自身的复合。如果对于任意 $⟨ 𝑎, 𝑏 ⟩, ⟨ 𝑏, 𝑐 ⟩ \in 𝑅$ ，都有 $⟨ 𝑎, 𝑐 ⟩ \in 𝑅$ ，那么称关系 $𝑅$ 是传递的。更加公理化的定义是：

定义 3.（传递性）

𝑅 是传递的 当且仅当 \forall 𝑎 \in 𝐴 \forall 𝑏 \in 𝐴 \forall 𝑐 \in 𝐴 (⟨ 𝑎, 𝑏 ⟩ \in 𝑅 \land ⟨ 𝑏, 𝑐 ⟩ \in 𝑅 \to ⟨ 𝑎, 𝑐 ⟩ \in 𝑅)

关系矩阵不能直观反映关系是否具有传递性。为了更简单地判定关系的传递性，我们通常计算关系与其自身的复合 $𝑅 ⚬ 𝑅$ 。如果 $𝑅 ⚬ 𝑅 \subseteq 𝑅$ ，那么关系就是传递的；否则不是传递的。

实数域上的大部分关系都是传递的，比如相等、大于(等于)等。

4.关系性质的性质概括法定义

上述中，从集合角度来考察关系性质的，就是性质概括法，可以利用之来验证关系性质。现总结罗列如下：

(1) $𝑅$ 具有自反性： $Δ_{𝐴} \subseteq 𝑅$
(2) $𝑅$ 具有反自反性： $Δ_{𝐴} \cap 𝑅 = ⌀$
(3) $𝑅$ 具有对称性： $𝑅 = 𝑅^{- 1}$
(4) $𝑅$ 具有反对称性： $𝑅 \cap 𝑅^{- 1} \subseteq Δ_{𝐴}$
(5) $𝑅$ 具有传递性： $𝑅 ⚬ 𝑅 \subseteq 𝑅$

5.关系运算与关系性质

首先给出下表：

表 1 关系运算与关系性质表

运算	自反性	反自反性	对称性	反对称性	传递性
$𝑅^{- 1}$	$✓$	$✓$	$✓$	$✓$	$✓$
$𝑅 \cap 𝑆$	$✓$	$✓$	$✓$	$✓$	$✓$
$𝑅 \cup 𝑆$	$✓$	$✓$	$✓$	$\times$	$\times$
$𝑅 - 𝑆$	$\times$	$✓$	$✓$	$✓$	$\times$
$𝑅 ⚬ 𝑆$	$✓$	$\times$	$\times$	$\times$	$\times$

现在解释上表的含义。这张表描述的是，如果给出的两个(或一个)关系都具有某种性质的话，那么运算结果是否还有这种性质。比如，如果 $𝑅, 𝑆$ 都对称，那么 $𝑅 \cup 𝑆$ 也对称；如果 $𝑅, 𝑆$ 都自反，那么 $𝑅 - 𝑆$ 不一定自反。

四、关系的闭包

还是假定关系 $𝑅$ 是一个集合 $𝐴$ 上的关系，即 $𝑅 \subseteq 𝐴 \times 𝐴$ 。这个关系可能不自反、或者不对称、或者不传递，但我们可以通过一些手段扩展这个关系(也就是添加一些有序对元素)、并且只添加最少量的元素，使之成为一个自反或对称或传递的关系。这个新生成的关系称为闭包。

1.自反闭包

正如上述，自反闭包是在原关系的基础上，以最小的扩展生成自反关系。 $𝑅$ 的自反闭包记为 $𝑟 (𝑅)$ ，这是取 $reflexive$ 的首字母。由于只要恒等关系是关系的子集那么关系就是自反的，因此 $𝑟 (𝑅) = 𝑅 \cup Δ_{𝐴}$ 。

定义 4.（自反闭包

𝑟 (𝑅)

）

自反闭包是原关系的扩展，即原关系是自反闭包的子集： $𝑅 \subseteq 𝑟 (𝑅)$ ；
自反闭包是自反关系： $Δ_{𝐴} \subseteq 𝑟 (𝑅)$ ；
对于任意包含原关系的自反关系 $𝑆$ ，自反闭包亦是它的子集： $𝑅 \subseteq 𝑆 \to 𝑟 (𝑅) \subseteq 𝑆$ 。

自反闭包可以证明一个关系是自反的，只要一个关系的自反闭包等于它自己。也就是若 $𝑟 (𝑅) = 𝑅$ 则 $𝑅$ 自反，反之亦然。

自反闭包保持子集关系，即若 $𝑅 \subseteq 𝑆$ ，那么 $𝑟 (𝑅) \subseteq 𝑟 (𝑆)$ 。

自反闭包与集合的交与并是可交换的，即：

𝑟 (𝑅 \cap 𝑆) = 𝑟 (𝑅) \cap 𝑟 (𝑆)

𝑟 (𝑅 \cup 𝑆) = 𝑟 (𝑅) \cup 𝑟 (𝑆)

2.对称闭包

$𝑅$ 的对称闭包记为 $𝑠 (𝑅)$ ，这是取 $symmetric$ 的首字母。为了以最小的扩展生成对称关系，只需要将关系遍历一遍，添加原本没有的对称有序对即可，即 $𝑠 (𝑅) = 𝑅 \cup 𝑅^{- 1}$ 。

定义 5.（对称闭包

𝑠 (𝑅)

）

对称闭包是原关系的扩展，即原关系是对称闭包的子集： $𝑅 \subseteq 𝑠 (𝑅)$ ；
对称闭包是对称关系： $𝑠 (𝑅) = {(𝑠 (𝑅))}^{- 1}$ ；
对于任意包含原关系的对称关系 $𝑆$ ，对称闭包亦是它的子集： $𝑅 \subseteq 𝑆 \to 𝑠 (𝑅) \subseteq 𝑆$ 。

对称闭包可以证明一个关系是对称的，只要一个关系的对称闭包等于它自己。也就是若 $𝑠 (𝑅) = 𝑅$ 则 $𝑅$ 对称，反之亦然。

对称闭包保持子集关系，即若 $𝑅 \subseteq 𝑆$ ，那么 $𝑠 (𝑅) \subseteq 𝑠 (𝑆)$ 。

自反闭包与集合并是可交换的，但与集合交不是，即：

𝑠 (𝑅 \cap 𝑆) \subseteq 𝑠 (𝑅) \cap 𝑠 (𝑆)

𝑠 (𝑅 \cup 𝑆) = 𝑠 (𝑅) \cup 𝑠 (𝑆)

3.传递闭包

$𝑅$ 的传递闭包记为 $𝑡 (𝑅)$ ，这是取 $transitive$ 的首字母。

定义 6.（传递闭包

𝑡 (𝑅)

）

传递闭包是原关系的扩展，即原关系是传递闭包的子集： $𝑅 \subseteq 𝑡 (𝑅)$ ；
传递闭包是传递关系： $𝑡 (𝑅) ⚬ 𝑡 (𝑅) \subseteq 𝑡 (𝑅)$ ；
对于任意包含原关系的传递关系 $𝑆$ ，传递闭包亦是它的子集： $𝑅 \subseteq 𝑆 \to 𝑡 (𝑅) \subseteq 𝑆$ 。

传递闭包可以证明一个关系是传递的，只要一个关系的传递闭包等于它自己。也就是若 $𝑡 (𝑅) = 𝑅$ 则 $𝑅$ 传递，反之亦然。

传递闭包保持子集关系，即若 $𝑅 \subseteq 𝑆$ ，那么 $𝑡 (𝑅) \subseteq 𝑡 (𝑆)$ 。

传递闭包与集合的交并只有子集的关系：

𝑡 (𝑅 \cap 𝑆) \subseteq 𝑡 (𝑅) \cap 𝑡 (𝑆)

𝑡 (𝑅) \cup 𝑡 (𝑆) \subseteq 𝑡 (𝑅 \cup 𝑆)

注意到到这里为止我们还没讲如何从原关系生成传递闭包。为此，我们需要先引入关系的幂。关系的 $𝑛$ 次幂，记作 $𝑅^{𝑛}$ ，是关系与自己的 $𝑛$ 次复合。例如， $𝑅^{3} = 𝑅 ⚬ 𝑅 ⚬ 𝑅$ 。

从关系矩阵的角度来说，取 $𝑅^{𝑛}$ 的关系矩阵中的某一个元素 $𝑚_{𝑖 𝑗}$ 。若 $𝑚_{𝑖 𝑗} = 1$ ，那么这说明元素 $𝑖$ 到 $𝑗$ 之间具有一条长度为 $𝑛$ 的通路。例如，原关系的关系矩阵就是在描述哪些元素间具有直接通路，也就是长度为 $1$ 的通路。

在一个传递的关系中，若两个元素间具有一条长度大于等于 $2$ 的通路，那么这两个元素间就应当有一条直接通路。因此，我们每计算一次 $𝑅^{𝑛}$ ，就是在寻找任意两个元素间的 $𝑛$ 通路，当我们从 $1$ 遍历到正无穷的时候，就相当于找到了所有长度的通路。这样，只要在“有通路”的两个元素间建立一条直接通路，我们就生成了原关系的传递闭包：

𝑡 (𝑅) = ⋃_{𝑛 = 1}^{+ \infty} 𝑅^{𝑛} = 𝑅^{*}

$𝑅^{*}$ 是中间的关系广义并的简记。然而实际上我们不可能一直计算到无穷大。假设 $𝐴$ 中有 $𝑛$ 个元素。如果一条通路长度大于 $𝑛$ 、那么这条通路必然会经过重复的顶点(鸽笼原理)，因此这条通路已经是至少两条长度小于 $𝑛$ 的通路的相连了。也就是说，我们只需计算到 $𝑅^{𝑛}$ 即可结束：

𝑡 (𝑅) = ⋃_{𝑘 = 1}^{𝑛} 𝑅^{𝑘}

4.Warshall算法

Warshall算法实际就是图论中的Floyd算法。这个算法是利用递推式，从 $𝑾_{0} = 𝑴_{𝑅}$ 开始，计算到 $𝑾_{𝑛}$ 为止。 $𝑾_{𝑛}$ 本身就是传递闭包结果，这省略了求广义并的过程。

记 $𝑤_{𝑖 𝑗}^{𝑘}$ 为矩阵 $𝑾_{𝑘}$ 的第 $𝑖$ 行 $𝑗$ 列元素。第 $𝑘$ 个矩阵由上一个矩阵，也就是第 $𝑘 - 1$ 个矩阵完全确定。递推式是：

𝑤_{𝑖 𝑗}^{𝑘} = 𝑤_{𝑖 𝑗}^{𝑘 - 1} \lor (𝑤_{𝑖 𝑘}^{𝑘 - 1} \land 𝑤_{𝑘 𝑗}^{𝑘 - 1})

五、等价关系

等价关系是一个非常严格的关系。如果一个关系同时是自反关系、对称关系、传递关系，那么称它为等价关系。实数域上的典型等价关系就是相等。

接下来假定等价关系 $𝑅 \subseteq 𝐴 \times 𝐴$ 。

1.等价类

等价类是一个集合，它的元素来源于集合 $𝐴$ ，也就是说它的元素不是有序对。等价类必须基于集合 $𝐴$ 中的某个元素，例如 $𝑎$ ，将所有与 $𝑎$ 等价的元素囊括进来，就形成了 $𝑎$ (所在等价关系上)的等价类，记为 ${[𝑎]}_{𝑅}$ 。也就是：

{[𝑎]}_{𝑅} = {𝑥 \in 𝐴) ⟨ 𝑎, 𝑥 ⟩ \in 𝑅}

由于自反性，等价类中必然至少有一个元素，因此等价类不可能是空集：

{[𝑎]}_{𝑅} \neq ⌀

2.代表

既然等价类内的任意一个元素都是等价的，那么取任一个元素它都能“代表”这个等价类。也就是说，只要 $𝑏 \in {[𝑎]}_{𝑅}$ ，那么 $𝑏$ 就是这个等价类的一个代表。当然 $𝑎$ 本身也是这个等价类的代表。

任取集合 $𝐴$ 中的两个元素 $𝑎, 𝑏$ ，它们之间要么等价要么不等价，因此它们代表的等价类要么相等要么没有交集，也就是：

{[𝑎]}_{𝑅} = {[𝑏]}_{𝑅} 或 {[𝑎]}_{𝑅} \cap {[𝑏]}_{𝑅} = ⌀

必居其中之一。

3.商集

商集是一个集合族，它是以等价类作为划分依据的等价关系的划分。 ¹¹ 复习：将一个集合 $𝐴$ 划分为几个互不相交的部分，每个部分自成一个集合，那么这些集合就可以形成一个集合族，称为 $𝐴$ 的划分，记为 $ℱ︀$ 。划分中的每一个集合称为一个划分块。

也就是每一个等价类都是一个划分块。 $𝐴$ 中所有元素的等价类构成的集合族，称为集合 $𝐴$ 关于等价关系 $𝑅$ 的商集，记为 $𝐴 / 𝑅$ ：

𝐴 / 𝑅 = {{[𝑎]}_{𝑅} | 𝑎 \in 𝐴}

商集作为集合 $𝐴$ 的划分，显然其广义并就是集合 $𝐴$ ：

⋃_{𝑎 \in 𝐴} {[𝑎]}_{𝑅} = ⋃ 𝐴 / 𝑅 = 𝐴

六、偏序关系

如果一个关系自反、反对称、传递，那么称它为偏序关系，也简称为偏序，此时我们可以用一个类似小于等于的符号 $⪯$ 来表示它。

在此基础上，如果它是反自反的，那么称之为严格序关系。事实上，如果一个关系既反自反又传递，那么它必是一个反对称关系。

如果一个关系自反且传递、但不反对称，那么称它为拟序关系。

接下来我们着重于偏序关系 $𝑅 \subseteq 𝐴 \times 𝐴$ ，或者写成 $⪯ \subseteq 𝐴 \times 𝐴$ ：

1.偏序集与比较

偏序集需要包含偏序关系、以及偏序关系所处在的集合，记为 $(𝐴, ⪯)$ 。注意到反对称性只要求两个元素 $𝑎, 𝑏$ 的有序对 $⟨ 𝑎, 𝑏 ⟩, ⟨ 𝑏, 𝑎 ⟩$ 不同时存在，也即允许两者都不存在，此时既不存在 $𝑎 ⪯ 𝑏$ 也不存在 $𝑏 ⪯ 𝑎$ ，则称 $𝑎, 𝑏$ 间不可比。反之，称为可比的。当 $𝐴$ 中任意两个元素都可比，那么称偏序集 $(𝐴, ⪯)$ 是全序的，或称为线序的。

注 2.（偏序关系的反对称性）

需要注意在偏序关系中，

𝑎 \neq 𝑏

不代表

𝑎 ⪯ 𝑏

且

𝑎 ⪰ 𝑏

，因为偏序关系是反对称的！

𝑎 \neq 𝑏

仅仅是强调“

𝑎

和

𝑏

不是同一个元素”。

假如 $𝑎, 𝑏$ 间有 $𝑎 ≺ 𝑏$ ，并且中间不存在一个元素 $𝑐$ 使得 $𝑎 ≺ 𝑐$ 且 $𝑐 ≺ 𝑏$ ，则称 $𝑏$ 覆盖 $𝑎$ 。

2.哈斯图

哈斯图是一种简化的关系图，用于表示一个偏序关系。

由于偏序关系是对称的，每个元素必有一条指回自己的环，这显然可以省略；

由于偏序关系是传递的，两元素间有长度大于等于 $2$ 的通路则必有直接通路，因此略去所有长度大于等于 $2$ 的通路。这意味着只有一个元素覆盖另一个元素时，两者间才有边；

规定偏序关系中较大者总画在较小者的上方，这样可以略去方向。

3.元与确界

首先我们来讲讲极大元、极小元、最大元、最小元：

取 $𝐴$ 中的某一个元素 $𝑎$ 。如果在 $𝐴$ 中没有比 $𝑎$ 更大的元素，那么称 $𝑎$ 为极大元；反之，如果在 $𝐴$ 中没有比 $𝑎$ 更小的元素，那么称 $𝑎$ 为极小元。

如果 $𝑎$ 大于等于 $𝐴$ 中所有的元素，那么称 $𝑎$ 为最大元；反之，如果 $𝑎$ 小于等于 $𝐴$ 中所有的元素，那么称 $𝑎$ 为最小元。 ²² 这两段话乍一看没啥区别，但关键在于是否是对“所有”的元素！如果存在与 $𝑎$ 不可比的元素，那么 $𝑎$ 就不能是最大元或最小元。

因此，如果 $𝑎$ 是最大元，那么它亦必是极大元；如果 $𝑎$ 是最小元，那么它亦必是极小元。(只有)在偏序集是全序的情况下，如果 $𝑎$ 是极大元，那么它亦是最大元；如果 $𝑎$ 是极小元，那么它亦是最小元。

再者，偏序集可以既没有最大元、也没有最小元，但如果有最大元、则最大元必唯一，如果有最小元、则最小元必唯一。然而，极大元和极小元的数量可以不限，既可以没有，也可以有多个。

接下来我们讲讲上界、下界、上确界、下确界：

“界”是针对偏序集 $(𝐴, ⪯)$ 的子集来说的。从偏序集中取一子集 $𝑆$ ，如果 $𝐴$ 中存在一个元素 $𝑎$ 大于等于 $𝑆$ 中的所有元素(注意是所有！)，则称 $𝑎$ 是 $𝑆$ 的上界；反之，若元素 $𝑎$ 小于等于 $𝑆$ 中的所有元素，则称 $𝑎$ 是 $𝑆$ 的下界。注意，这里只要求 $𝑎 \in 𝐴$ ，也就是 $𝑆$ 中的元素也可以是 $𝑆$ 的上界或下界。

而上界中的最小元称为 $𝑆$ 的上确界，下界中的最大元称为 $𝑆$ 的下确界。类似于最大元最小元， $𝑆$ 可以既没有上确界也没有下确界，但如果有的话必唯一；上确界必是上界，下确界也必是下界。

并且，如果有上界属于 $𝑆$ ，那么它必是上确界；同理，如果有下界属于 $𝑆$ ，那么它必是下确界。