关系

• 1. 有序对与笛卡尔积
  • 1.1 有序对
  • 1.2 笛卡尔积
• 2. 二元关系
  • 2.1 关系的定义
  • 2.2 关系的表示
  • 2.3 关系的运算
• 3. 关系的性质
  • 3.1 五大基本性质
  • 3.2 传递闭包
• 4. 等价关系
  • 4.1 等价关系的定义
  • 4.2 等价类与商集
  • 4.3 集合的划分
• 5. 偏序关系
  • 5.1 偏序的定义
  • 5.2 全序与可比性
  • 5.3 特殊元素
  • 5.4 Hasse 图

在前面的章节中，我们学习了集合的基本定义及其运算。然而，数学的研究对象不仅仅是孤立的个体，更多时候我们需要关注对象之间的“联系”。例如，“小于”关系描述了两个实数的大小比较，“属于”关系描述了元素与集合的隶属。在本章中，我们将通过集合论的语言，将这种抽象的“联系”严格化，这就是关系（Relation）。

1. 有序对与笛卡尔积

在讨论关系之前，我们需要一种能够区分顺序的数学工具。集合 $\left\{a,\, b\right\}$ 是无序的，即 $\left\{a,\, b\right\} = \left\{b,\, a\right\}$。但在描述“$x$ 喜欢 $y$”这种关系时，顺序至关重要。

1.1 有序对

为了表达顺序，我们引入了有序对的概念。

定义 有序对（Ordered Pair）是由两个元素组成的序列，记作 $(a,\, b)$。其中 $a$ 称为第一分量（First Coordinate），$b$ 称为第二分量（Second Coordinate）。

在数学中，我们经常需要处理成对出现的数据，例如平面上的坐标 $(x,\, y)$，或者是表示两个集合之间映射的输入输出对。这些对子与普通集合 $\left\{a,\, b\right\}$ 的最大区别在于其有序性。在集合中，顺序是不重要的，但对于有序对，$(1,\, 2)$ 和 $(2,\, 1)$ 是完全不同的对象。

在集合论的公理体系中，我们通常使用 Kuratowski 的定义来通过集合构造有序对：

$$(a,\, b) = \left\{\left\{a\right\},\, \left\{a,\, b\right\}\right\}$$

这种定义巧妙地利用了集合的嵌套结构来标记谁是“第一个”。集合 $\left\{a\right\}$ 标识了第一分量，而 $\left\{a,\, b\right\}$ 包含了所有成分。如果 $a = b$，则该定义简化为 $\left\{\left\{a\right\}\right\}$。这种构造方式虽然看起来有些奇怪，但它在逻辑上是非常严密的，因为它仅依赖于集合的基本概念就成功诱导出了“顺序”的语义。

@theorem-1 有序对相等的充要条件是它们对应的分量分别相等，即：

$$(a,\, b) = (c,\, d) \Leftrightarrow a = c \land b = d$$

证明： 充分性（$\Leftarrow$）是明显的，若 $a = c$ 且 $b = d$，则由外延公理可知 $\left\{\left\{a\right\},\, \left\{a,\, b\right\}\right\} = \left\{\left\{c\right\},\, \left\{c,\, d\right\}\right\}$。

必要性（$\Rightarrow$）：假设 $(a,\, b) = (c,\, d)$，即 $\left\{\left\{a\right\},\, \left\{a,\, b\right\}\right\} = \left\{\left\{c\right\},\, \left\{c,\, d\right\}\right\}$。 我们需要证明 $a = c$ 且 $b = d$。根据集合相等的定义，左边集合的每一个元素都必须属于右边集合。

1. 情况一：$a = b$ 此时 $(a,\, b) = \left\{\left\{a\right\},\, \left\{a,\, a\right\}\right\} = \left\{\left\{a\right\}\right\}$。 由于集合相等，必有 $\left\{\left\{c\right\},\, \left\{c,\, d\right\}\right\} = \left\{\left\{a\right\}\right\}$。 这意味着该集合只有一个元素，因此 $\left\{c\right\} = \left\{a\right\}$ 且 $\left\{c,\, d\right\} = \left\{a\right\}$。 由第一个等式得 $c = a$。由第二个等式得 $c = d = a$。 既然 $a = b$ 且 $a = c = d$，那么显然有 $a = c$ 且 $b = d$。

