偏序关系这块内容我见过太多人挂在半路上。原因不是难而是概念一次性冒出来太多偏序、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界一口气九个术语砸过来谁扛得住更麻烦的是最大元和极大元听起来几乎一模一样但意思差之千里上界和上确界又多了一层“精确”的关系光靠记定义根本分不清。而且这东西不是纯数学玩具它在数据库设计、编译器类型推导、任务调度、知识图谱的层级结构里都实打实地在用。这篇内容我打算用一套贯穿始终的例子把上面所有概念串起来配合哈斯图的读法告诉你每个定义到底在描述什么、找的时候从哪里下手、考试和实际应用里最容易踩哪些坑。看完你至少能达到一个标准给一个偏序集和它的子集你能在五分钟内把这些元、界、确界全部找齐并且每一条都能说出依据。1. 偏序关系的基本规则先搞清楚“≤”到底在说什么1.1 偏序关系不是“小于等于”很多初学者看到偏序关系里的符号“≤”第一反应就是算术里的小于等于。这既是方便之处也是最大的坑。方便在于所有和偏序有关的论证都可以借用“≤”这个符号的直觉坑在于真实的偏序关系压根不限于数字比较元素的顺序、集合的包含、任务的先后依赖全部可以构成偏序关系。我在实际教学中喜欢用“家族辈分”来打比方。假设一个家族里定义关系“a领先b”表示a是b的祖先或者a和b是同一个人。你会发现这个关系满足三条规律一个人一定是自己的祖先自反如果a是b的祖先b又是a的祖先那a和b只能是一个人反对称如果a是b的祖先b是c的祖先那么a一定是c的祖先传递。这三条规律组合在一起就是偏序关系。形式化的定义是这样的设R是集合A上的一个二元关系如果R满足自反性、反对称性、传递性那么R就是一个偏序关系通常记作“≤”而(A, ≤)称为偏序集。注意这里的“≤”已经不是一个具体的算术符号了它只是一个抽象的关系记号。在具体例子里它可能表示“整除”、“包含”、“先于”等等。1.2 自反、反对称、传递三个条件逐个拆解自反性对任意x∈A都有x≤x。意思是一个元素总能和自己比较而且结果是“不落后于自己”。在整除关系里6整除6成立在集合包含关系里集合A包含A自身成立。这个性质比较直观一般不会出错。反对称性对任意xy∈A如果x≤y且y≤x那么xy。这条是偏序关系的灵魂也是和“等价关系”分道扬镳的地方。等价关系要求对称也就是a和b等价时b和a也等价而偏序关系强调的是“谁在前、谁在后”如果有两个元素互相“不大于对方”那就说明它俩根本就是同一个元素。传递性如果x≤y且y≤z那么x≤z。这条的重要性在于它决定了我们能不能通过“中间人”来推理。比如在任务依赖关系中任务A必须在B之前完成B必须在C之前完成那么A必须在C之前完成。如果不满足传递性整个偏序结构就塌了也没法画成层级图。很多人会把反对称性和“不能双向比较”混为一谈这是错误的理解。反对称性没有禁止x≤y和y≤x同时成立它只规定了同时成立的结果xy。换句话说同一个元素当然可以双向比较但不同元素之间不能互相“领先”。1.3 偏序 vs 全序 vs 等价关系偏序和全序的差别用一个词概括就是“可比性”。偏序集里任意两个元素不一定能比较比如整除关系下2和3谁大谁小2不整除33也不整除2两者不可比。但实数集上通常的“≤”任何两个数都能比出高低这就是全序。全序关系一定是偏序关系但偏序关系不一定是全序关系。这个逻辑关系就像“正方形是矩形但矩形不一定是正方形”一样。如果你在写代码处理数据优先级遇到的是全序直接sort就能解决遇到的是偏序就必须用拓扑排序那一套这也是偏序关系在计算机领域最经典的应用。等价关系则是另一套逻辑。等价关系满足自反、对称、传递注意这里没有反对称而是要求对称。等价关系是把元素“归类”偏序关系是把元素“排序”两者出发点完全不同。如果拿集合打比方等价关系看的是“哪些元素属于同一类”偏序关系看的是“哪些元素包含在哪些里面”。2. 最大元、最小元全局第一名的诞生条件2.1 最大元和最小元的定义与判定方法设(A, ≤)是一个偏序集B是A的一个子集。如果存在一个元素b∈B使得对任意x∈B都有x≤b那么b就是B的最大元。同理如果存在一个元素b∈B使得对任意x∈B都有b≤x那么b就是B的最小元。注意三个关键点。第一最大元和最小元必须属于B本身不能跑到集合外面去找。第二它必须和B中每一个元素都能比较而且总是“大于等于”它们也就是所有元素的共同“天花板”。第三由于偏序关系不保证任意两元素可比最大元的存在性其实是很苛刻的。判定方法其实很机械遍历B中所有元素逐个检查它和其他元素是否都满足x≤b。这个步骤用哈斯图看更直观——最大元就是图中位于所有B中元素“上方”的那个点而且必须从它出发能顺着边沿到达所有其他B中的点。2.2 最大元、最小元的唯一性证明思路最大元如果存在一定只有一个。这个结论课本上会证明我这里说一个更直观的理解方式。假设B里有两个不同的最大元b1和b2根据最大元的定义b1要满足x≤b1对一切x∈B成立特别地取xb2就有b2≤b1同理b2是最大元所以b1≤b2。两个不等式同时成立由反对称性立刻推出b1b2。所以最大元要么不存在要么只有一个绝无可能同时出现两个不同的最大元。最小元的唯一性证明完全对称把符号反过来就行。这个唯一性结论在做题时非常有用一旦你找到了一个最大元就可以停手了不用再找第二个。2.3 全序集中最大元什么时候不存在很多人一开始以为任何有限集合都有最大元这个直觉只对全序集成立。在偏序集里最大元非常容易“缺席”。最典型的一个例子在正整数集合上定义整除关系取子集{2, 3, 5}。2和3不可比、3和5不可比、5和2不可比所以这个集合里没有任何一个元素能同时大于等于其他两个元素。最大元不存在最小元自然也不存在。再看一个例子集合{2, 3, 4, 6}在整除关系下4和6谁大4不整除66也不整除4所以没有最大元但2能整除4和62整除自己却无法和3比较大小2不整除3所以2也不是最小元。这个例子里最大元没有最小元也没有但极大元和极小元都存在。这就是下一节要讲的内容。3. 极大元、极小元局部没有更强的对手3.1 极大元、极小元的定义局部比较最大元要求的是“比所有元素都大”极大元的要求则宽松得多在集合B中不存在任何一个元素x使得b≤x且b≠x。换句话说在B里面你找不到一个严格比它大的元素它就是极大元。极小元对称在B中不存在严格比它小的元素。注意极大元不需要和B中所有元素都可比。它只需要保证“没有元素能压过它”。这就像一个班里如果两个同学的成绩没法直接比较比如分属文理科不同评分体系那他们各自在自己体系里可能是最高分两人都是“极大元”。最大元一定是极大元但极大元不一定是最大元。这条逻辑链要记牢。最大元要求“赢过所有人”极大元只要求“没人赢过我”显然后者更容易满足所以极大元可能有很多个最大元最多一个。3.2 用{2, 3, 5}这个例子彻底区分最大元和极大元我们回到整除关系下的集合{2, 3, 5}。这个集合里每个元素之间都不可比所以对2来说找遍整个集合没有任何一个元素比它“严格大”3和5都是不可比不算严格大所以2是极大元。同理3和5也都是极大元。但最大元呢必须要有一个元素同时大于等于2、3、5这里显然谁都不满足所以最大元不存在。反过来看{2, 4, 6, 12}这个整除关系集合。12能整除谁12整除自己也能被2、4、6整除也就是说2≤12、4≤12、6≤12都成立同时12整除12所以12是最大元同时也是极大元。这个例子里极大元只有12一个2还能找到严格比它大的吗能4、6、12都可以所以2不是极大元。4能找到严格比它大的吗12可以所以4也不是。6同理可以被12压住所以不是。可见最大元存在时极大元就是最大元本人。真正有意思的是最大元不存在但极大元存在的情况比如{2, 3, 4, 6}在整除关系下2不整除33不整除24不整除66不整除4所以极大元是谁4在集合里没有严格比4大的元素6和它不可比2和3都比它小所以4是极大元。6同理也是极大元。3呢没有严格比3大的元素4不整除3但是也不被3整除不可比6能被3整除所以6严格大于3那3就不是极大元。2呢4、6都严格比2大所以2不是极大元。最终极大元是4和6最大元不存在。这是一个值得反复琢磨的例子。3.3 有限偏序集一定有极大元吗答案是非空有限偏序集一定存在至少一个极大元也一定存在至少一个极小元。这个结论可以用归纳法严格证明直观上也很好理解从任意一个元素出发如果它不能继续往上走那它已经是极大元如果它能往上走就走一步接着检查因为集合有限不可能无穷尽地往上走最终必然停在一个“上不去”的元素上那就是极大元。但是无限偏序集就不一定了。比如正整数集合带上通常的“≤”关系这是一个全序集没有最大元每个数都能找到比它更大的数但有最小元1。反过来如果定义关系为“≥”那就变成没有最小元但有最大元1。再比如全体正整数在整除关系下1是最小元但极大元一个都没有因为每个正整数n都能找到严格大于它的数比如2n而且n整除2n。这个例子说明无限集里极大元可能完全消失做题时一定要先确认集合是否有限。4. 上界、下界与上确界、下确界站在子集的视角看“天花板”4.1 上界和下界的定义最大元和极大元讨论的是集合内部的“王者”但有时候我们需要跳出集合B到整个偏序集A里面去找外部的家伙来“制服”B。这就是上界和下界的思路。设(A, ≤)是偏序集B是A的子集。如果存在a∈A使得对任意x∈B都有x≤a那么称a是B的一个上界。如果存在a∈A使得对任意x∈B都有a≤x那么称a是B的一个下界。这里和最大元有三个明显区别。上界和下界不需要属于B它们只需要属于A就行。其次上界可以有很多个也可能一个都没有。第三上界的定义要求它和B中每个元素都可比这一点倒是和最大元类似。我讲课的时候喜欢举这个例子全班同学的身高构成偏序集某小组三个人是B那么年级里任何一个比这三个人都高的同学都是这个小组的上界。这个上界不一定是小组里的人可能是隔壁班的甚至可能是老师。4.2 上确界最精准的上界有了上界的概念自然想找“最小的那个上界”也就是最接近B的一个上界。这个“最小上界”就叫上确界记作sup B。严格定义是a是B的一个上界且对B的任意上界c都有a≤c那么a就是B的上确界。下确界对称b是B的一个下界且对B的任意下界c都有c≤b那么b就是B的下确界记作inf B。上确界和下确界跟最大元最小元的关系也要理清。如果B的最大元存在那最大元一定是B的上确界因为最大元本身就是B里的一个上界而上确界是“最小的上界”最大元已经是最接近B的了它必然是最小上界。反过来上确界不一定是最大元因为上确界可以不属于B。比如实数区间(0,1)它的上确界是1但1不在区间内所以不是最大元。4.3 哈斯图实战找上界、下界、确界的标准步骤哈斯图是偏序关系最直观的表示方式。画法原则很简单如果x≤y且x≠y就把y画在x的上方如果y覆盖x也就是x≤y且不存在z使得x≤z≤y就在x和y之间连一条线。覆盖关系就像“直接上级”中间的中间人都省略掉图形会干净很多。拿到一个哈斯图找B的上界我的标准流程是这样的在图上把B的所有元素圈出来。从这些元素同时出发顺着边往上走凡是能同时从所有B元素出发到达的节点就是上界。在上界集合里找“最低”的那个也就是能顺着边往下到达其他所有上界的节点那就是上确界。下界和上界完全对称只是方向换成往下走然后在所有下界里找“最高”的那个就是下确界。举个具体的例子。考虑偏序集A {1, 2, 3, 4, 6, 8, 12}偏序关系为整除取B {2, 3}。2和3的上界是谁6能被2和3整除吗2整除6、3整除6所以6是一个上界12同样也能被2和3整除也是上界。上界集合是{6, 12}。其中6小于12按“整除即小于”的规定6是6和12之间的较小者因此上确界是6。下界呢能被2和3整除的数就是同时整除2和3那就是最大公约数gcd(2,3)11整除2且1整除3所以1是唯一的……等等严格说下界是可以被2和3“整除的数”不对下界的定义是a≤x对所有x∈B成立即a整除2且a整除3。满足这个条件的a只有1可能还有谁0在这里不在A中负数不在A中所以下界就是{1}下确界也是1。再看一个更复杂的。取B {4, 6}在同一个偏序集A {1, 2, 3, 4, 6, 8, 12}里。上界谁同时能被4和6整除12能所以12是上界8不能被6整除排除其他更小更不可能。所以上界只有{12}上确界就是12。下界谁能同时整除4和61可以2可以2整除4且2整除63不能3不整除44不能4不整除6。所以下界集合是{1, 2}。在这两个下界里谁更大2比1大1整除2所以下确界是2。这个例子很好地展示了“上确界不是交集”这种认知上的陷阱上确界并不是求两个数里较大的数而是求最小公倍数式的操作下确界也不是求较小的数而是求最大公约数式的操作。4.4 上确界一定存在吗看实数集例子上确界不是对任意偏序集和任意子集都存在的。比如在有理数集Q上取B {x ∈ Q | x² 2}这个集合的上确界是√2但√2不是有理数不在Q里所以B在Q中根本没有上确界。而如果偏序集本身是所有实数R那上确界就存在了这正是实数完备性的核心内容。在实际问题中确界是否落在集合内部决定了我们要不要单独处理它。比如最优化问题里如果最优值能取到那它对应的就是最大元如果只能无限逼近但取不到那它对应的就是上确界而非最大元。这一点在很多算法分析中格外重要。5. 常见误区、答题模板与自测练习5.1 五个高频错误逐个排雷错误一混用最大元和极大元。这是重灾区。我反复提醒学生做题时先问自己一句“这个元素需要和集合里所有元素都可比吗”最大元需要极大元不需要。看集合内是否存在不可比的元素如果有极大元就可能不是一个而是多个。错误二找上界时忘记上界可以不属于B。很多初学者找上界只会在B里找结果找半天找不到。上界定义说的是a∈A不是a∈B一定要看清楚A是什么。错误三认为上确界一定是极大元。上确界可以不在B中当然谈不上是B的极大元它只能在A这个更大的偏序集里讨论。如果上确界恰好属于B那它确实会成为B的最大元但这不是必然的。错误四在无限集合里默认极大元存在。无限偏序集完全可能没有极大元比如正整数整除关系中每个元素都能被自己的倍数“压住”。这个问题要特别警惕因为很多题目默认集合有限做多了容易产生错误的惯性。错误五画哈斯图时把不可比元素连上线。哈斯图只画覆盖关系不可比的元素不能连线。我见过很多同学在图上把所有“在上面的”元素都连起来结果图变成了一个网状完全看不出层级结构。5.2 一套完整的做题流程直接照着用根据我的经验面对“求偏序集中的最大元、最小元、极大元、极小元、上下界、上下确界”这类题目最稳妥的顺序是这样的。第一步把偏序关系搞清楚确定符号是“≤”真实含义是整除、包含、还是数值比较。这一步错后面全错。第二步画哈斯图或者脑子里过一遍覆盖关系。动手画永远比空想靠谱画图时先找出所有覆盖对再逐层排列。第三步找最大元和最小元。看有没有一个元素能顺着图中的连线到达B中所有其他元素。能就有不能就没有。对极大元和极小元就反过来看哪些元素没有箭头通向其他更大的元素那些就是极大元。第四步找上界下界。从B中所有元素同时出发向外扩展到整个A看哪些元素能同时覆盖所有B元素上界。再反过来看哪些元素能被所有B元素覆盖下界。第五步在上界集合里找最小值在下界集合里找最大值那才是上确界和下确界。这一步最容易省略很多人找到上界就停了不排序导致确界算不出来。整个过程只要按这个顺序走不出意外十分钟内能解决一道标准题。5.3 可以自己验证的一组自测题我想留几个题目你做完之后可以对照一下答案检查自己是否真的掌握了这套知识。题目一设A {1, 2, 3, 4, 5, 6, 10, 12, 20, 30, 60}偏序关系为整除求A的最大元、最小元、极大元、极小元。题目二在题目一的偏序集A中取B {2, 3, 5}求B的所有上界、下界、上确界、下确界。题目三在题目一的偏序集A中取B {4, 6, 10}求B的所有上界、下界、上确界、下确界。题目四考虑由集合X的幂集P(X)构成的偏序集偏序为集合包含取X {a, b, c}令B {{a}, {b}}求B的所有上界、下界、上确界、下确界以及最大元、最小元、极大元、极小元。第一个题目的答案是最大元60最小元1极大元60最大元就是极大元极小元1。第二个题目B的上界是{6, 12, 30, 60}这里要注意2和3的最小公倍数是6凡是6的倍数都是上界在A中6、12、30、60都能被2和3整除所以上界是{6, 12, 30, 60}上确界6下界是{1}下确界1。第三个题目4、6、10的最小公倍数是60所以上确界60上界只有{60}最大公约数是2所以下确界2下界{1, 2}。第四个题目B {{a}, {b}}所有包含{a}和{b}的集合都是上界也就是{a,b}和{a,b,c}上确界是{a,b}能被两者包含的集合只有∅所以下界是{∅}下确界是∅。最大元不存在最小元不存在极大元是{a}和{b}极小元同样是{a}和{b}。你可以拿自己的结果对照一下如果都对了说明这些概念在你心里基本建立起来了。写到最后的一些经验我带过很多届学生发现一个现象凡是能把最大元和极大元的关系用自己的话讲清楚的人后面学格论、完备性、拓扑排序都特别顺。凡是只能背定义的碰到稍微变形的题目就会卡住。所以建议你学这一节时别急着记结论先拿三四个不同的例子反复画哈斯图把每个概念在同一张图上标出来。真正动手画上几遍之后会发现这些问题不过是一张图上不同位置的节点而已没有那么玄乎。我个人的一个小技巧是把极大元想象成“山脊上那些没有更高峰的山头”把最大元想象成“这群山里最高的那座主峰”。如果不只一座山头同高且互不相连那它们都是极大元但主峰最大元就不存在。这个类比虽然朴素但真的很管用尤其是考试时脑子发懵的时候回到这个画面里想一想答案往往就出来了。
偏序关系全解析：从最大元到上确界，一张哈斯图理清九个核心概念
偏序关系这块内容我见过太多人挂在半路上。原因不是难而是概念一次性冒出来太多偏序、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界一口气九个术语砸过来谁扛得住更麻烦的是最大元和极大元听起来几乎一模一样但意思差之千里上界和上确界又多了一层“精确”的关系光靠记定义根本分不清。而且这东西不是纯数学玩具它在数据库设计、编译器类型推导、任务调度、知识图谱的层级结构里都实打实地在用。这篇内容我打算用一套贯穿始终的例子把上面所有概念串起来配合哈斯图的读法告诉你每个定义到底在描述什么、找的时候从哪里下手、考试和实际应用里最容易踩哪些坑。看完你至少能达到一个标准给一个偏序集和它的子集你能在五分钟内把这些元、界、确界全部找齐并且每一条都能说出依据。1. 偏序关系的基本规则先搞清楚“≤”到底在说什么1.1 偏序关系不是“小于等于”很多初学者看到偏序关系里的符号“≤”第一反应就是算术里的小于等于。这既是方便之处也是最大的坑。方便在于所有和偏序有关的论证都可以借用“≤”这个符号的直觉坑在于真实的偏序关系压根不限于数字比较元素的顺序、集合的包含、任务的先后依赖全部可以构成偏序关系。我在实际教学中喜欢用“家族辈分”来打比方。假设一个家族里定义关系“a领先b”表示a是b的祖先或者a和b是同一个人。你会发现这个关系满足三条规律一个人一定是自己的祖先自反如果a是b的祖先b又是a的祖先那a和b只能是一个人反对称如果a是b的祖先b是c的祖先那么a一定是c的祖先传递。这三条规律组合在一起就是偏序关系。形式化的定义是这样的设R是集合A上的一个二元关系如果R满足自反性、反对称性、传递性那么R就是一个偏序关系通常记作“≤”而(A, ≤)称为偏序集。注意这里的“≤”已经不是一个具体的算术符号了它只是一个抽象的关系记号。在具体例子里它可能表示“整除”、“包含”、“先于”等等。1.2 自反、反对称、传递三个条件逐个拆解自反性对任意x∈A都有x≤x。意思是一个元素总能和自己比较而且结果是“不落后于自己”。在整除关系里6整除6成立在集合包含关系里集合A包含A自身成立。这个性质比较直观一般不会出错。反对称性对任意xy∈A如果x≤y且y≤x那么xy。这条是偏序关系的灵魂也是和“等价关系”分道扬镳的地方。等价关系要求对称也就是a和b等价时b和a也等价而偏序关系强调的是“谁在前、谁在后”如果有两个元素互相“不大于对方”那就说明它俩根本就是同一个元素。传递性如果x≤y且y≤z那么x≤z。这条的重要性在于它决定了我们能不能通过“中间人”来推理。比如在任务依赖关系中任务A必须在B之前完成B必须在C之前完成那么A必须在C之前完成。如果不满足传递性整个偏序结构就塌了也没法画成层级图。很多人会把反对称性和“不能双向比较”混为一谈这是错误的理解。反对称性没有禁止x≤y和y≤x同时成立它只规定了同时成立的结果xy。换句话说同一个元素当然可以双向比较但不同元素之间不能互相“领先”。1.3 偏序 vs 全序 vs 等价关系偏序和全序的差别用一个词概括就是“可比性”。偏序集里任意两个元素不一定能比较比如整除关系下2和3谁大谁小2不整除33也不整除2两者不可比。但实数集上通常的“≤”任何两个数都能比出高低这就是全序。全序关系一定是偏序关系但偏序关系不一定是全序关系。这个逻辑关系就像“正方形是矩形但矩形不一定是正方形”一样。如果你在写代码处理数据优先级遇到的是全序直接sort就能解决遇到的是偏序就必须用拓扑排序那一套这也是偏序关系在计算机领域最经典的应用。等价关系则是另一套逻辑。等价关系满足自反、对称、传递注意这里没有反对称而是要求对称。等价关系是把元素“归类”偏序关系是把元素“排序”两者出发点完全不同。如果拿集合打比方等价关系看的是“哪些元素属于同一类”偏序关系看的是“哪些元素包含在哪些里面”。2. 最大元、最小元全局第一名的诞生条件2.1 最大元和最小元的定义与判定方法设(A, ≤)是一个偏序集B是A的一个子集。如果存在一个元素b∈B使得对任意x∈B都有x≤b那么b就是B的最大元。同理如果存在一个元素b∈B使得对任意x∈B都有b≤x那么b就是B的最小元。注意三个关键点。第一最大元和最小元必须属于B本身不能跑到集合外面去找。第二它必须和B中每一个元素都能比较而且总是“大于等于”它们也就是所有元素的共同“天花板”。第三由于偏序关系不保证任意两元素可比最大元的存在性其实是很苛刻的。判定方法其实很机械遍历B中所有元素逐个检查它和其他元素是否都满足x≤b。这个步骤用哈斯图看更直观——最大元就是图中位于所有B中元素“上方”的那个点而且必须从它出发能顺着边沿到达所有其他B中的点。2.2 最大元、最小元的唯一性证明思路最大元如果存在一定只有一个。这个结论课本上会证明我这里说一个更直观的理解方式。假设B里有两个不同的最大元b1和b2根据最大元的定义b1要满足x≤b1对一切x∈B成立特别地取xb2就有b2≤b1同理b2是最大元所以b1≤b2。两个不等式同时成立由反对称性立刻推出b1b2。所以最大元要么不存在要么只有一个绝无可能同时出现两个不同的最大元。最小元的唯一性证明完全对称把符号反过来就行。这个唯一性结论在做题时非常有用一旦你找到了一个最大元就可以停手了不用再找第二个。2.3 全序集中最大元什么时候不存在很多人一开始以为任何有限集合都有最大元这个直觉只对全序集成立。在偏序集里最大元非常容易“缺席”。最典型的一个例子在正整数集合上定义整除关系取子集{2, 3, 5}。2和3不可比、3和5不可比、5和2不可比所以这个集合里没有任何一个元素能同时大于等于其他两个元素。最大元不存在最小元自然也不存在。再看一个例子集合{2, 3, 4, 6}在整除关系下4和6谁大4不整除66也不整除4所以没有最大元但2能整除4和62整除自己却无法和3比较大小2不整除3所以2也不是最小元。这个例子里最大元没有最小元也没有但极大元和极小元都存在。这就是下一节要讲的内容。3. 极大元、极小元局部没有更强的对手3.1 极大元、极小元的定义局部比较最大元要求的是“比所有元素都大”极大元的要求则宽松得多在集合B中不存在任何一个元素x使得b≤x且b≠x。换句话说在B里面你找不到一个严格比它大的元素它就是极大元。极小元对称在B中不存在严格比它小的元素。注意极大元不需要和B中所有元素都可比。它只需要保证“没有元素能压过它”。这就像一个班里如果两个同学的成绩没法直接比较比如分属文理科不同评分体系那他们各自在自己体系里可能是最高分两人都是“极大元”。最大元一定是极大元但极大元不一定是最大元。这条逻辑链要记牢。最大元要求“赢过所有人”极大元只要求“没人赢过我”显然后者更容易满足所以极大元可能有很多个最大元最多一个。3.2 用{2, 3, 5}这个例子彻底区分最大元和极大元我们回到整除关系下的集合{2, 3, 5}。这个集合里每个元素之间都不可比所以对2来说找遍整个集合没有任何一个元素比它“严格大”3和5都是不可比不算严格大所以2是极大元。同理3和5也都是极大元。但最大元呢必须要有一个元素同时大于等于2、3、5这里显然谁都不满足所以最大元不存在。反过来看{2, 4, 6, 12}这个整除关系集合。12能整除谁12整除自己也能被2、4、6整除也就是说2≤12、4≤12、6≤12都成立同时12整除12所以12是最大元同时也是极大元。这个例子里极大元只有12一个2还能找到严格比它大的吗能4、6、12都可以所以2不是极大元。4能找到严格比它大的吗12可以所以4也不是。6同理可以被12压住所以不是。可见最大元存在时极大元就是最大元本人。真正有意思的是最大元不存在但极大元存在的情况比如{2, 3, 4, 6}在整除关系下2不整除33不整除24不整除66不整除4所以极大元是谁4在集合里没有严格比4大的元素6和它不可比2和3都比它小所以4是极大元。6同理也是极大元。3呢没有严格比3大的元素4不整除3但是也不被3整除不可比6能被3整除所以6严格大于3那3就不是极大元。2呢4、6都严格比2大所以2不是极大元。最终极大元是4和6最大元不存在。这是一个值得反复琢磨的例子。3.3 有限偏序集一定有极大元吗答案是非空有限偏序集一定存在至少一个极大元也一定存在至少一个极小元。这个结论可以用归纳法严格证明直观上也很好理解从任意一个元素出发如果它不能继续往上走那它已经是极大元如果它能往上走就走一步接着检查因为集合有限不可能无穷尽地往上走最终必然停在一个“上不去”的元素上那就是极大元。但是无限偏序集就不一定了。比如正整数集合带上通常的“≤”关系这是一个全序集没有最大元每个数都能找到比它更大的数但有最小元1。反过来如果定义关系为“≥”那就变成没有最小元但有最大元1。再比如全体正整数在整除关系下1是最小元但极大元一个都没有因为每个正整数n都能找到严格大于它的数比如2n而且n整除2n。这个例子说明无限集里极大元可能完全消失做题时一定要先确认集合是否有限。4. 上界、下界与上确界、下确界站在子集的视角看“天花板”4.1 上界和下界的定义最大元和极大元讨论的是集合内部的“王者”但有时候我们需要跳出集合B到整个偏序集A里面去找外部的家伙来“制服”B。这就是上界和下界的思路。设(A, ≤)是偏序集B是A的子集。如果存在a∈A使得对任意x∈B都有x≤a那么称a是B的一个上界。如果存在a∈A使得对任意x∈B都有a≤x那么称a是B的一个下界。这里和最大元有三个明显区别。上界和下界不需要属于B它们只需要属于A就行。其次上界可以有很多个也可能一个都没有。第三上界的定义要求它和B中每个元素都可比这一点倒是和最大元类似。我讲课的时候喜欢举这个例子全班同学的身高构成偏序集某小组三个人是B那么年级里任何一个比这三个人都高的同学都是这个小组的上界。这个上界不一定是小组里的人可能是隔壁班的甚至可能是老师。4.2 上确界最精准的上界有了上界的概念自然想找“最小的那个上界”也就是最接近B的一个上界。这个“最小上界”就叫上确界记作sup B。严格定义是a是B的一个上界且对B的任意上界c都有a≤c那么a就是B的上确界。下确界对称b是B的一个下界且对B的任意下界c都有c≤b那么b就是B的下确界记作inf B。上确界和下确界跟最大元最小元的关系也要理清。如果B的最大元存在那最大元一定是B的上确界因为最大元本身就是B里的一个上界而上确界是“最小的上界”最大元已经是最接近B的了它必然是最小上界。反过来上确界不一定是最大元因为上确界可以不属于B。比如实数区间(0,1)它的上确界是1但1不在区间内所以不是最大元。4.3 哈斯图实战找上界、下界、确界的标准步骤哈斯图是偏序关系最直观的表示方式。画法原则很简单如果x≤y且x≠y就把y画在x的上方如果y覆盖x也就是x≤y且不存在z使得x≤z≤y就在x和y之间连一条线。覆盖关系就像“直接上级”中间的中间人都省略掉图形会干净很多。拿到一个哈斯图找B的上界我的标准流程是这样的在图上把B的所有元素圈出来。从这些元素同时出发顺着边往上走凡是能同时从所有B元素出发到达的节点就是上界。在上界集合里找“最低”的那个也就是能顺着边往下到达其他所有上界的节点那就是上确界。下界和上界完全对称只是方向换成往下走然后在所有下界里找“最高”的那个就是下确界。举个具体的例子。考虑偏序集A {1, 2, 3, 4, 6, 8, 12}偏序关系为整除取B {2, 3}。2和3的上界是谁6能被2和3整除吗2整除6、3整除6所以6是一个上界12同样也能被2和3整除也是上界。上界集合是{6, 12}。其中6小于12按“整除即小于”的规定6是6和12之间的较小者因此上确界是6。下界呢能被2和3整除的数就是同时整除2和3那就是最大公约数gcd(2,3)11整除2且1整除3所以1是唯一的……等等严格说下界是可以被2和3“整除的数”不对下界的定义是a≤x对所有x∈B成立即a整除2且a整除3。满足这个条件的a只有1可能还有谁0在这里不在A中负数不在A中所以下界就是{1}下确界也是1。再看一个更复杂的。取B {4, 6}在同一个偏序集A {1, 2, 3, 4, 6, 8, 12}里。上界谁同时能被4和6整除12能所以12是上界8不能被6整除排除其他更小更不可能。所以上界只有{12}上确界就是12。下界谁能同时整除4和61可以2可以2整除4且2整除63不能3不整除44不能4不整除6。所以下界集合是{1, 2}。在这两个下界里谁更大2比1大1整除2所以下确界是2。这个例子很好地展示了“上确界不是交集”这种认知上的陷阱上确界并不是求两个数里较大的数而是求最小公倍数式的操作下确界也不是求较小的数而是求最大公约数式的操作。4.4 上确界一定存在吗看实数集例子上确界不是对任意偏序集和任意子集都存在的。比如在有理数集Q上取B {x ∈ Q | x² 2}这个集合的上确界是√2但√2不是有理数不在Q里所以B在Q中根本没有上确界。而如果偏序集本身是所有实数R那上确界就存在了这正是实数完备性的核心内容。在实际问题中确界是否落在集合内部决定了我们要不要单独处理它。比如最优化问题里如果最优值能取到那它对应的就是最大元如果只能无限逼近但取不到那它对应的就是上确界而非最大元。这一点在很多算法分析中格外重要。5. 常见误区、答题模板与自测练习5.1 五个高频错误逐个排雷错误一混用最大元和极大元。这是重灾区。我反复提醒学生做题时先问自己一句“这个元素需要和集合里所有元素都可比吗”最大元需要极大元不需要。看集合内是否存在不可比的元素如果有极大元就可能不是一个而是多个。错误二找上界时忘记上界可以不属于B。很多初学者找上界只会在B里找结果找半天找不到。上界定义说的是a∈A不是a∈B一定要看清楚A是什么。错误三认为上确界一定是极大元。上确界可以不在B中当然谈不上是B的极大元它只能在A这个更大的偏序集里讨论。如果上确界恰好属于B那它确实会成为B的最大元但这不是必然的。错误四在无限集合里默认极大元存在。无限偏序集完全可能没有极大元比如正整数整除关系中每个元素都能被自己的倍数“压住”。这个问题要特别警惕因为很多题目默认集合有限做多了容易产生错误的惯性。错误五画哈斯图时把不可比元素连上线。哈斯图只画覆盖关系不可比的元素不能连线。我见过很多同学在图上把所有“在上面的”元素都连起来结果图变成了一个网状完全看不出层级结构。5.2 一套完整的做题流程直接照着用根据我的经验面对“求偏序集中的最大元、最小元、极大元、极小元、上下界、上下确界”这类题目最稳妥的顺序是这样的。第一步把偏序关系搞清楚确定符号是“≤”真实含义是整除、包含、还是数值比较。这一步错后面全错。第二步画哈斯图或者脑子里过一遍覆盖关系。动手画永远比空想靠谱画图时先找出所有覆盖对再逐层排列。第三步找最大元和最小元。看有没有一个元素能顺着图中的连线到达B中所有其他元素。能就有不能就没有。对极大元和极小元就反过来看哪些元素没有箭头通向其他更大的元素那些就是极大元。第四步找上界下界。从B中所有元素同时出发向外扩展到整个A看哪些元素能同时覆盖所有B元素上界。再反过来看哪些元素能被所有B元素覆盖下界。第五步在上界集合里找最小值在下界集合里找最大值那才是上确界和下确界。这一步最容易省略很多人找到上界就停了不排序导致确界算不出来。整个过程只要按这个顺序走不出意外十分钟内能解决一道标准题。5.3 可以自己验证的一组自测题我想留几个题目你做完之后可以对照一下答案检查自己是否真的掌握了这套知识。题目一设A {1, 2, 3, 4, 5, 6, 10, 12, 20, 30, 60}偏序关系为整除求A的最大元、最小元、极大元、极小元。题目二在题目一的偏序集A中取B {2, 3, 5}求B的所有上界、下界、上确界、下确界。题目三在题目一的偏序集A中取B {4, 6, 10}求B的所有上界、下界、上确界、下确界。题目四考虑由集合X的幂集P(X)构成的偏序集偏序为集合包含取X {a, b, c}令B {{a}, {b}}求B的所有上界、下界、上确界、下确界以及最大元、最小元、极大元、极小元。第一个题目的答案是最大元60最小元1极大元60最大元就是极大元极小元1。第二个题目B的上界是{6, 12, 30, 60}这里要注意2和3的最小公倍数是6凡是6的倍数都是上界在A中6、12、30、60都能被2和3整除所以上界是{6, 12, 30, 60}上确界6下界是{1}下确界1。第三个题目4、6、10的最小公倍数是60所以上确界60上界只有{60}最大公约数是2所以下确界2下界{1, 2}。第四个题目B {{a}, {b}}所有包含{a}和{b}的集合都是上界也就是{a,b}和{a,b,c}上确界是{a,b}能被两者包含的集合只有∅所以下界是{∅}下确界是∅。最大元不存在最小元不存在极大元是{a}和{b}极小元同样是{a}和{b}。你可以拿自己的结果对照一下如果都对了说明这些概念在你心里基本建立起来了。写到最后的一些经验我带过很多届学生发现一个现象凡是能把最大元和极大元的关系用自己的话讲清楚的人后面学格论、完备性、拓扑排序都特别顺。凡是只能背定义的碰到稍微变形的题目就会卡住。所以建议你学这一节时别急着记结论先拿三四个不同的例子反复画哈斯图把每个概念在同一张图上标出来。真正动手画上几遍之后会发现这些问题不过是一张图上不同位置的节点而已没有那么玄乎。我个人的一个小技巧是把极大元想象成“山脊上那些没有更高峰的山头”把最大元想象成“这群山里最高的那座主峰”。如果不只一座山头同高且互不相连那它们都是极大元但主峰最大元就不存在。这个类比虽然朴素但真的很管用尤其是考试时脑子发懵的时候回到这个画面里想一想答案往往就出来了。
