单击此处编辑母版副标题样式*1单击此处编辑母版标题样式偏序关系l离散数学：第6讲上一讲内容的回顾l等价关系的定义l等价关系的关系图的特征l等价类定义非空集合A上等价关系R的等价类的性质商集l集合的划分l等价关系与集合划分的对应偏序关系l偏序关系与偏序集l拟序l哈斯图l偏序集中的特殊元素极大元与极小元最大元与最小元上(下)界与上(下)确界l全序l良序“字典顺序”l假设是集合A上的偏序关系，定义AA上的关系R如下： R iff. x1x2且x1 x2, 或者x1= x2且y1 y2易证R是AA上的偏序关系l给定有限字符集合，只要在上定义一个偏序关系，类似上述办法，就可以对任意正整数k,定义k(由中字符构成的长度为k的串的集合)上的偏序关系加以适当的技术处理，则容易定义+(由中字符构成的长度为任意正整数的串的集合)上的偏序关系：字典关系注意：在通常的字典关系中，任何两个元素均可比偏序集l定义了偏序的集合l表示：l例子：, 其中A是集合, N是自然数集，“|”是整除关系拟序l“小于”关系不是偏序，不满足自反性l拟序的定义：反自反、传递l拟序满足反对称性注意：实际上,不会同时出现哈斯图 l普通关系图当然可以表示偏序关系l哈斯图(Hasse) - 利用特定性质简化图示方法利用自反性省略环利用反对称性省略箭头利用传递性省略部分连线(a,b,c)上的包含关系a,b,ccbab,ca,ca,b912810115643211,2,.,12上的整除关系724846231211,2,3,4,6,8,12,24上的整除关系偏序集中的特殊元素 ：极大(小)l定义：x是偏序集中的极大元 iff. 对任意yA,若xy, 则x=yx是偏序集中的极小元 iff. 对任意yA,若yx, 则x=yl有关极大元与极小元的讨论有穷集合一定有极大(小)元不一定唯一一个元素可能兼为极大(小)元没比它更小(大)的了！偏序集中的特殊元素 ：最大(小)l定义：x是偏序集中的最大元 iff. 对任意yA,yxx是偏序集中的最小元 iff. 对任意yA, xyl有关最大元与最小元的讨论最大(小)元最多只有一个可能不存在。
它比谁都要小(大)！偏序集中的特殊元素 ：上(下)确界l定义上界：对于偏序集和A的子集B，若存在y,对B中任意元素x,均有xy,则y是B的上界上确界：如果B的上界构成的偏序集有最小元，则该最小元为B的上确界类似地可以定义下(确)界l有关上(下)界的讨论不一定存在上(下)界不一定唯一，但上(下)确界若存在，必唯一注意：上(下)确界即某个偏序集的最大(小)元从哈斯图看特殊元素最大/极大极小极小子集SS的上界的集合上确界全序l任何两个元素均可比的偏序称为“全序”，又称“线性序”例子：实数集上的“不大于”关系、基于拉丁字母表的字典顺序l链与反链设B是偏序集的一个子集假设B中任何两个元素均可比，则B构成一个链建设B中任何两个元素均不可比，则B构成一个反链l注意：所有链的集合或者所有反链的集合与集合包含关系也构成一个偏序集，因此可以讨论极大/极小、最大/最小链或反链偏序关系与等价关系l是否有可能一个关系既是偏序，又是等价关系？l任意非空集合A上的恒等关系IA = | aAl显然，IA满足自反性、对称性、反对称性、传递性，因此它是偏序，也是等价关系作为等价关系，其商集是a|aA作为偏序，它的任一链只含一个元素，而其最大反链即A本身。
有限偏序集中的链与反链.元素个数最多的反链，含k个元素a1a2aiak对i=1,2,k, 从ai开始可以依次构造元素尽可能多的链Li ,且Li中不含L1, Li-1中已有的元素必包含该偏序集中所有元素，为什么？关于整除关系的讨论l定义N-0上的关系R：aRb 当且仅当：存在tN-0，满足：at=b (通常记为a|b)lR是偏序关系l极大/极小元；最大最小元？l链的特征？l反链的特征？l在集合包含关系下讨论极大/极小链？“道是无序却有序”l自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链l你能证明吗？提示：建立nn的方阵，在i,j单元中放入自然数1,2,3,n2+1中的某一个，条件是在给顶排列中以该数为起点的严格递增链长度是i, 而严格递减链长度是j证明不可能有两个不同的数落在同一单元中道是无序却有序” 偏序模型l自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链l建立偏序集模型集合：A= |i=1,2,n2+1, 每个vi取1,2,n2+1中一个不同的值建立两个偏序关系：lR1: R1 iff. ij并且vivj lR2: R2 iff. ivj l问题：证明: 一定存在A的一个至少含n+1个元素的子集，它是R1的链或者R2的链。
注意：R1的链是R2反链，反之亦然良序l定义：给定集合A上的偏序，若A的任一非空子集均存在最小元素，则该偏序为良序l良序必为全序对任意a,bA, a,b必有最小元，则a,b一定可比l实际上，“反对称性+任一非空子集存在最小元”是“自反性+传递性+任何两个元素均可比”的充分条件自反性：对任意aA, a也必有最小元，即aa传递性：假设ab, bc, a, b, c的最小元素只能是a, 因此ac任何两个元素可比上面已证明关于次序关系的进一步讨论l全序是否一定是良序？l当A是无穷集合时，全序不一定是良序例如：, 任何开区间上没有最小元素l偏序、全序、良序的逆关系是否仍为偏序、全序和良序？l良序不一定保持例如作业lpp.140-45-50。