2. 情况二：$a \neq b$ 此时 $(a,\, b)$ 是一个含有两个不同元素的集合：$\left\{a\right\}$ 和 $\left\{a,\, b\right\}$。 由于 $(a,\, b) = (c,\, d)$，$\left\{a\right\}$ 必须等于 $\left\{c\right\}$ 或 $\left\{c,\, d\right\}$。 如果 $\left\{a\right\} = \left\{c,\, d\right\}$，则 $c = d = a$，这会导致 $(c,\, d)$ 只有一个元素 $\left\{\left\{c\right\}\right\}$，与 $(a,\, b)$ 有两个元素矛盾。 因此，必须有 $\left\{a\right\} = \left\{c\right\}$，即 $a = c$。 接下来，剩下的一项必有 $\left\{a,\, b\right\} = \left\{c,\, d\right\}$。 既然已经知道 $a = c$，等式变为 $\left\{a,\, b\right\} = \left\{a,\, d\right\}$。 因为 $b \neq a$ 且 $b$ 必须属于右边的集合 $\left\{a,\, d\right\}$，所以唯一的可能是 $b = d$。

我们可以进一步推广这个概念，定义更多的元素序列。

定义 有序 $n$ 元组（Ordered $n$-tuple）可以通过递归定义：

• 对于 $n=1$，$(a_1) = a_1$
• 对于 $n=2$，即上面定义的有序对 $(a_1,\, a_2)$
• 对于 $n > 2$，$(a_1,\, a_2,\, \cdots,\, a_n) = ((a_1,\, a_2,\, \cdots,\, a_{n-1}),\, a_n)$

这种定义方式允许我们将任何长度的序列都归约为嵌套的有序对。例如，一个三元组 $(a,\, b,\, c)$ 实际上被视为 $((a,\, b),\, c)$。

1.2 笛卡尔积

有了有序对，我们就可以定义集合之间的乘法运算，这种运算产生的集合包含了所有可能的配对方式。

定义 笛卡尔积（Cartesian Product）是指集合 $A$ 与 $B$ 的所有可能的有序对构成的集合，记作 $A \times B$：

$$A \times B = \left\{(a,\, b) \mid a \in A,\, b \in B\right\}$$

这个概念得名于法国数学家笛卡尔（René Descartes），正是他将代数与几何结合，开创了解析几何。在解析几何中，平面的每一个点都可以表示为实数集 $\mathbb{R} \times \mathbb{R}$ 中的一个有序对。

例 1.1 设 $A = \left\{1,\, 2\right\}$，$B = \left\{a,\, b,\, c\right\}$，则它们的笛卡尔积包含 $2 \times 3 = 6$ 个元素：

$$A \times B = \left\{(1,\, a),\, (1,\, b),\, (1,\, c),\, (2,\, a),\, (2,\, b),\, (2,\, c)\right\}$$

NOTE

对于有限集，笛卡尔积的势（元素个数）满足乘法原理：$|A \times B| = |A| \cdot |B|$。这也是为什么它被称为“积”的原因。

笛卡尔积的一个重要性质是它通常不满足交换律。也就是说，一般情况下 $A \times B \neq B \times A$。只有当 $A = B$，或者其中至少一个集合为空集时，等式才成立。 例如，若 $A = \left\{1\right\}, B = \left\{2\right\}$，则 $A \times B = \left\{(1,\, 2)\right\}$，而 $B \times A = \left\{(2,\, 1)\right\}$。

此外，笛卡尔积也不满足结合律。 尽管 $(A \times B) \times C$ 与 $A \times (B \times C)$ 在直观上都表示三元组的集合，但根据前面的递归定义，它们的元素形式分别是 $((a,\, b),\, c)$ 和 $(a,\, (b,\, c))$。虽然它们之间存在一种自然的对应关系（双射），但在严格的集合论层面上，它们是不同的集合。

