《组合数学》 §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\) 都是链。

证明略。