第8讲等价关系与序关系 内容提要 等价关系等价类,商集 划分,第二类 Stirling数 秦偏序线序拟序,良序 哈斯图 眷特殊元素:最?元,极?元,?界?确界 (反)链 《集合论与图论》第8讲
《集合论与图论》第8讲 1 第8讲 等价关系与序关系 内容提要 等价关系,等价类,商集 划分, 第二类Stirling数 偏序,线序,拟序,良序 哈斯图 特殊元素: 最?元,极?元,?界,?确界 (反)链
等价( equivalence)关系 定义 同余关系 等价类 癱商集 划分 划分的加细 Stirling子集数 《集合论与图论》第8讲
《集合论与图论》第8讲 2 等价(equivalence)关系 定义 同余关系 等价类 商集 划分 划分的加细 Stirling子集数
等价( equivalence)关系定义 等价关系:设RAxA且A≠x,若R是自 反的,对称的,传递的,则称R为等价关系 例9:判断是否等价关系(A是某班学生) R{<Xy>xyEA∧x与y同年生} R2{Xy> X, EAX与y同姓} R3{xXy>XyAx的年龄不比y小 R{xXy>ⅸyAX与y选修同门课程} R5{Xxy>XyEA∧x的体重比y重 《集合论与图论》第8讲
《集合论与图论》第8讲 3 等价(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(续) 定义自反对称传递等价关系 Rx与y同年生√ R2x与y同姓 R3x的年龄不比√×y R4×与y选修同 门课程 x的体重比y 重 《集合论与图论》第8讲
《集合论与图论》第8讲 4 例9(续) × × × √ √ 等价关系 x与y选修同 √ √ × 门课程 R4 R2 x与y同姓 √ √ √ x的体重比y × × √ 重 R5 x的年龄不比 √ × √ y小 R3 R1 x与y同年生 √ √ √ 定义 自反 对称 传递
例10 例10:设 RCAXA且A≠⑦,对R依次求三 种闭包共有6种不同顺序,其中哪些顺序 定导致等价关系? rst(R),Its(R), str(R), srt(R), trs(R) tsr(R)=t(S(〔(R)) 解:s(R)≌s(R),Sr(R)=s(R) tsr(R=trs(R=rts(R) str(R =srt (R =rst(R 《集合论与图论》第8讲
《集合论与图论》第8讲 5 例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 )