定理27(证明(4) (4)U{区XR|X∈A}=A 馨证明:(4)A=U{}|X∈A} cU{R|X∈A}cu{AX∈A}=A u区g|XeA}=A.# yo 《集合论与图论》第8讲
《集合论与图论》第8讲 11 定理27(证明(4)) (4) U{ [x]R | x∈A } = A. 证明: (4) A=U{ {x} | x∈A } ⊆ U{ [x]R | x∈A } ⊆ U{ A | x∈A }=A. ∴ U{ [x]R | x∈A } = A. # x y
同余( congruence关系 同余关系:设n∈{234…Xy∈Z则 与y模n同余( e congruent modulo n) 台Xy(modn分nXy)<Xy=kn(∈Z) 同余关系是等价关系 ]={knk∈Z 1]={1+knk∈2 2]={2+knk∈Z1…, n-1]={(n-1)+knk∈2} 《集合论与图论》第8讲
《集合论与图论》第8讲 12 同余关系: 设n∈{2,3,4,…}, x,y∈Z,则 x与y模n同余(be congruent modulo n) ⇔ x≡y(mod n) ⇔ n|(x-y) ⇔ x-y=kn (k∈Z) 同余关系是等价关系 [0] ={ kn|k∈Z}, [1] ={ 1+kn|k∈Z}, [2] ={ 2+kn|k∈Z},…, [n-1]={(n-1)+kn|k∈Z}. 同余(congruence)关系 6 9 3 8 7 5 4 2 1 10 11 0
例11 例11:设A={1,23458},求 R3=(<x,y> X,yEAA X=y(mod 3)] 的等价类,画出R2的关系图 解:[1]=4]={1,4},(2]=5]=8]={2,58} 3]={3}# 《集合论与图论》第8讲 13
《集合论与图论》第8讲 13 例11 例11: 设 A={1,2,3,4,5,8}, 求 R3 = { <x,y> | x,y∈A ∧ x≡y(mod 3) } 的等价类, 画出R3的关系图. 解: [1]=[4]={1,4}, [2]=[5]=[8]={2,5,8}, [3]={3}. # 1 4 2 5 8 3
商集( (quotient set 婚商集:设R是A≠⑦上等价关系, AR={区]R|X∈A 称为A关于R的商集,简称A的商集 癱显然UA/R=A 例1(续):AR3={14,{2,5,8,{3 《集合论与图论》第8讲
《集合论与图论》第8讲 14 商集(quotient set) 商集: 设R是A≠∅上等价关系, A/R = { [x]R | x∈A } 称为A关于R的商集, 简称A的商集. 显然 U A/R = A. 例11(续): A/R3 ={ {1,4}, {2,5,8}, {3} }.
例12(1) 例12(1):设A={a1,a2,,an,IA,EA Auai, ai sai, a 都是A上等价关系,求对应的商集,其中 aa∈A,i④是A上等价关系吗? 解:AIA={l{a2}…,an}} AEA={{a1a2…,an} ARAA《aa-a 不是A上等价关系(非自反).# 《集合论与图论》第8讲 15
《集合论与图论》第8讲 15 例12(1) 例12(1): 设A={a1,a2,…,an}, IA, EA, Rij=IA∪{<ai,aj>,<aj,ai>} 都是A上等价关系, 求对应的商集, 其中 ai,aj∈A, i≠j. ∅是A上等价关系吗? 解: A/IA={ {a1}, {a2},…, {an } } A/EA={ {a1,a2,…,an } } A/Rij= A/IA∪{{ai,aj}} - {{ai},{aj}}. ∅不是A上等价关系(非自反). #