集合论与图论 · 第 9 讲：偏序集与 Mirsky 定理

本页目录

集合论与图论

2026年 10月15日笔记

1. Mirsky定理

设是非空有限偏序集。称两两可比的元素组成的集合为链，两两不可比的元素组成的集合为反链。

定理（Mirsky）：中最长链的元素个数，等于将划分成反链所需的最少反链数。

证明：记最长链的元素个数为。若被划分为个反链，则任意一条链在每个反链中至多有一个元素。取一条含个元素的链，可知。

下面构造一个恰有个反链的划分。对每个，令为以为最大元素的链所能包含的最多元素个数，并令

由于有限，每个均有定义，且，所以这些两两不交，且并集为。若，将一条以为最大元素、含个元素的链接上，便得到一条以为最大元素的链。因此，从而与不可能同属一个。故每个都是反链。

再取一条最长链。由上述性质，；这些数都在到之间，故恰好分别为。于是每个均非空，构成的一个反链划分。结合前面的下界，最少反链数正是。

另一证明（对最长链长度归纳）：仍记中最长链的元素个数为。当时，中任意两个不同元素都不可比，因此本身就是一个反链。

假设对最长链的元素个数小于的所有非空有限偏序集，均可将其划分成与最长链等数目的反链。现在设，令为的所有极小元组成的集合。任意两个不同的极小元不可比，故是反链。记，并赋予从继承的偏序关系。

中不可能有含个元素的链：否则这条链的首元素不是的极小元，其下方还有一个元素，可以将它接到链的前端，得到中含个元素的链，矛盾。另一方面，取中一条含个元素的链，其首元素必为极小元，否则同样可以向前延长；所以其余个元素在中构成一条链。由此可知的最长链恰含个元素。

根据归纳假设，可划分为个反链。再加上反链，便得到的一个由个反链组成的划分。前一证明的下界论证说明，任何反链划分都至少需要个反链。因此结论成立。

推论

是一个片续集，且，若有两个正整数满足，则中必存在一个包含个元素的反链或一个包含个元素的链。

定理（Dilworth）：

设是非空有限偏序集，则中最大反链的元素个数，等于将划分成链所需的最少链数。

换言之，若的最大反链含个元素，则既可以将划分为条链，也不可能用少于条链划分。

定理（超限归纳原理）：

设是良序集，是关于的命题。若对每个，只要所有满足的都使成立，就能推出成立，则对中的每个元素都成立。即

这里的归纳假设包含之前的所有元素，不仅是紧邻的前一个元素；因此同一条件也适用于没有直接前驱的元素。

证明：

反设存在使不成立。由于是良序集，所有使命题不成立的元素中存在最小元。于是每个都满足。由定理的归纳条件可得也成立，矛盾。因此不存在反例，命题对所有成立。

定义：如果是两个偏序集，存在一个双射，使得对任意，有当且仅当，则称与同构。