北京大学：《离散数学》系列课程之一《集合论与图论》第8讲 等价关系与序关系

第8讲等价关系与序关系 内容提要 等价关系等价类,商集 划分,第二类 Stirling数 秦偏序线序拟序,良序 哈斯图 眷特殊元素:最?元,极?元,?界?确界 (反)链 《集合论与图论》第8讲

《集合论与图论》第8讲 1 第8讲 等价关系与序关系 内容提要 等价关系,等价类,商集 划分, 第二类Stirling数 偏序,线序,拟序,良序 哈斯图 特殊元素: 最?元,极?元,?界,?确界 (反)链

等价( equivalence)关系 定义 同余关系 等价类 癱商集 划分 划分的加细 Stirling子集数 《集合论与图论》第8讲

《集合论与图论》第8讲 2 等价(equivalence)关系 定义 同余关系 等价类 商集 划分 划分的加细 Stirling子集数

等价( equivalence)关系定义 等价关系:设RAxA且A≠x,若R是自 反的,对称的,传递的,则称R为等价关系 例9:判断是否等价关系(A是某班学生) R{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∈A∧x与y同年生} R2={|x,y∈A∧x与y同姓} R3={|x,y∈A∧x的年龄不比y小} R4={|x,y∈A∧x与y选修同门课程} R5={|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 )

例10(续) tsr(R)=trs(R) str()=srt(R) =s(R) rst(R) 自反 对称 传递 √x 等价关系√等价闭包) 《集合论与图论》第8讲

《集合论与图论》第8讲 6 例10(续) √ √ √ √(等价闭包) 传递 × 对称 √ × √ str(R)=srt(R) =rst( R ) 等价关系 自反 tsr(R)=trs(R) =rts( R )

等价类( equivalence class) 等价类:设R是A≠0上等价关系,X∈A,令 X={y|y∈A∧xRy 称×]为X关于R的等价类,简称x的等价类 简记为Ⅸ1 等价类性质:区X=≠ XRy→R=ⅣR; XRy→区^MR= uⅨXg|X∈A=A 《集合论与图论》第8讲

《集合论与图论》第8讲 7 等价类(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≠上等价关系,xyEA, (1)区R≠0 2)xRy→(=lR; (3)-XRy→gR= (4)U{Ⅸ|X∈A}=A 证明:(1)R自反→XRX→X∈冈→×D 《集合论与图论》第8讲

《集合论与图论》第8讲 8 定理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≠∅. x

定理27(证明(2) 秦(2)XRy→区 Fly; 证明:(2)只需证明Ⅳ和R (z,z∈R∧Ry→ ZRXAXRY zRy→z∈ⅣR.∴Reyg 已)同理可证.z 《集合论与图论》第8讲

《集合论与图论》第8讲 9 定理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. (⊇) 同理可证. x y z

定理27(证明(3) (3)-XRy→区R^MR=0; 证明:(3)(反证)假设彐Z,z∈凶yla,则 Z∈∩yR→2 RXAZRy→ XRZAZRy xRy,这与XRy矛盾!:区×g~= 《集合论与图论》第8讲

《集合论与图论》第8讲 10 定理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=∅. x y z