序关系重点课件.ppt

《序关系重点课件.ppt》由会员分享，可在线阅读，更多相关《序关系重点课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.12序关系序关系定义：定义：设设R是非空集合是非空集合A上的关系，上的关系，若若R是自反、反对称和传递的，是自反、反对称和传递的，则称则称R为为A上的偏序关系。称有上的偏序关系。称有 序偶序偶为偏序集。为偏序集。一、偏序关系一、偏序关系偏序关系一般记为偏序关系一般记为 偏序集一般记为偏序集一般记为 xy (读作小于等于读作小于等于)例：例：证明集合证明集合A=2,3,6,12,24,36上上 的整除关系是偏序关系。的整除关系是偏序关系。证明：证明：R=|x,y A,x|yx|y表示：表示：x整除整除y（y被被x整除）整除）对于任意的对于任意的x Ax|x R R是自反的是自反的 对于任意的

2、对于任意的x,y A，若若 x|y 且且 y|x 则则 x=y 即：即：若若 R且且 R则则x=y R是反对称的是反对称的 对于任意的对于任意的,R，有有x|y 且且 y|z 有有x|z R R是传递的是传递的综合综合、，R是偏序关系是偏序关系例例:(1)集合族上集合族上:子集关系、包含关系子集关系、包含关系 (2)正自然数集正自然数集N+上上:整除关系、整倍数关系整除关系、整倍数关系 (3)实数集实数集R上上:小于等于关系、大于等于关系小于等于关系、大于等于关系 若若是是A上的偏序关系，上的偏序关系，则则-1(记记)也是也是A上的偏序关系上的偏序关系,和和 都是偏序集。都是偏序集。定义：定义

3、：设设是非空集合是非空集合A上的偏序关上的偏序关 系，对于系，对于x,y A:若有若有 或或 ，则称则称 x 与与 y 可比可比若有若有 且且 ，则称则称 x 与与 y 不可比不可比若有若有 且且 x y，则称则称 xy（读作（读作小于小于）在偏序集在偏序集 中，中，x,y A，恰符合以下三种情况之一：，恰符合以下三种情况之一：(1)x与与y 不可比不可比 (2)xy(或或 yx)(3)x=y例：例：2,3,6,12,24,36 上的整除关系上的整除关系:(1)2与与3、24与与36不可比不可比 (2)6与与6、6与与12、6与与3可比可比 (3)66、612、36 66、612、36 有穷偏

4、序集的关系图，有穷偏序集的关系图，可以简化为哈斯图。可以简化为哈斯图。二、哈斯图二、哈斯图定义：定义：设设 为偏序集，对于任意为偏序集，对于任意x,y A，若，若xy，且不存在，且不存在 z A，使得使得 xzy，则称，则称 y 盖住盖住 x。例：例：2,3,6,12,24,36 上的整除关系上的整除关系:6|36，636，但，但36没有盖住没有盖住6，36盖住盖住12，12盖住盖住6 哈斯图哈斯图的画法：的画法：对于任意对于任意x,y A，若，若xy，则，则 将将x画在画在y的下方的下方 若若y盖住盖住x，则用一条线段连接，则用一条线段连接 x和和y 对于有穷偏序集，哈斯图是关系图的简化。对

5、于有穷偏序集，哈斯图是关系图的简化。例：例：2,4,6,8上的整除关系上的整除关系44268682例：例：2,3,6,12,24,36 上有上有整除关系整除关系 和和整倍数关系整倍数关系,画出哈斯图。画出哈斯图。236361224243361262例：例：集合集合A=a,b,c,P(A)上有上有子集关系子集关系,画出哈斯图。画出哈斯图。a,b,cbca,ba,cb,c a例：例：根据哈斯图，根据哈斯图，写出偏序关系。写出偏序关系。4268解：解：A=2,4,6,8R=,A上的整倍数关系上的整倍数关系定义：定义：设设 为偏序集为偏序集,若对任若对任 意的意的 x,y A，x与与y 都是可比都是可

6、比 的，则称的，则称 为为 A 上的上的全序关全序关 系系，称，称 为为全序集全序集。三、全序关系三、全序关系全序关系一定是偏序关系，偏序关系全序关系一定是偏序关系，偏序关系不一定是全序关系。不一定是全序关系。例：例：2,4,6,8 上的上的整除关系整除关系不是全序不是全序 关系，关系，小于等于关系小于等于关系是全序关系。是全序关系。42688642例：例：(1)实数集上的小于等于关系、大于实数集上的小于等于关系、大于 等于关系：等于关系：是是全序关系全序关系(2)集合族上的子集关系、包含关系：集合族上的子集关系、包含关系：不是不是全序关系全序关系(3)正自然数集上的整除关系、整倍正自然数集上

