集合论第三课等价关系与偏序关系

1、2.6 等价关系与划分 定义2.12（划分） 设A是一个集合。Ai 是一组不同的集合, 且Ai , i=1, , n 。若A1 A2 An=A， Ai Aj=（i, j=1, n, ij），则称=A1, A2, , An是A的一个划分。其中每个Ai称为划分的一个块。显然，A的划分是2A的子集。 例2.21 设A=a, b, c，A的子集组成的以下集合(是2A的子集)，哪些是A的划分？ P=a,b, c S=a, b, c T=a, b, c U=a, c V=a, b, b, c W=a, b, a, c, c P, S, T是A的划分，其余不是A的划分。 2 划分的块数可以是有限的或无限的

2、例2.22：整数集I的划分: 1=E, O，其中E为偶数集，O为奇数集； 2=0, -1, 1, -2, 2, -3, 3, 也是I的一个划分。 定义2.13（等价关系） 设R是A上的二元关系，若R是自反的、对称的和传递的，则称R是A上的等价关系。若aRb，则称a与b等价。 例2.23 设A是一个学生集合, 定义A上二元关系R: R当且仅当a与b同年龄. R是等价关系.2.6 等价关系与划分 定义2.14（等价类） 设R是A上的等价关系，对于每个aA，与a等价的全体元素构成的集合称为由a生成的关于R的等价类，记为aR，即 aR =x | xA，xRa，a称为该等价类的代表元。 根据上下文可以确

3、定R时，将aR简记为a。 定义2.15（商集） 设R是A上的等价关系，关于R的全体等价类构成的集合称为A关于R的商集，记为A/R，即A/R=a | aA。2.6 等价关系与划分 定理2.13 设R是A上的等价关系，则（1）对任一aA，有aa；（2）对a, bA，如果aRb，则a=b;（3）对a, bA，如果R，则ab=;（4）aAa=A。/*（1）根据等价类的定义进行证明；*/证明：由于R是自反的，即aRa，所以aa。/*（2）基本法证明；*/证明：/*先证明ab*/ 对任一ca，有cRa，又由假设aRb，根据R的传递性，必有cRb，即cb，从而ab；/*再证明ba */ 对任一cb，有cRb

4、，又由假设aRb，根据R的传递性，必有cRa，即ca，从而ba； 所以a=b。/*（3）反证法证明；*/证明：已知R，如果ab; 假设cab, 则ca且cb, 从定义可知cRa，cRb。由R的对称性和传递性，必有aRb，导致矛盾。所以ab= 。/*（4）基本法证明 */证明：对任一caAa，存在bA使cb。而bA，从而cA，所以aAa A 。反过来，再证A aAa 。任一cA，c aAa ,由于cc，故c aAa 。 定理2.13 (1)说明: A中每个元素所产生的等价类都是非空的； (2)说明: 互相等价的元素属于同一个等价类, (3)说明:不等价的元素所属的等价类没有公共元素; (1)(4

5、)共同说明：A关于R的商集A/R就是A的一个划分。 首先A/R= a | aA 是集合族，然后检查其是否符合A的划分的3个条件 由(1)， A/R中每个集合都是非空的， (4)说明aA/Ra= aAa=A 任取a,b A/R 若ab,必有R（否则由(2)可得a=b，矛盾），那么由(3)得ab=2.6 等价关系与划分 定理2.14 集合A上的任一划分 =A1, A2, , An可以确定A上的一个等价关系，称为由导出的等价关系。 由定义A上的二元关系 R=(A1A1)(A2A2) (AnAn) 证明R是一个等价关系，即证明R是自反、对称和传递的。 例2.26 设A= a, b, c, d, e,

6、f 的一个划分=a, b, c, d, e, f,由确定A上的一个等价关系R: R=(a, ba, b) (c, d c, d)(e, f e, f) =, , , , , , , , , , , 定理2.15 (1) 对A上的等价关系R，A/R导出的等价关系=R （请给出证明） (2) 设R1和R2是A上的等价关系， R1=R2 A/R1=A/R2 。（左推右显然，根据(1)右推左） 例： A=1,2,3 , R=, A/R=1,2,3 写出由A/R导出的等价关系 ,= R 定理2.13和定理2.15: 任一等价关系R确定一个划分,即A/R. 定理2.14和定理2.15: 任一划分确定一个等

7、价关系,即(A1A1) (AnAn). 并且在给定R时，将A/R取作，有 (A1A1) (AnAn)=R；或者给定 ，将(A1A1) (AnAn)取作R，则A/R = （的每个划分块都是R的一个等价类）。从而A的划分和A上的等价关系是一一对应的。 定理2.16 设R1和R2是A上的等价关系，则 R1R2是A上的等价关系。 例：设A=1, 2, 3, 4, 5，A上的二元关系R中，有多少个是等价关系？ 因为等价类划分和等价关系是一一对应的，所以A上的二元关系中等价关系的个数等于A的划分个数。 西安交通大学1998考研 解：对于A的划分可分为如下几种情况： （1） 划分成5个都只含1个元素的块，共

