例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