7、的整除关系、整倍 数关系：数关系：不是不是全序关系全序关系 最小元最小元 最大元最大元极小元极小元 极大元极大元下界下界 上界上界下确界下确界 上确界上确界四、偏序集中一些特殊元素四、偏序集中一些特殊元素定义：定义：设设 为偏序集，为偏序集，B A：若若 y B，使得，使得 x(x B yx)，则称则称 y 是是 B 的的最小元最小元 若若 y B，使得，使得 x(x B xy)，则称则称 y 是是 B 的的最大元最大元 若若 y B，使得，使得 x(x B xy)，则称则称 y 是是 B 的的极小元极小元 若若 y B，使得，使得 x(x B yx)，则称则称 y 是是 B 的的极大元极大元

8、例：例：2,3,6,12,24,36 上的整除关系，上的整除关系，求求 2,3,6,12 的最元、极元。的最元、极元。236361224最小元：无最小元：无最大元：最大元：12极小元：极小元：2，3极大元：极大元：12最元与极元是有区别的：最元与极元是有区别的：最元与最元与 B 中其它元素都可比，中其它元素都可比，是是 B 中最小中最小(大大)的元素的元素 极元不一定与极元不一定与 B 中元素都可比，中元素都可比，只要没有比它小只要没有比它小(大大)的元素，的元素，它就是极小它就是极小(大大)元元定理：定理：偏序集的非空子集，偏序集的非空子集，可能没有最元，若有必唯一，可能没有最元，若有必唯一

9、，可能没有极元，若有未必唯一可能没有极元，若有未必唯一。定义：定义：设设 为偏序集，为偏序集，B A：若若 y A，使得，使得 x(x Byx)，则称则称 y是是B的的下界下界 若若 y A，使得，使得 x(x Bxy)，则称则称 y是是B的的上界上界 令令 C=y|y是是B的下界的下界，则称则称 C的最大元的最大元 是是B的的下确界下确界 令令 C=y|y是是B的上界的上界，则称则称 C的最小元的最小元 是是B的的上确界上确界例：例：2,3,6,12,24,36 上的整除关系，上的整除关系，求求 2,3,6,12 的界、确界。的界、确界。236361224下界：无下界：无上界：上界：12,2

10、4,36下确界：无下确界：无上确界：上确界：12说明：说明：B的界、确界在的界、确界在 A 的范围中，的范围中，可能在可能在B中，也可能不在中，也可能不在B中；中；下确界是下界中的最大，下确界是下界中的最大，上确界是上界中的最小。上确界是上界中的最小。定理：定理：偏序集的非空子集，偏序集的非空子集，可能没有确界，若有必唯一，可能没有确界，若有必唯一，可能没有界，若有未必唯一可能没有界，若有未必唯一。定理：定理：对偏序集的非空子集，对偏序集的非空子集，最小元一定是下界，且是下确界；最小元一定是下界，且是下确界；下界、下确界不一定是最小元。下界、下确界不一定是最小元。最大元一定是上界，且是上确界；

11、最大元一定是上界，且是上确界；上界、上确界不一定是最大元。上界、上确界不一定是最大元。没有最元、极元、确界、界没有最元、极元、确界、界例：例：整数集整数集 Z 上的上的 小于等于关系小于等于关系 给定给定 Z 的奇数子集的奇数子集 考虑其最元、极元、确界、界考虑其最元、极元、确界、界定义：定义：设设 为偏序集为偏序集,若若A的的任意任意非空子集都有最小元，则称非空子集都有最小元，则称为为A上的上的良序关系良序关系，称，称为为良序集良序集。五、良序关系五、良序关系例：例：是良序集，是良序集，、不是良序集不是良序集 定理：定理：良序集一定是全序集。良序集一定是全序集。有限的全序集一定是良序集有限的

12、全序集一定是良序集 (无限的全序集不一定是良序集无限的全序集不一定是良序集)。证明：证明：证明：证明：证明良序集一定是全序集：证明良序集一定是全序集：良序集良序集的任意非空子集都有最小元，的任意非空子集都有最小元，则对于则对于A中中任意任意两个元素两个元素x,y，x,y有最小元有最小元x与与y可比可比是全序集是全序集 证明有限的全序集一定是良序集：证明有限的全序集一定是良序集：全序集全序集中，中，任意两个元素可比，任意两个元素可比，又又A是有限集合是有限集合 任意非空子集都有最小元任意非空子集都有最小元 是良序集是良序集 序关系，反映了集合中元素的序关系，反映了集合中元素的顺序顺序性。性。小结：小结：P146 3-12 (5)(7)作业作业7：