图3-14
例3.10.7 设A?{2,3,6,12,24,36}，A上的整除关系“|”是一偏序关系，其哈斯图如图3-15所示。
图3-15
3.10.3 偏序集中特殊位置的元素
从偏序集的哈斯图可以看到偏序集中各个元素之间具有分明的层次关系，则其中必有一些处于特殊位置的元素。下面讨论偏序集中具有特殊位置的元素。
定义3.10.3 设A,?是一个偏序集合，且B是A的子集，若有某个元素b?B，使得（1）
不存在x?B，满足b?x且b?x，则称b为B的极大元(Maximal Element)；
（2）不存在x?B，满足b?x且x?b，则称b为B的极小元(Minimal Element)；
109
（3）对每一个x?B有x?b，则称b为B的最大元(Largest Element)； （4）对每一个x?B有b?x，则称b为B的最小元(Smallest Element)。 例3.10.8 设A?{2,3,5,7,14,15,21}，其偏序关系
R?{2,14,3,15,3,21,5,15,7,14,7,21,2,2,3,3
5,5,7,7,14,14,15,15,21,21}
求B?{2,7,3,21,14}的极大元、极小元、最大元和最小元。
解 COV A?{2,14,3,15,3,21,5,15,7,14,7,21}，A,R的哈斯图如图3-16所示。
14 21 15 2 7 3 5 图3-16 故B的极小元集合是{2,7,3}，B的极大元集合为{14,21}，B无最大元，也无最小元。
例3.10.9 在例3.10.7中取B分别为A，{6,12}和{2,3,6}，则
集合 A {6,12} {2,3,6} 极大元 24,36 极小元 2,3 最大元 无 12 6 最小元 无 6 12 6 6 2,3 无
例3.10.10 在例3.10.6中的图3-22(c)所示的偏序集中，取B分别为P(S3)，{{a},{b},{c}}和{{a},{a,b}}，则
集合 P(S3) {{a},{b},{c}} {{a},{a,b}} 极大元 {a,b,c} {a},{b},{c} 极小元 ? {a},{b},{c} 最大元 {a,b,c} 最小元 ? 无 {a,b} 无 {a} {a,b} {a}
从上面的3个例子可以看出，最大（小）元和极大（小）元有如下性质： 定理3.10.1 设A,?为一偏序集且B?A，则
（1）B的最大（小）元必是B的极大（小）元，反之不然。
（2）B的最大（小）元不一定存在，若B有最大（最小）元，则必是唯一的。
（3）B的极大（小）元不一定是唯一的。当B?A时，则偏序集A,?的极大元即是哈斯图中最顶层的元素，其极小元是哈斯图中最底层的元素，不同的极小元或不同的极大元之间是
110
不可比较的。
证明 我们证明最大（小）元的唯一性。假定a和b都是B的最大元，则a?b且b?a，由?的反对称性，得到a?b。B的最小元情况与此类似。
定义3.10.4 设A,?为一偏序集，对于B?A，如有a?A，对B的任意元素x，都满足 （1）x?a，则称a为B的上界(Upper Bound)； （2）a?x，则称a为B的下界(Lower Bound)；
（3）a为B的上界，且对B的任一上界a?均有a?a?，则称a为B的最小上界（上确界）(Least Upper Bound)，记作LUBB；
（4）a为B的下界，且对B的任一下界a?，均有a??a，则称a为B的最大下界（下确界）(Greatest Lower Bound)，记为GLBB。
例3.10.11 在例3.10.7中取B分别为A，{6,12}和{2,3,6}，{12,24,36}和{24,36}，则
集合 A {6,12} {2,3,6} 上界 无 12,24,36 下界 无 2,3,6 上确界 无 12 6 下确界 无 6 6,12,24,36 无 2,3,6,12 2,3,6,12 无 12 12 {12,24,36} {24,36} 无 无 无 无 例3.10.12 在例3.10.6中的图3-22(c)所示的偏序集中，取B分别为P(S3)，{{a},{b},{c}}和{{a},{a,b}}，则
集合 P(S3) {{a},{b},{c}} {{a},{a,b}} 上界 {a,b,c} {a,b,c} 下界 ? ? 上确界 {a,b,c} {a,b,c} 下确界 ? ? {a} {a,b}，{a,b,c} ?，{a} {a,b}
从上面的两个例子可以看出，上(下)界和上(下)确界有如下性质： 定理3.10.2 设A,?为一偏序集且B?A，则
（1）B的上（下）界不一定存在，若存在，则不一定唯一，并且它们可能在B中，也可能在B外；
（2）B的上（下）确界不一定存在，若存在，必定是唯一的，并且若B有最大（小）元，则它必是B的上（下）确界。
3.10.4 两种特殊的偏序集
1．全序
111
定义3.10.5 设A,?为一个偏序集，若对于任意a,b?A，必有a?b或b?a，则称A,?为全序集合或线序集合（有时也称为链），二元关系?称为全序关系或线序关系(Total Order Or Linear Order)。
例3.10.13 （1）定义在自然数集合N上的小于等于关系“?”是偏序关系，且对任意i,j?N，必有：i?j或j?i成立，故“?”是全序关系。
（2）实数集R上的小于等于关系“?”也是R上的一个全序关系。
（3）设A?{1,2,4,8,24,48}，则A上的整除关系是一个全序关系，其哈斯图如 图3-25所示。
图3-25 例3.10.13中（3）的哈斯图
（4）自然数集合N上的整除关系就仅是一个偏序而不是全序。 2.良序
定义3.10.6 设A,?为一个偏序集，若A的任意非空子集B均有最小元素，则称?为A上的一个良序(Well-ordered)，A,?称为良序集(Well-ordered Set)。
例如，（1）正整数集I??{1,2,3,?}上的小于等于关系是良序，即I?,?是良序集。 （2）In?{1,2,?,n}上的小于等于关系是良序，即In,?是良序集。
（3）整数集I和实数集R上的小于等于关系“?”不是良序关系（因为I或R本身无最小元）。
定理3.10.3 每一个良序集合，一定是全序集合。
证明 设A,?为良序集合，则对任意两个元素x,y?A可构成子集{x,y}，必存在最小元素，这个最小元素不是x就是y，因此一定有x?y或y?x。所以A,?为全序集。 注意：定理3.10.3的逆不成立 。 例如，整数集I和实数集R上的小于等于关系“?”是全序，但不是良序。但是我们有
定理3.10.4 每一个有限的全序集合，一定是良序集合。
证明 设A?{a1,a2,?,an}，且A,?是全序集合，现在假定A,?不是良序集合，那么必存在一个非空子集B?A，在B中不存在最小元素，由于B是一个有限集合，故一定可以找出两个元素x与y是无关的，由于A,?是全序集x,y?A，所以x,y必有关系，得出矛盾，故A,?必是良序集合。
112