8、有1种； （2） 划分成1个都只含2个元素，3个都只含1个元素的块，共有10种； （3） 划分成2个都只含2个元素，1个都只含1个元素的块，共有15种； （4） 划分成1个都只含3个元素，2个都只含1个元素的块，共有10种； （5） 划分成1个都只含3个元素，1个都只含2个元素的块，共有10种； （6） 划分成1个都只含4个元素，1个都只含1个元素的块，共有5种； （7） 划分成1个都只含5个元素的块，共有1种； 综上所述，A上的等价关系共有1+10+15+10+10+5+1=52 定义2.17(加细) 设和是A的划分，若的每一块都包含在的某一块中，则称细分，或 是的加细。 例： A是学生集合

9、，是在A中按学院的划分， 是在A中按专业的划分。 定理2.17 设和是A的划分，它们确定A上的等价关系R和R，则细分当且仅当RR。例： A是学生集合，是在A中按学院的划分， 是在A中按专业的划分。和确定A上的等价关系R:同学院同学关系和R:同专业同学关系，显然RR。 证明： /*细分 RR ，基本法*/ 对于任一R，存在的某块S，使a, bS。因为细分，所以必存在的块S，使SS。因此a, bS，从而R。 /* RR 细分 */ 设S是的一块，aS则aR =x|xRa=S（请展开证明）。由于RR，若xRa必有xRa。因此x|xRax|xRa，即 aRaR。的一块包含在的一块中，所以细分。2.7

10、次序关系 一 偏序关系、偏序集 定义2.19(偏序关系) 设R是A上的二元关系，若 R是自反的、反对称的和传递的，则称R是A上的偏序关系。又记为。（借用了数的小于等于符号，但涵义更广）常见的偏序关系：, 定义2.20(偏/半序集) 若集合A具有偏序关系R（或 ），则称A为偏序集，记为（A, R）或（A, ）。 哈斯图：常用来表示偏序集，画法如下 位置关系：若a b，则结点a在b之下； 连线规则：若a与b之间不存在其他元素c，使a c，c b则在a与b之间用一线相连。2.7 次序关系 例题： Rosen离散数学及其应用（本科教学版）p225例13、例14、P226例18 判断是否正确，并说明理由

11、。 设A为集合，R是A的幂集P(A)上的二元关系，对所有S, TP(A)，(S, T)R当且仅当|S|T|。那么，R是一个偏序关系。 /*复旦大学1999考研*/ 证明整除关系是正整数集合上的偏序关系。 /*北京师范大学1999考研*/2.7 次序关系 四 最大元、最小元、极大元、极小元 定义2.21（最大元、最小元、极大元、极小元）设偏序集(A, )，BA，(1)最大元、最小元 若存在一个元素bB，对所有bB都有b b，则称b是B的最大元；若都有b b，则称b是B的最小元；(2)极大元、极小元 若存在一个元素bB，在B中不存在元素b b使得b b，则称b是B的极大元；若在B中不存在元素b b

12、使得b b ，则称b是B的极小元；2.7 次序关系(3)上界、下界 若存在一个元素aA，对所有bB都有ba，则称a是B的上界；对所有bB都有ab，则称a是B的下界；(4)上确界、下确界 若aA是B的上界且对B的每个上界a都有a a，则称a是B的上确界（最小上界，也就是B的上界集合中的最小元，故不一定存在）；若aA是B的下界且对B的每个下界a都有aa，则称a是B的下确界（最大下界）。2.7 次序关系 定理2.22 设偏序集(A, )，BA，若在B中存在最大元（最小元），则必唯一。 证明： （反证） 定理2.23 设偏序集（A, ）, BA，在B中存在最大元（最小元）必为极大元（极小元）。 写出集

13、合A=a, b, c的幂集P(A)，并画出偏序集(P(A), )的哈斯图。 /*北京航空航天大学1996考研试题*/2.7 次序关系 二 拟序关系 定义2.22（拟序关系） A上的二元关系 R是反自反的和传递的，称R为A上的拟序关系。称(A, R)为拟序集，或记为(A, )。（不意味着小于） 定理2.24 A上的二元关系 R是拟序的，则R必为反对称的。证明：反证法2.7 次序关系 定理2.25 设R是A上的二元关系，则(1)若R是A上的拟序关系，则r(R)=RIA是A上的偏序关系；(2) R是A上的偏序关系，则R-IA是A上的拟序关系； 证明方法：根据定义给出的性质证明。2.7 次序关系 三 全序关系 定义2.23（全序关系） 设是集合A 上的二元关系，如果对于A中任意两个元素a, bA，必有a b或b a，则称 是A上的全序关系（或线