北大离散数学 《集合论与图论》第8讲.pptVIP

《集合论与图论》第8讲 第8讲 等价关系与序关系 内容提要 等价关系,等价类,商集 划分, 第二类Stirling数 偏序,线序,拟序,良序 哈斯图 特殊元素: 最?元,极?元,?界,?确界 (反)链 等价(equivalence)关系 定义 同余关系 等价类 商集 划分 划分的加细 Stirling子集数 等价(equivalence)关系定义 等价关系: 设 R?A?A 且 A??, 若R是自反的, 对称的, 传递的,则称R为等价关系 例9: 判断是否等价关系(A是某班学生): R1={x,y|x,y?A?x与y同年生} R2={x,y|x,y?A?x与y同姓} R3={x,y|x,y?A?x的年龄不比y小} R4={x,y|x,y?A?x与y选修同门课程} R5={x,y|x,y?A?x的体重比y重} 例9(续) 例10 例10: 设 R?A?A 且 A??, 对R依次求三种闭包共有6种不同顺序, 其中哪些顺序一定导致等价关系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=t(s(r( R ))) 解: st( R )?ts( R ), sr( R )=rs( R ),… tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R ) 例10(续) 等价类(equivalence class) 等价类: 设R是A??上等价关系,?x?A,令 [x]R={ y | y?A ? xRy }, 称[x]R为x关于R的等价类, 简称x的等价类, 简记为[x]. 等价类性质: [x]R?? ; xRy ? [x]R=[y]R ; ?xRy ? [x]R?[y]R=? ; U{ [x]R | x?A } =A. 定理27 定理27:设R是A??上等价关系,?x,y?A, (1) [x]R?? (2) xRy ? [x]R=[y]R ; (3) ?xRy ? [x]R?[y]R=? ; (4) U{ [x]R | x?A } =A. 证明: (1) R自反?xRx?x?[x]R?[x]R??. 定理27(证明(2)) (2) xRy ? [x]R=[y]R ; 证明: (2) 只需证明[x]R?[y]R和[x]R?[y]R. (?) ?z, z?[x]R?xRy ? zRx?xRy ? zRy ? z?[y]R . ? [x]R?[y]R. (?) 同理可证. 定理27(证明(3)) (3) ?xRy ? [x]R?[y]R=? ; 证明: (3) (反证) 假设?z, z?[x]R?[y]R, 则 z?[x]R?[y]R ? zRx?zRy ? xRz?zRy ? xRy, 这与?xRy矛盾! ? [x]R?[y]R=?. 定理27(证明(4)) (4) U{ [x]R | x?A } = A. 证明: (4) A=U{ {x} | x?A } ? U{ [x]R | x?A } ? U{ A | x?A }=A. ? U{ [x]R | x?A } = A. # 同余(congruence)关系 同余关系: 设n?{2,3,4,…}, x,y?Z,则 x与y模n同余(be congruent modulo n) ? x?y(mod n) ? n|(x-y) ? x-y=kn (k?Z) 同余关系是等价关系 [0] ={ kn|k?Z}, [1] ={ 1+kn|k?Z}, [2] ={ 2+kn|k?Z},…, [n-1]={(n-1)+kn|k?Z}. 例11 例11: 设 A={1,2,3,4,5,8}, 求 R3 = { x,y | x,y?A ? x?y(mod 3) } 的等价类, 画出R3的关系图. 解: [1]=[4]={1,4}, [2]=[5]=[8]={2,5,8}, [3]={3}. # 商集(quotient set) 商集: 设R是A??上等价关系, A/R = { [x]R | x?A } 称为A关于R的商集, 简称A的商集. 显然 U A/R = A. 例11(续): A/R3 ={ {1,4}, {2,5,8}, {3} }. 例12(1) 例12(1): 设A={a1,a2,…,an}, IA, EA, Rij=IA?{ai,aj,aj,ai} 都是A上等价关系, 求对应的商集, 其中ai,aj?A, i?j.