概率论-第十五讲 等价关系和划分

8
一、等价关系
定理5: 设R是A上的二元关系,设R′=tsr(R)是R的自反对称 传递闭包,那么 (a) R′是A上的等价关系,叫做R诱导的等价关系； (b) R′是包含R的最小等价关系。 证明： r(R)是自反的，所以sr(R)是自反的，对称的，所以 tsr(R)是自反的，对称的，传递的，即R’=tsr(R)是A上 的等价关系。 设R”是包含R的任意等价关系，即R⊆R”，因为R”是 自反的，所以r(R)⊆r(R”)=R”；因为R”是对称的，所以 sr(R)⊆s(R”)=R”;又因为R”是传递的，所以 tsr(R)⊆t(R”)=R”，即R”包含tsr(R)。
14
二、划分
定理9：设π是非空集合A上的划分,R是A上的等价关系,那么,
π诱导出R当且仅当R诱导出π。 证：（必要性）假设π诱导出R,R诱导出π′ 设a是A的任一元素,并设B和B′分别是π和π′的块, 使a∈B和B′，那么对任一b b∈B iff ［a］R =［b］R iff b∈B′ 所以,B=B′。 因为a是A的任一元素而π和π′都是A的覆盖,故π=π′。
若是划分，则必是覆盖；若是覆盖，则不一定是划分。
②设A是非空集合, ρ(A)-{∅ } 是A的一个覆盖,而不是A的划分,除非A是单元素集合。
11
二、划分
定理6 : 设A是非空集合,R是A上的等价关系。R的等价类集合 {［a］R ｜a∈A}是A的划分。 由上面定理2，3可得出。 定义5：设R是非空集合A上的等价关系,称划分{［a］R｜a∈A} 定理2：设R是集合A上的等价关系,则对所有a,b∈A,或者 ［a］=［b］,或者［a］∩［b］= ∅ 为商集A/R,也叫A模R。
10
二、划分
例4：①A={a,b,c}，则 S={{a,b},{b,c}}, Q={{a},{a,b},{a,c}}, D={{a},{b,c}}, G={{a,b,c}}, E={{a},{b},{c}}, F={{a},{a,c}}, 划分 最小划分 最大划分 既不是覆盖，也不是划分 覆盖 覆盖
15
二、划分
定理9：设π是非空集合A上的划分,R是A上的等价关系,那么,
π诱导出R当且仅当R诱导出π。 证：（充分性）假设R诱导出π,π诱导出等价关系R′。 那么对任意a,b∈A aRb iff ［a］R =［b］R iff a,b∈［a］R iff 存在B，使(B∈π∧a∈B∧b∈B) iff aR′b 所以，R=R’。
回顾：
偏序关系 拟序、线序、良序
1
3.5
一、等价关系
等价关系和划分
定义1：如果集合A上的二元关系R是自反的,对称的和传递的, 那么称R是等价关系。设R是A上的等价关系,a,b是A 的任意元素，如果aRb(即〈a,b〉∈R),通常我们记作 a～b,读做“a等价于b”。 如: 实数集上的“=”关系； 任何集合上的相等关系和全域关系； 空集上的二元关系。 等价关系的有向图的每一分图是完全图。
若R1 = R 2，对任意a ∈ A， 则[a ]R1 = {x | x ∈ A ∧ xR1a} = {x | x ∈ A ∧ xR 2a} = [a ]R 2， 所以{[a ]R1 | a ∈ A} = {[a ]R 2 | a ∈ A}。
充分性：
反之，假设{[a ]R1 | a ∈ A} = {[a ]R 2 | a ∈ A}，对任意[a ]R1， 必存在[c ]R 2 ∈ {[a ]R 2 | a ∈ A}，使得[a ]R1 = [c ]R 2，故 < a , b >∈ R1 ⇔ a ∈ [a ]R1 ∧ b ∈ [a ]R1 ⇔ a ∈ [c ]R 2 ∧ b ∈ [c ]R 2 ⇒< a, b >∈ R 2，所以R1 ⊆ R 2，类似有R 2 ⊆ R1，所以R1 R 2。 ＝
x∈A
又 Q[a ] ⊆ A， c ∈ A， U [x ] ⊆ A ∴ ∴
x∈A
又 Q 对任意c ∈ A，必有c ∈ [c]，而[c] ⊆ U [x ]，
x∈A
∴ c ∈ U [x ]， A ⊆ U [x ] ∴
x∈A x∈A
综上，A = U [x ]
x∈A
7
一、等价关系
定理4：设R1和R2是集合A上的等价关系,那么R1=R2当且仅当 {［a］R1｜a∈A}={［
定义2:设R是集合A上等价关系,对每一a∈A，a关于R的等价类 是集合{x｜xRa},记为［a］R，简记为［a］;称a为等价 类［a］的表示元素。 如果等价类个数有限,则R的不同等价类的个数叫做 R的秩;否则秩是无限的。 对每一a∈A,等价类［a］R非空,因为a∈［a］R。 例2：R是I上的模3等价关系，确定由I的元素所产生的等价类。 ［0］3={…-6,-3,0,3,6,…}= ［-3］3=［3］3= ［6］3 =… ［1］3={…-5,-2, 1,4,7,…}= ［-2］3=［4］3= ［7］3 =… ［2］3={…-4,-1,2,5,8,…}= ［-1］3=［5］3= ［8］3 =… 该等价关系R的秩为3。 例3：集合A上相等关系的秩等于？ A的元素个数。
13
B∈π
二、划分
例5：设A={a,b,c,d,e}，划分S={{a,b},{c},{d,e}}, 由S确 定A上等价关系R。 解：R={a,b} ×{a,b} ∪{c} ×{c} ∪{d,e} ×{d,e} = {〈a,a〉, 〈a,b〉, 〈b,a〉, 〈b,b〉, 〈c,c〉, 〈d,d〉, 〈d,e〉, 〈e,d〉, 〈e,e〉} 若已知等价关系，求划分，则把有R关系的元素放到一 个划分块即可。
5
一、等价关系
定理2：设R是集合A上的等价关系,则对所有a,b∈A,或者 ［a］=［b］,或者［a］∩［b］= ∅ 证：如果A= ∅ , 断言无义地真。 现设A≠ ∅ 。若［a］∩［b］≠ ∅ , 则存在某元素c c∈［a］和c∈［b］。 根据定理1得［a］=［c］=［b］。 又因［a］和［b］都非空, ［a］∩［b］= ∅和［a］=［b］不能兼得。故定理得证。
4
一、等价关系
定理1：设R是非空集合A上的等价关系,aRb当且仅当 ［a］=［b］ 证 ：1)充分性： 因为a∈［a］且［a］=［b］,即a∈［b］,所以aRb。 2)必要性： 对任意x∈［a］,有xRa， 又因为aRb,由传递性可知xRb，即x∈［b］ 所以［a］⊆［b］，同理可证［b ］⊆［a］ 故［a］=［b］。
9
二、划分
定义4：给定非空集合A和非空集合族π={A1,A2,…,Am},如果 (i)π是A的覆盖,即 A = U A i
i =1 m
(ii)Ai∩Aj= ∅ 或Ai=Aj(i,j=1,2,…,m) 那么集合族π叫做集合A的一个划分；划分的元素Ai 称为划分π的块,如果划分是有限集合,则不同块的 个数叫划分的秩。若划分是无限集合,则它的秩是无 限的。划分的秩就是划分的大小。
定理3：设R是集合A上的等价关系,则 A = U [x ] x∈A 定理7：设R1和R2是非空集合A上的等价关系,那么R1=R2当且仅 即R的等价类集合是A的覆盖。
当A/R1=A/R2。
定理6，7说明A上的等价关系可以诱导出A的划分，且是唯一 的。
12
二、划分
定理8：设π是非空集合A的一个划分,则A上的二元关系: R = U B × B 或写成 aRb ⇔ ∃B[B ∈ π ∧ a ∈ B ∧ b ∈ B] 是A上的等价关系。 证：(a)对任意a∈A，因为a是在π的某块B中,所以aRa， 故R自反。 (b)如果aRb,那么有某块B∈π,使a∈B和b∈B， 所以bRa，故 R是对称的。 (c)如果aRb和bRc,那么存在B1∈π和B2∈π,使 a,b∈B1和b,c∈B2,即b∈B1∩B2,由划分的定义, 要么B1∩B2= ∅,要么B1=B2,所以B1=B2。 因此,c∈B1,有aRc，故 R是传递的。 通过该定理可知A的划分也可诱导出A上的等价关系。
6
一、等价关系
定义3：给定非空集合A和非空集合族π={A1,A2,…,Am},如 果 A = U A i ,那么称集合族π是A的覆盖。
i =1 m
U 定理3：设R是集合A上的等价关系,则 A = x∈A[x ] 即R的等价类集合是A的覆盖。 证： Q 对任意c ∈ U [x ]，必存在一a，使c ∈ [a ]，
等价关系和划分只是相同概念的不同描述，本质相同。
16
二、划分
例6：设A={a,b,c,d,e}，构造A上的一个等价关系 S，使得|S|=7。 例7：设A={a,b,c}，求A上所有的等价关系。
17
作业：P125 3、6、7、11(a)
18
2
一、等价关系
例1：设A为任意整数集合的子集， A上的关系R={〈x,y〉 |x≡y(mod k)} (称x,y模k (k是一个正整数)等价， 即存在整数m,使x-y=mk,k为模数)，证明R是等价关系。 证：(1)若A为空集，显然R为等价关系。 (2)若A非空，则 i) 因为对任意a∈A,有a-a=0·k，所以a≡a(mod k)， 故R自反； ii) 因为a≡b(modk)时,存在某m∈I,使a-b=m·k, 于是b-a= -m·k,因此b≡a(modk),故R对称； iii)设a≡b(modk)和b≡c(modk), 那么存在m1,m2∈I,使a-b=m1k和b-c=m2·k, 将两等式两边相加,得a-c=(m1+m2)·k, 所以a≡c(modk)，故R传递。 3