为了处理多个集合的乘积，我们定义 $n$ 重笛卡尔积：

$$A_1 \times A_2 \times \cdots \times A_n = \left\{(a_1,\, a_2,\, \cdots,\, a_n) \mid a_i \in A_i,\, i = 1,\, \cdots,\, n\right\}$$

特别地，如果所有的集合都相同，$A^n$ 表示 $A$ 与自身的 $n$ 次笛卡尔积。

• $A^1 = A$
• $A^2 = A \times A$
• $A^3 = A \times A \times A$

例如，三维空间可以表示为 $\mathbb{R}^3$，其元素是形如 $(x,\, y,\, z)$ 的有序三元组。

2. 二元关系

2.1 关系的定义

在日常生活中，我们经常谈论事物之间的关系：张三是李四的“朋友”，3 “小于” 5，或者 10 是 2 的“倍数”。在数学中，关系被抽象为一种结构，用来描述两个集合的元素之间是否存在某种特定的连接。

定义 二元关系（Binary Relation）：从集合 $A$ 到集合 $B$ 的一个二元关系 $R$ 是笛卡尔积 $A \times B$ 的一个子集，即 $R \subseteq A \times B$。

如果一个有序对 $(a,\, b)$ 属于子集 $R$，我们就说 $a$ 与 $b$ 满足关系 $R$，记作 $a \mathrel{R} b$。如果 $(a,\, b) \notin R$，则说它们不满足该关系，记作 $a \not\mathrel{R} b$。

定义 $A$ 上的关系：如果 $A = B$，即关系是在同一个集合内部建立的，我们称 $R$ 是集合 $A$ 上的一个二元关系。

关系的本质就是筛选出符合特定条件的有序对。

例 2.1：

1. 小于关系：在整数集 $\mathbb{Z}$ 上，定义关系 $L = \left\{(x,\, y) \in \mathbb{Z} \times \mathbb{Z} \mid x < y\right\}$。那么 $3 \mathrel{L} 5$ 是真的，因为 $(3,\, 5) \in L$；而 $5 \mathrel{L} 3$ 是假的。
2. 整除关系：在正整数集 $\mathbb{Z}^+$ 上，定义关系 $D = \left\{(m,\, n) \mid \exists k \in \mathbb{Z}^+,\, n = k \cdot m\right\}$。我们通常把 $m \mathrel{D} n$ 记作 $m \mid n$（$m$ 整除 $n$）。
3. 空关系：$\varnothing \subseteq A \times B$。在空关系中，没有任何元素之间存在联系。
4. 全域关系：$E = A \times B$。在全域关系中，任意两个元素（前者来自 $A$，后者来自 $B$）都有关系。
5. 恒等关系：在集合 $A$ 上定义 $I_A = \left\{(a,\, a) \mid a \in A\right\}$。这描述了每个元素仅与其自身有关系，通常对应于逻辑上的“等于”。

2.2 关系的表示

为了直观地研究关系，特别是当集合规模有限时，我们可以使用不同的数学工具来表示它。

1. 集合表示法：这是最基本的方法，直接列出所有属于关系的有序对。

2. 关系矩阵（Relation Matrix）：这是一种非常适合计算机处理的表示方式。设 $A = \left\{a_1,\, a_2,\, \cdots,\, a_m\right\}$，$B = \left\{b_1,\, b_2,\, \cdots,\, b_n\right\}$。我们定义一个 $m \times n$ 的布尔矩阵 $M_R = [r_{ij}]$，其中的元素取值规则为：

   $$r_{ij} = \begin{cases} 1, & a_i \mathrel{R} b_j \\ 0, & a_i \not\mathrel{R} b_j \end{cases}$$

   使用矩阵表示关系的优势在于，许多关系运算可以转化为矩阵运算。例如：

   • 并运算 $R \cup S$ 对应于矩阵的按位或（Logical OR）。
   • 交运算 $R \cap S$ 对应于矩阵的按位与（Logical AND）。
   • 包含关系 $R \subseteq S$ 对应于矩阵元素的逐项不等式 $r_{ij} \leqslant s_{ij}$。

