09-划分、等价关系.pptVIP

* 3.10　等价关系 定义：设A是非空集合， 若S＝{S1，S2，…，Sm}，且 ① Si ≠ Φ ( 1≤i≤m ) ② Si ∩ Sj ＝ Φ ( 1≤i＜j≤m ) ③ ∪Si ＝ S1∪S2∪…∪Sm ＝ A 则称S是A的划分，称Si为A的划分块。 一、划分 各划分块非空 不同划分块不相交 所有划分块的并集是 A 定义：设A是非空集合， S = { S1，S2，…，Sm }， T = { T1，T2，…，Tn }， S 和 T 是 A 的两个划分， 若对于每一个 Si，都有 Tj， 使得 Si 是 Tj 的子集， 则称 S 是 T 的加细。 例：A = {1,2,3,4} A的划分： S1 = {{1,2},{3},{4}} S2 = {{1},{2},{3},{4}} 最大划分 S3 = {{1,2,3,4}} 最小划分 S1是S3的加细 , S2是S1的加细 , S2是S3的加细 说明： ① A 的划分， 是 A 的幂集 P(A) 的子集 ② 最大(最细)划分：{ {a}｜a?A } 最小(最粗)划分：{ A } 例：S 是任意非空集合, P(S) - {Φ}能否构成S的划分？ 解：(1) 若 |S| =1: P(S) - {Φ}是S的划分 (2) 若 |S| 1: P(S) - {Φ}不是S的划分 S的划分是 P(S) - {Φ} 的真子集 定义： 设R是集合A上的二元关系， 若R是自反的、对称的和传递的， 则称R为A上的等价关系 。 二、等价关系 例：A = {1,2,3,4,5,6,7,8} R = { x,y | x,y?A , x≡y(mod 3) } = {1,1,1,4,1,7,2,2,2,5, 2,8,3,3,3,6,4,1,4,4, 4,7,5,2,5,5,5,8,6,3, 6,6,7,1,7,4,7,7,8,2, 8,5,8,8} 模３同余关系 　　 是等价关系 定理：任何Z的子集上的模n同余关系 是等价关系。 (一类重要的等价关系) 证明：设Z1是整数集Z的任一子集 R是Z1上的模n同余关系 R={ a,b | a,b?Z1,a≡b(mod n) } 模n同余关系：(a-b)可以被n整除 ① 对于任意的a? Z1， ∵ a-a=0·n ∴ 有a≡a(mod n) ∴ a,a?R ∴ R是自反的 ② 对于任意的a,b?R，有 a≡b(mod n) 即存在整数k，使a-b=k·n， 那么有　b-a＝(-k)·n ∴有b≡a(mod n) ∴ b,a?R ∴ R是对称的 ③对于任意的a,b,b,c?R，有 a≡b(mod n), b≡c(mod n) 即存在整数k、h， 使a-b=k·n，b-c=h·n，　 那么有 a-c=(a-b)+(b-c)=(k+h)·n ∴有a≡c(mod n) ∴ a,c?R ∴ R是传递的 综合①、②、③，∴ R是等价关系 等价关系的关系图可简化为： ①有向环省去 ②用一条无向边代替两条有向边 定义： 设R为非空集合A上的等价关系， 对任意的 a?A，令 [a]R = { x | x?A 且 x,a?R } 称 [a]R 为 a关于R的等价类， 简称 a的等价类，简记[a] 三、等价类 例：模３同余关系 A = {1,2,3,4,5,6,7,8} R = { x,y | x,y?A , x≡y(mod 3) } = {1,1,1,4,1,7,2,2,2,5, 2,8,3,3,3,6,4,1,4,4, 4,7,5,2,5,5,5,8,6,3, 6,6,7,1,7,4,7,7,8,2, 8,5,8,8} 等价类： [1]R ＝ [4]R ＝ [7]R　＝ {