《组合数学》 §1.2 学习笔记

前言：本文有很多 $\leqslant$ 符号，均表示偏序关系。小于等于则使用 $\le$ 。（自己定的规则，其实可以混用）

定义 1.2.1

设 $X$ 是一个非空集合， $P$ 是定义在 $X$ 上的具有自反性、反对称性及传递性的二元关系，

则称 $\mathbf{P} = (X,P)$ 为一个偏序集。在不引起混淆的情况下，又是直接称 $X$ 是一个偏序集。

符合上述性质的关系称为偏序关系。

通常用 $x \leqslant y$ 来描述 $X$ 中的元素 $x,y$ 满足偏序集 $(X,P)$ 中 $P$ 所规定的关系，

即 $(x,y) \in P$ 记为 $x \leqslant y$ ，这样偏序集 $(X,P)$ 也可写成 $(X,\leqslant)$ 。

根据 “$\leqslant$” ，自然地定义 $X$ 上的二元关系 “$<$” ：$x < y$ 表示 $x \leqslant y$ 且 $x \ne y$ 。

例 1.2.2

设 $\mathbb{Z}^+$ 为全体正整数组成的集合，对于 $a,b \in \mathbb{Z}^+$ ，规定 $a \leqslant b$ 当且仅当 $a \mid b$ ，则 $\mathbb{Z}^+$ 是一个偏序集。

提示：这里是书本自己随便定义的。

例 1.2.3

设 $S$ 是一个集合，$P(S)$ 为 $S$ 的幂集。对于 $A,B \in P(S)$ ，规定 $A \leqslant B$ 当且仅当 $A \subseteq B$ ，

则易验证 $P(S)$ 为一个偏序集。当 $S$ 是无限集时，令 $P_f(S)$ 表示 $S$ 所有有限子集组成的集合。

对于 $A,B \in P_f(S)$ ，仍如上规定 $A \leqslant B$ ，则 $P_f(S)$ 也为一个偏序集。

例 1.2.4

看不懂。

定义 1.2.5

给定偏序集 $\mathbf{P} = (X, P)$ ，若对 $X$ 中任意两个元素 $x,y$ ，

$x \leqslant y$ 与 $y \leqslant x$ 必有一者成立，则称 $\mathbf{P}$ 为一个全序集，也称为链。

若对 $X$ 中任意两个相异的元素 $x,y$ ，$x \leqslant y$ 与 $y \leqslant x$ 都不成立（即两两不可比较），则称 $\mathbf{P}$ 为反链。

有限链或反链中的元素个数称为它的长度。

定义 1.2.6

给定偏序集 $(X,P)$ ，若 $X’$ 是 $X$ 的子集，则易验证 $P$ 在 $X’$ 上的限制也成为一个偏序集。

称 $\mathbf{P}’ = (X’,P)$ 为 $\mathbf{P} = (X, P)$ 的子偏序集。在不引起混淆的情况下，有时也直接称 $X’$ 是 $X$ 的子偏序集。

偏序集 $(X,P)$ 的最长子链的长度称为这个偏序集的高度，其最长子反链的长度称为这个偏序集的宽度。

例 1.2.7

在整除关系决定的偏序集 $\mathbf{P} = (\mathbb{Z}^+,\mid)$ 中，易验证 $(\{m \mid m = 2^k, k\in \mathbb{N}\}, \mid)$ 是 $\mathbf{P}$ 的子偏序集，它是一个链

而 $\mathbf{P}$ 的另一个子偏序集 $(\{p \mid p \in \mathbb{P}\},\mid)$ ，其中 $\mathbb{P}$ 表示素数集，则是反链。

在包含关系 $\subseteq$ 决定的偏序集 $(P(S), \subseteq)$ 中，$(\{A\subseteq S \mid |A| = 1\}, \subseteq)$ 是它的一个子反链。

事实 1.2.8

对于 $\mathbf{P}$ 的两个子偏序集 $A$ 和 $B$ ，如果 $A$ 是链，$B$ 是反链，则 $|A \cap B| \le 1$ 。

定义 1.2.9

偏序集 $X$ 的极小元是 $X$ 中的一个元素 $a$ ，使得没有异于 $a$ 的元素 $x$ 满足 $x \leqslant a$ ，

即若 $\exists x \in X, x \leqslant a$ ，则必有 $x = a$ ；而最小元是 $X$ 中的一个元素 $a$ ，使得对任意 $x \in X$ 均有 $a \le x$ 。

类似地，$X$ 的极大元是 $X$ 中的一个元素 $b$ ，使得没有异于 $b$ 的元素 $y$ 满足 $b \le y$ ；

而最大元是 $X$ 中的一个元素 $b$ ，使得对任意 $y \in X$ ，均有 $y \le b$ 。

显然，一个链的极小元就是最小元，极大元也就是最大元。

例 1.2.10

偏序集的所有极小元形成一个反链，所有极大元也如此。

定理 1.2.11

设偏序集 $(X, \leqslant)$ 的高度为 $n$ ，则存在划分 $X = \bigcup_{i=1}^n A_i$ ，使得每个 $A_i$ 都是反链。

证明略。

定理 1.2.12（Dilworth 定理）

设有限偏序集 $(X, \leqslant)$ 的宽度为 $m$ ，则存在划分 $X = \bigcup_{i=1}^mC_i$ ，使得每个 $C_i$ 都是链。

证明略。