3. 关系图（Relation Graph）：对于集合 $A$ 上的关系，我们可以利用图论的思想。将 $A$ 中的每个元素看作一个点（顶点）。如果 $a \mathrel{R} b$，我们就画一条从 $a$ 指向 $b$ 的有向边。如果 $a \mathrel{R} a$，则在点 $a$ 上画一个自环。

关系图能够直观地展示关系的结构：

• 路径：如果从 $a$ 到 $b$ 有一条长度为 $k$ 的路径，说明 $a \mathrel{R^k} b$。
• 孤立点：没有任何边相连的元素在关系中不与其他任何元素（包括自身）产生联系。
• 回路：如果图中存在回路，说明关系中存在某种循环推荐或反馈。

例 2.2 设 $A = \left\{1,\, 2,\, 3\right\}$，定义关系 $R = \left\{(1,\, 1),\, (1,\, 2),\, (2,\, 3)\right\}$。 我们可以通过矩阵来观察它的结构：

$$M_R = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$$

其关系图如下：

从矩阵和图中我们可以一眼看出，1 与 1、1 与 2、2 与 3 有关系，而其他的配对都不在关系中。通过这种可视化手段，原本抽象的集合子集变得形象生动。

2.3 关系的运算

由于关系本质上是集合，我们可以对它们进行标准的集合运算。例如，如果 $R$ 和 $S$ 都是 $A$ 到 $B$ 的关系，那么它们的并 $R \cup S$ 表示满足 $R$ 或 满足 $S$ 的所有对子。

除此之外，关系还有一些特殊的代数运算。

定义 逆关系（Inverse/Converse Relation）：设 $R$ 是从 $A$ 到 $B$ 的关系，它的逆关系 $R^{-1}$ 是从 $B$ 到 $A$ 的关系，定义为：

$$R^{-1} = \left\{(b,\, a) \mid (a,\, b) \in R\right\}$$

直觉上，逆关系就是将所有的有向边反向。例如，“父亲”关系的逆关系是“子女”关系。

定义 关系的复合（Composition）：这是关系理论中最核心的运算。设 $R \subseteq A \times B$，$S \subseteq B \times C$。则 $S$ 与 $R$ 的复合（记作 $S \circ R$）是一个从 $A$ 到 $C$ 的新关系，定义为：

$$S \circ R = \left\{(a,\, c) \mid \exists b \in B,\, (a \mathrel{R} b \land b \mathrel{S} c)\right\}$$

TIP

注意复合符号的顺序。$S \circ R$ 意味着先应用 $R$，再应用 $S$。这与函数复合 $f(g(x))$ 的写法是一致的。

关系的复合可以看作是“找中间人”。如果 $a$ 能通过某个中间桥梁 $b$ 间接地联系到 $c$，那么 $a$ 与 $c$ 就建立了复合关系。 在矩阵表示下，关系的复合对应于布尔矩阵乘法。设 $M_R$ 和 $M_S$ 是对应的矩阵，则 $M_{S \circ R} = M_R \cdot M_S$，其中加法对应逻辑或 ($\lor$)，乘法对应逻辑与 ($\land$)。

定义 关系的幂：对于集合 $A$ 上的关系 $R$，我们可以定义它自身的复合：

• $R^1 = R$
• $R^{n+1} = R^n \circ R$ 直观上，$a \mathrel{R^n} b$ 表示在关系图中，存在一条从 $a$ 到 $b$ 且长度恰好为 $n$ 的路径。

3. 关系的性质

当我们深入研究某种特定的数学结构时，通常会关注关系是否具有某些优美的特征。以下五个性质是分析关系时的基础维度。

3.1 五大基本性质

设 $R$ 是定义在集合 $A$ 上的二元关系。

定义 自反性（Reflexivity）：如果集合 $A$ 中的每一个元素都与自身有关系，即 $\forall a \in A,\, (a,\, a) \in R$，则称 $R$ 是自反的。

