划分 partition) 划分:设A≠,P(A)若满足 (1)丝; (2)Xy(Xy∈A∧Xy→Xy=) (3)U=A 则称为A的一个划分,中元素称为划分 块bloc 《集合论与图论》第8讲 16
《集合论与图论》第8讲 16 划分(partition) 划分: 设A≠∅, A⊆P(A),若A满足 (1) ∅∉A ; (2) ∀x,y( x,y∈A ∧ x≠y ⇒ x∩y=∅ ) (3) UA = A 则称A为A的一个划分, A中元素称为划分 块(block).
划分(举例) 鲁设≠A1,A2…AncE,则以下都是划分: A={A,~A,(i=1,2,…,n) AA,~A^A,A⌒A1~A^~A{ j=12…n∧i) A12.n={~A~A A A~A2…~An个An A^A2…∩An{.# 《集合论与图论》第8讲
《集合论与图论》第8讲 17 划分(举例) 设 ∅≠A1,A2,…,An⊂E, 则以下都是划分: Ai = {Ai,~Ai}, ( i=1,2,…,n ) Aij = {Ai∩Aj,~Ai∩Aj, Ai∩~Aj, ~Ai∩~Aj}-{∅} ( i,j =1,2,…,n ∧ i≠j ) …… A12…n = {~A1∩~A2∩… ∩~An,…, ~A1∩~A2∩… ∩~An-1∩An,… A1∩A2∩… ∩An}-{∅}. #
划分(举例续) 《集合论与图论》第8讲 8
《集合论与图论》第8讲 18 划分(举例,续) Ai ~Ai
等价关系与划分是一一对应的 定理28:设A≠,则 (1)R是A上等价关系→AR是A的划分 (2)是A的划分→R是A上等价关系,其中 XRN分3(z∈∧Xezy∈2) R称为由划分所定义的等价关系(同块关系).# 《集合论与图论》第8讲 19
《集合论与图论》第8讲 19 等价关系与划分是一一对应的 定理28: 设A≠∅, 则 (1) R是A上等价关系 ⇒ A/R是A的划分 (2) A是A的划分 ⇒ RA是A上等价关系,其中 xRAy ⇔ ∃z(z∈A ∧ x∈z ∧ y∈z) RA称为由划分A 所定义的等价关系(同块关系). #
例12(2) 例122:A={ab,c},求A上全体等价关系 解:A上不同划分共有5种 bc/·bcc八bcc八b/● b oc R=E A R2=Ab,c><c,b>}, R3=lAU<a, c><c, a> R4=lAU<a, b><b, a>, R5=lA. 《集合论与图论》第8讲
《集合论与图论》第8讲 20 例12(2) 例12(2): A={a,b,c}, 求A上全体等价关系. 解: A上不同划分共有5种: a b c a b c a b c a b c a b c R1= EA, R2=IA∪{<b,c><c,b>}, R3=IA∪{<a,c><c,a>}, R4=IA∪{<a,b><b,a>}, R5=IA. #