偏序

15.5偏序(partialorder)关系定义5.5.1设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作≤。序偶A,≤称为偏序集。设≤为偏序关系，如果x,y∈≤，则记作x≤y，读作“x小于或等于y”。注意这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。2例5.5.1实数集上的小于等于关系是偏序关系；集合A，P(A)上的包含关系是偏序关系；设Z+是正整数集合，a,b∈Z+，若a整除b，记为ab，则“整除关系”是Z+上的一个偏序关系。3例5.5.2设A={1,2,3,4,6,12}，则A，(为整除关系)是偏序集。4例5.5.2设A={1,2,3,4,6,12}，则A，(为整除关系)是偏序集。证明：＝{1,1,1,2,1,3,1,4,1,6,1,12,2,2,2,4,2,6,2,12,3,3,3,6,3,12,6,6,6,12,12,12}关系矩阵为关系图如5.5.1所示。111111010111001011000101000011000001显然，偏序关系“”具有自反、反对称和传递性，因此A，是偏序集。1234612图5.5.1关系示意图5偏序集的哈斯（Hasse）图定义5.5.2设A,≤是一个偏序集，若,xyA，xy，xy，且没有其它元素zA满足xzy,则称元素y盖住元素x。令COV(A)={x,yx,yA，y盖住x}，称COV(A)为A,≤的盖住关系。例5.5.3例5.5.2中，偏序集A,的盖住关系为COV(A)={1,2,1,3,2,4,2,6,3,6,4,12,6,12}6利用盖住关系作“≤”的哈斯(Hasse)图既简单又层次清楚。Hasse图的作图规则是：(1)用小圆点（或小圆圈）代表元素；(2)如果x≤y且xy，则将代表y的小圆点画在代表x的小圆点的上面；(3)如果x,yCOV(A)，则在x与y之间用直线连接。例5.5.4例5.5.3中偏序集A,的哈斯图为(图5.5.2)。1361242图5.5.2示意图例7例5.5.5设A={2,3,6,12,24,36}，是A上的整除关系，求偏序集A,的哈斯图。8例5.5.5设A={2,3,6,12,24,36}，是A上的整除关系，求偏序集A,的哈斯图。解：＝{2,2,2,6,2,12,2,24,2,36,3,3,3,6,3,12,3,24,3,36,6,6,6,12,6,24,6,36,12,12,12,24,12,36,24,24,36,36}偏序集A,的盖住关系为COV(A)={2,6,3,6,6,12,12,24,12,36}偏序集A,的哈斯图如图5.5.3所示。2436126239例5.5.6设Z是整数集，“≤”为数的小于或等于关系，则Z,≤的哈斯图如图5.5.4所示。10－1－22图5.5.4示意图例10偏序集中的特殊元定义5.5.3设A，≤为偏序集，B是A的子集，bB(1)如果在B中找不到x适合于xb且bx，即(()()())xxBbxxb，则称b是B的极大元。(2)如果在B中找不到x适合于xb且xb，即(()()())xxBxbxb，则称b是B的极小元。(3)如果任意xB都有xb，即(()())xxBxb，则称b是B的最大元。(4)如果任意xB都有bx，即(()())xxBbx，则称b是B的最小元。定理5.5.1设A，≤为偏序集，B是A的子集，若B有最大（最小）元，则必是唯一的。证明：假设a,b都是B的最大（最小）元，则必有ab和ba成立，由偏序关系“≤”的反对称性知，ab。11定义5.5.4设A，≤为偏序集，B是A的任意非空子集，(1)对任意xB,如果有aA，满足xa，即(()(()()))xxBaaAxa，则称a为B的上界。(2)对任意xB，如果有aA，满足ax，即(()(()()))xxBaaAax，则称a为B的下界。(3)设C={yy是B的上界}A，C的最小元称为B的最小上界（上确界）。(4)设C={yy是B的下界}A，C的最大元称为B的最大下界（下确界）。注意：上、下界不唯一，但上、下确界是唯一的。12例5.5.8设集合A={2,3,6,12,18,36}，偏序集的A，|哈斯图如图5.5.5所示。图5.5.5一个偏序集的哈斯图6分别是集合B1={2,3,6}A的上界；2,3分别是集合B2={2,3,6,12}A的下界；B4={3,6,12,18}A的最大下界(下确界)是3；B5={2,3,6}A的最小上界（上确界）是6。36181262313可比(1)x,y∈A，x＜yx≤y∧x≠y。(2)x,y∈A，x与y可比x≤y∨y≤x。在具有偏序关系的集合A中任取两个元素x和y，可能有下述几种情况发生：x＜y(或y＜x)，x＝y，x与y不是可比的。例如A＝{1，2，3}，≤是A上的整除关系，则有1＜2，1＜3，1=1，2=2，3=3，2和3不可比。14全序关系及其应用定义5.5.5设R为非空集合A上的偏序关系，如果x,y∈A，x与y都是可比的，则称R为A上的全序关系(或线序关系)。例如数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。整除关系一般来说不是全序关系，如集合{1,2,3}上的整除关系就不是全序关系，因为2和3不可比。15例题补充例画出偏序集{1,2,3,4,5,6,7,8,9}，R整除和P({a,b,c}),R的哈斯图。16例题补充例已知偏序集A,R的哈斯图如右图所示，试求出集合A和关系R的表达式。解答A={a,b,c,d,e,f,g,h}R={b,d,b,e,b,f,c,d,c,e,c,f,d,f,e,f,g,h}∪IA17偏序集中的特殊元素363242126B最大元最小元极大元极小元{2,3,6,12,24,36}{6,12}{2,3,6}{6}无无24,262,31261266无62,3666618例设偏序集A,≤如右图所示，求A的极小元、最小元、极大元、最大元。解答极小元：a,b,c,g极大元：a,f,h。没有最小元与最大元说明哈斯图中的孤立顶点既是极小元也是极大元。19上界与下界举例363242126B上界下界上确界下确界{2,3,6,12,24,36}{6,12}{2,3,6}{6}无无无无12,24,362,3,61266,12,24,36无6无6,12,24,362,3,666考虑右图中的偏序集。令B＝{b，c，d}，则B的下界和最大下界都不存在，上界有d和f，最小上界为d。