• 直观理解：每个人都认识自己，每个数都等于自己。
• 例子：实数集上的“等于”关系、“大于等于”关系。
• 图形特征：关系图中每一个顶点都有一个自环。
• 矩阵特征：关系矩阵的主对角线元素全为 1。

定义 反自反性（Irreflexivity）：如果集合 $A$ 中的任何元素都不与自身有关系，即 $\forall a \in A,\, (a,\, a) \notin R$，则称 $R$ 是反自反的。

• 直观理解：没有人比自己更老，没有任何数严格大于自身。
• 例子：实数集上的“大于”关系（因为没有任何数大于它自己）。
• 注意：反自反并不等同于“不自反”。一个关系可能既不是自反的（只有部分元素有自环），也不是反自反的（部分元素有自环，部分没有）。

定义 对称性（Symmetry）：如果关系是相互的，即 $\forall a,\, b \in A,\, a \mathrel{R} b \Rightarrow b \mathrel{R} a$，则称 $R$ 是对称的。

• 直观理解：如果 A 是 B 的熟人，那么 B 也是 A 的熟人。
• 例子：平面几何中的“相似”关系、社会关系中的“熟人”关系。
• 矩阵特征：关系矩阵是一个对称矩阵（即 $M_R = M_R^T$）。
• 图形特征：如果有一条从 $a$ 到 $b$ 的有向边，必然也有一条从 $b$ 到 $a$ 的有向边。

定义 反对称性（Antisymmetry）：如果关系只允许在相等的情况下双向成立，即 $\forall a,\, b \in A,\, (a \mathrel{R} b \land b \mathrel{R} a) \Rightarrow a = b$，则称 $R$ 是反对称的。

• 直观理解：如果 A 并不比 B 小，且 B 也不比 A 小，那么他们只能是同一个数。
• 例子：正整数集上的“整除”关系。如果 $m \mid n$ 且 $n \mid m$，那么必有 $m = n$。
• 注意：反对称性并不意味着“不对称”。它的核心含义是禁止不同元素之间的双向连接。

定义 传递性（Transitivity）：如果关系具有连通性，即 $\forall a,\, b,\, c \in A,\, (a \mathrel{R} b \land b \mathrel{R} c) \Rightarrow a \mathrel{R} c$，则称 $R$ 是传递的。

• 直观理解：朋友的朋友不一定是朋友，但祖先的祖先一定是祖先。
• 例子：祖先关系。如果你是你父亲的后代，你父亲是你爷爷的后代，那么你自然也是你爷爷的后代。
• 判据：一个关系是传递的，当且仅当 $R^2 \subseteq R$。

3.2 传递闭包

很多时候，原始的关系并不具备传递性。例如，“直接认识”关系不具有传递性（你认识的朋友的朋友，你不一定直接认识）。但我们可能对“间接认识”（即通过任意长度的社交链联系起来）感兴趣。这就引入了闭包（Closure）的概念。

定义 传递闭包（Transitive Closure）：给定集合 $A$ 上的关系 $R$，包含 $R$ 且具有传递性的最小关系称为 $R$ 的传递闭包，记作 $R^+$。

传递闭包可以通过穷举所有可能的路径长度来构造：

$$R^+ = R \cup R^2 \cup R^3 \cup \cdots = \bigcup_{n=1}^{\infty} R^n$$

如果集合 $A$ 是有限的，假设有 $n$ 个元素，那么我们只需要计算到 $R^n$ 即可，因为任何长度超过 $n$ 的路径在简单图中必然包含重复节点。

4. 等价关系

等价关系是数学抽象中最强大的工具之一。它的本质作用是化归：将具有相同性质的不同对象归为同一类，从而简化问题的复杂度。

4.1 等价关系的定义

定义 等价关系（Equivalence Relation）：如果集合 $A$ 上的关系 $R$ 同时满足 自反性、对称性 和 传递性，则称 $R$ 是 $A$ 上的等价关系。

我们通常用符号 $\sim$ 或 $\equiv$ 来代替 $R$。等价关系可以看作是“等于”概念的推广。

常见的例子：

