极小不等于最小
定义 2.3.1
(偏序、极小元素与最小元素)
集合上的偏序 满足自反性、反对称性及传递性;两个元素不一定可以比较。对偏序集的子集 ,元素 称为
- 的极小元素,若不存在与 不同的 满足 ;
- 的最小元素,若对每个 都有 。
把比较方向反转,便得到极大元素和最大元素的定义。
定理 2.3.2
(最小元素必为极小,且唯一)
若 有最小元素 ,则 是 的极小元素,而且 是 唯一的最小元素。
证明
(反对称性迫使两者相等)
设 满足 。由于 是最小元素,也有 ,反对称性便给出 。所以没有与 不同的元素在它之下, 是极小元素。若 也是最小元素,则 且 ,故 。
极小元素却未必最小,因为它可能与另一元素不可比较。
定理 2.3.3
(非空有限偏序集必有极小元素)
每个非空有限偏序集都有极小元素。
证明
(严格下降的路径必须停止)
任取一个元素 。若它不是极小,就选 且 ,并照此继续。由传递性, 时 ;反对称性加上 使任何元素都不会重复出现:若 时 ,则 会迫使 。有限集合中这条路径必然停止,而它停下的地方就是极小元素。
这并不保证有最小元素。对无限集合,上述结论也可能失效:整数配上通常次序便没有极小元素。
常见错误
(把看似唯一的底部当成最小元素)
有限偏序集可以有多个极小元素,此时它们都不是最小元素。“每个非空有限偏序集都有极小元素”不可加强为“有最小元素”。在 上以整除定序,极小元素是 和 ,而两者互不整除。
在不违反原有比较下排成全序
定义 2.3.4
(线性扩张)
集合 上偏序 的线性扩张,是 上的一个全序 ,使得对所有 , 蕴含 。
定理 2.3.5
(反复移除极小元素得到线性扩张)
设 为有限偏序集。反复从剩余的元素中移除一个极小元素,并按移除次序排列,所得列表就是 的一个线性扩张。反过来,任何线性扩张的首项都是极小元素。
证明
(较大的元素不会比较小的先被移除)
设 且 。当 仍在集合中时, 有一个与它不同而较小的元素 ,所以 不是极小,不能先被移除。因此 先被移除,在列表中排在前面。每一步都可行,因为非空有限偏序集必有极小元素。反过来,设 是某线性扩张的首项。若有 满足 ,则 必须排在 之前,这不可能,所以 是极小元素。
证明透视
为何以极小性决定下一个元素
证明只依赖一个比较:对 ,“在剩余元素中极小”这个检验之所以挡住 ,正是因为 仍然在场。除此之外不需要别的信息,所以程序无需预先观察,也无需回头修正。有限性用了两次:保证每一阶段都有极小元素,并保证程序在 步后结束。反对称性用在极小元素的存在性上,因为没有它, 这样的循环可能令极小元素完全消失。逆向叙述说明这个选择并非方法的产物:每个线性扩张都从一个极小元素开始,移除它之后剩下的部分仍是线性扩张。不同的极小元素选择会产生不同的扩张,所以结论只是存在性,不是唯一性。
下面的例子把两个结果用于整除序,其中 表示 。
例题
例题 2.3.6
(整除序中的极小与最小)
在 上,找出所有极小及极大元素,并判断是否存在最小及最大元素。
只有 和 在 中没有另一个不同的因数;其余每个元素均可被 或 整除。因此极小元素是 。由于 且 ,两者均不是最小元素。每个元素都整除 ,所以 是最大元素,因而也是极大元素。其他元素均为 的不同因数,故不是极大元素。因此唯一极大元素是 ,而最小元素不存在。
例题 2.3.7
(列出所有线性扩张)
在 上以整除定序。列出所有线性扩张并解释为何没有遗漏。
整除所有元素,故必排第一;所有元素都整除 ,故 必排最后。中间的 和 不可比较,因此任一个都可以先排。 及 都保留所有整除比较。首尾位置已确定,中间只有两种排列,所以没有其他可能。
例题 2.3.8
(反链没有比较需要遵守)
设 ,只有 时才有 。每个元素都既是极小又是极大,没有最小或最大元素。移除程序可以从三个元素中任一个开始,再从剩下两个中任选一个,最后是剩下的一个,所以 的 种排列全都是线性扩张。这是偏序完全不施加限制的边界情形。
反例模式
极小元素可以不唯一,因此未必有最小元素
命题:非空有限偏序集必有最小元素。以整除序检验 。 是极小元素,因为 和 都不整除 ; 同理也是极小元素。若 是最小元素,它应整除 ,但并非如此;若 是最小元素,它应整除 ,也并非如此;而 不是最小元素,因为 。所以 没有最小元素,尽管它有限且非空。补救是改用上面证明的较弱而正确的叙述:必有极小元素;只有当所有元素都在某个共同元素之上时,才有最小元素。
练习
快速检查
(最小元素是否必为极小?极小元素是否必为最小?)
一个方向用反对称性;另一个方向用整除序下的 。
解答 · 答案
由反对称性,最小元素必为极小。反过来不成立:在整除序下, 是 的极小元素,但它不整除 ,所以不是最小元素。
快速检查
(以整除定序排列 。共有多少个线性扩张?)
先选一个极小元素,再对剩余的元素重复。关系为 、、。
解答 · 答案
共有 个。极小元素是 和 。先取 时,剩下的 须保持 在 之前,得 、、。先取 时,因为 和 都要求 在先,下一个必是 ,之后 可任意排:、。总共 。
快速检查
(为什么配上通常次序的 的每个非空子集都有极小元素,而 没有?)
比较 本身与 的非空子集。
解答 · 答案
由良序原理, 的每个非空子集都有最小元素,它同时也是极小元素。 本身没有极小元素,因为对每个整数 , 都严格较小。本单元的有限性论证不适用于这两个集合。