1. 模 $n$ 同余：在整数集 $\mathbb{Z}$ 上，固定正整数 $n$。定义 $a \equiv b \pmod n$ 当且仅当 $n$ 能整除 $a-b$。例如，在模 12 的时钟算术中，13 点和 1 点是等价的。
2. 集合等势：在所有集合构成的类中，如果存在从 $A$ 到 $B$ 的双射，则称 $A \approx B$。这满足等价关系的三大特征。
3. 逻辑等价：在命题逻辑中，如果两个命题在所有赋值下真值相同，则它们是等价的。

4.2 等价类与商集

有了等价关系后，我们可以将集合 $A$ 切分成一个个“小格”。

定义 等价类（Equivalence Class）：设 $R$ 是 $A$ 上的等价关系。对于任何元素 $a \in A$，所有与 $a$ 等价的元素构成的子集称为 $a$ 的等价类，记作 $[a]_R$：

$$[a]_R = \left\{x \in A \mid x \sim a\right\}$$

关键性质：

1. $a \in [a]$（由自反性保证）。
2. $[a] = [b]$ 当且仅当 $a \sim b$。
3. 任意两个等价类要么完全相同，要么完全不交（$[a] \cap [b] \neq \varnothing \Rightarrow [a] = [b]$）。

这组性质说明，等价类就像是集合的一层“蒙版”，把原本不同的元素按照等价性“粘”在一起。

定义 商集（Quotient Set）：所有不同的等价类作为元素构成的集合称为 $A$ 关于 $R$ 的商集，记作 $A / R$：

$$A / R = \left\{[a]_R \mid a \in A\right\}$$

通过商集，我们将研究对象从“个体”提升到了“类别”。例如，在研究整数的奇偶性时，我们关心的不再是具体的数字 2、4、6，而是它们的共同类别——“偶数类” $[0]_2$。

4.3 集合的划分

定义 划分（Partition）：集合 $A$ 的一个划分 $\mathcal{P}$ 是指由 $A$ 的非空子集构成的一个集合族，满足：

1. 覆盖性：所有子集的并集等于 $A$。
2. 互斥性：集合族中任意两个不同的成员都不相交。

@theorem-2 等价关系与划分的一一对应： 每一个定义在 $A$ 上的等价关系都唯一地对应 $A$ 的一个划分（即商集）；反之， $A$ 的每一个划分也唯一地定义了一个等价关系。

证明思路：

1. 从关系到划分：利用等价类的性质，每个元素都属于且仅属于一个等价类，因此商集天然地构成了一个划分。
2. 从划分到关系：如果给定一个划分，我们可以定义两个元素“有关系”当且仅当它们位于划分的同一个子块中。容易证明这种定义出的关系满足自反、对称和传递。

这个定理告诉我们，等价关系和集合划分是同一个硬币的两面。关系侧重于描述元素间的局部联系，而划分侧重于描述集合的全局结构。

5. 偏序关系

如果等价关系描述的是“平权”或“相同”，那么偏序关系描述的就是“等级”或“次序”。

5.1 偏序的定义

定义 偏序关系（Partial Order）：如果集合 $A$ 上的关系 $R$ 同时满足 自反性、反对称性 和 传递性，则称 $R$ 是 $A$ 上的偏序关系。通常用符号 $\leqslant$ 记之。

注意这里使用 $\leqslant$ 只是一个抽象符号，它不一定代表数字的大小。

定义 偏序集（Partially Ordered Set, 简称 Poset）：一个集合 $A$ 连同其上的偏序关系 $R$ 构成的二元组 $(A,\, \leqslant)$ 称为偏序集。

例 5.1：

1. 子集包含关系：设 $S$ 是一个集合，其幂集 $\mathcal{P}(S)$ 关于包含关系 $\subseteq$ 构成偏序集。注意，如果 $A = \left\{1\right\}, B = \left\{2\right\}$，则 $A \not\subseteq B$ 且 $B \not\subseteq A$，这意味着并不是所有子集都能比较大小。
2. 整除关系：正整数集 $\mathbb{Z}^+$ 关于整除关系 $\mid$ 是偏序集。它满足自反（$n \mid n$）、反对称（$m \mid n \land n \mid m \Rightarrow m=n$）和传递（$a \mid b \land b \mid c \Rightarrow a \mid c$）。

5.2 全序与可比性

偏序之所以被称为“偏”，是因为它允许存在不可比的元素。

定义 可比（Comparable）：在偏序集 $(A,\, \leqslant)$ 中，如果对于 $a,\, b \in A$，满足 $a \leqslant b$ 或 $b \leqslant a$，则称 $a$ 与 $b$ 是可比的。否则，称它们为不可比（Incomparable）。

定义 全序（Total Order / Linear Order）：如果偏序集中的任意两个元素都是可比的，即这个序列是一条没有分支的线，则称该序为全序。

TIP

实数集 $\mathbb{R}$ 的通常大小关系是全序。但在二维平面上，如果我们定义 $(x_1,\, y_1) \leqslant (x_2,\, y_2)$ 当且仅当 $x_1 \leqslant x_2$ 且 $y_1 \leqslant y_2$，这就只是一个偏序，因为 $(1,\, 2)$ 和 $(2,\, 1)$ 无法比较。

5.3 特殊元素

在偏序集中，有些元素因其位置显赫而被特别命名。

定义 最大元（Greatest Element）：如果一个元素 $g$ 比集合中所有的元素都大（$\forall x \in A,\, x \leqslant g$），则称 $g$ 是最大元。最大元如果存在，必定是唯一的。

定义 极大元（Maximal Element）：如果一个元素 $m$ 没有任何人比它大（不存在 $x$ 使得 $m < x$），则称 $m$ 是极大元。一个偏序集可以有多个极大元。

极大元与最大元的微妙区别： 最大元必须与集合中所有其他元素都可比，并且比它们都大。而极大元只需要保证没有比它更大的元素即可，它不需要管那些与它不可比的元素。在有向图中，极大元就是没有任何出边的顶点（忽略自环）。

NOTE

最大元 vs 极大元： 想象一个职场结构。如果有一个总经理管所有人，他是最大元。如果公司有几个互不隶属的部门，每个部门经理都是极大元（因为没人管他们），但他们不是最大元（因为他们不管其他部门的人）。

类似的，我们可以定义最小元（Least Element）和极小元（Minimal Element）。

• 最小元：$\forall x \in A,\, a \leqslant x$。
• 极小元：不存在 $x \in A$ 使得 $x < a$。 同样的，最小元如果存在则唯一，而极小元可以有多个。

进一步地，如果我们关注偏序集的一个子集 $B \subseteq A$：

• 如果 $a \in A$ 满足 $\forall x \in B,\, x \leqslant a$，则称 $a$ 是 $B$ 的一个上界（Upper Bound）。
• 在所有上界构成的集合中，如果存在最小元，我们称之为上确界（Supremum，或最小上界，Least Upper Bound）。

5.4 Hasse 图

Hasse 图是偏序集最直观的代言人。通过消除冗余信息（自反边和传递边），它保留了偏序的核心骨架。

画图规则：

1. 如果 $a < b$ 且不存在 $c$ 使得 $a < c < b$（即 $b$ 盖住 $a$），则在 $a$ 和 $b$ 之间画连线。
2. 较大的元素画在上方。

例 5.3 考虑数字 12 的所有正因子构成的集合 $D_{12} = \left\{1,\, 2,\, 3,\, 4,\, 6,\, 12\right\}$，关于整除关系。 它的 Hasse 图呈现出一种菱形叠加的结构：

在这个结构中：

• 1 是最小元，也是唯一的极小元。
• 12 是最大元，也是唯一的极大元。
• 4 和 6 是不可比的，虽然它们都整除 12。
• 对于子集 $\left\{2,\, 3\right\}$，它的上界有 6 和 12，其中 6 是它的上确界。

关系理论为我们提供了一套通用的语言，去描述从最简单的集合隶属到复杂的代数结构中无处不在的“联系”。掌握了关系，我们也就拿到了通往函数、图论以及现代抽象代数的钥匙。