复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）04/30

例:设整数集I上的模2同余关系为R,这 是Ⅰ上的等价关系。 在R下,把I中所有与0有关系即与0等价 的整数划分为一类,记为E; 与1等价的所有整数划分为一类,记为O 集合I中的元素或者属于E,或者属于O, 且它们互不相交。 由关系R把I分为两类:E和O, 这就是的一个划分

• 例：设整数集I上的模2同余关系为R,这 是I上的等价关系。 • 在R下，把I中所有与0有关系即与0等价 的整数划分为一类，记为E； • 与1等价的所有整数划分为一类，记为O • 集合I中的元素或者属于E，或者属于O, 且它们互不相交。 • 由关系R把I分为两类：E和O， • 这就是I的一个划分

三、等价关系与划分 定义214:设R是A上的等价关系,对于 每个a∈A,与a等价的元素全体所组成的集 合称为由a生成的关于R的等价类,记为 a],即|al={xx∈A,xRa},a称为该等价类 的代表元。 在不会引起误解的情况下,可把|a]简记 为|a 定义2.15:设R是A上的一个等价关系, 关于R的等价类全体所组成的集合族称为 A上关于R的商集,记为A/R,即 A/R={alla∈A}

• 三、等价关系与划分 • 定义 2.14：设R是A上的等价关系, 对于 每个aA,与a等价的元素全体所组成的集 合称为由a生成的关于R的等价类,记为 [a]R, 即[a]R={x|xA,xRa},a称为该等价类 的代表元。 • 在不会引起误解的情况下,可把[a]R简记 为[a]。 • 定义 2.15：设R是A上的一个等价关系, 关于R的等价类全体所组成的集合族称为 A 上 关 于 R 的 商 集 , 记 为 A/R, 即 A/R={[a]|aA}

例:整数集I上的模2同余关系R,其等价类为 0][1]l 其中[0]={…,-4,-2,0,2,4,…,}=[2|=4|=|-2|=|- [1}={…,-3,1,1,3,}=3=-1=[-3 因此A/R={|01 例:整数集I上的模n同余关系是I上的等价关系。 I上关于R的等价类为: 0}={…,-2n,n,0,n,2n,} [1={,2n+1,n+1,1,n+1,2n+1,} In-l|={…,-n-1,1,n-1,2n-1,3n-1,} 这些类又称上模n同余类。 I上关于R的商集I/R={011,n-}

• 例：整数集I上的模2同余关系R，其等价类为 [0],[1]。 • 其中[0]={…,-4,-2,0,2,4,…}=[2]=[4]=[-2]=[- 4]=… • [1]={…,-3,-1,1,3,…}=[3]=[-1]=[-3]=… • 因此A/R={[0],[1]} • 例:整数集I上的模n同余关系是I上的等价关系。 I上关于R的等价类为： • [0]={…,-2n,-n,0,n,2n,…} • [1]={…,-2n+1,-n+1,1,n+1,2n+1,…} • … • [n-1]={…,-n-1,-1,n-1,2n-1,3n-1,…} • 这些类又称I上模n同余类。 • I上关于R的商集I/R={[0],[1],…,[n-1]}

定理213:设R是A上的等价关系,则 (1)对任一a∈A,有a∈|al; (2)若aRb,则|a=[b]; (3)对ab∈A,如果(a,bER则|a∩b]= a∈A 此定理的(1)说明A中每个元素所产生的等价类是非空的 定理的(2)、(3)说明:互相等价的元素属于同一个等价类, 而不等价的元素其所对应的等价类之间没有公共元素 定理的(4)说明:A上等价关系R所对应的等价类的并就等于 A由此定理说明A上等价关系R所对应的等价类集合是A的 个划分。 该定理告诉我们,给定一个等价关系就唯一确定一个划分

• 定理 2.13：设R是A上的等价关系, 则 • (1)对任一aA,有a[a]; • (2)若aRb, 则[a]=[b]; • (3)对a,bA, 如果(a,b)R,则[a]∩[b]=; a A a A =  (4)[ ] 此定理的(1)说明A中每个元素所产生的等价类是非空的 定理的(2)、(3)说明：互相等价的元素属于同一个等价类， 而不等价的元素其所对应的等价类之间没有公共元素 定理的(4)说明：A上等价关系R所对应的等价类的并就等于 A.由此定理说明A上等价关系R所对应的等价类集合是A的 一个划分。 该定理告诉我们，给定一个等价关系就唯一确定一个划分

证明:(1对任一a∈A,因为R是A上的等 价关系,所以有Ra(R自反),则a∈|a (2)对ab∈A,aRb,分别证明[a|∈[bl b|∈|a 对任意x∈[a](目标证明x∈[b,即xRb) 下面证明[bc|a 对任意x∈[b(目标证明x∈al,即xRa)。 (3)对a,b∈A,如果a,b)gR,则[ab= 采用反证法。假设|abH≠,则至少存 在x∈a]∩[b]l

• 证明：(1)对任一aA，因为R是A上的等 价关系，所以有aRa(R自反)，则a[a]。 • ( 2 )对 a,bA, aRb, 分别证明 [ a][b]， [b][a]。 • 对任意x[a](目标证明x[b]，即xRb)。 • 下面证明[b][a] • 对任意x[b](目标证明x[a]，即xRa)。 • (3)对a,bA, 如果(a,b)R,则[a]∩[b]= • 采用反证法。假设[a]∩[b]≠，则至少存 在x[a]∩[b]

(4)∪a=A a∈A 对任意的x∈Ua必存在某个a∈A使得x∈aA a∈A 所以Jd≤A 又对任意的x∈A有x∈[x]Ua a∈A 所以A∈∪a a∈A 因此有Ud=A

a A a A =  (4)[ ] x a a A x a A a A      对任意的 [ ],必存在某个 ,使得 [ ] a A a A   所以[ ]  a A x A x x a  又对任意的  ,有 [ ]  [ ]  a A A a  所以  [ ] a A a A =  因此有[ ]

例:设A={1,2,3,4},R={(1,1)(2,2) (3,3),(4,4),(1,3),(2,4,3,1),(4,2)为等价关 系。 ·其等价类为[={1,3} 「2={2,4} 4}={2,4} 划分∏={,2 前面是给定等价关系唯一确定划分,反 过来,给定一个划分,也可唯一确定 个等价关系

• 例：设 A={1,2,3,4}，R={(1,1),(2,2), (3,3),(4,4),(1,3),(2,4),(3,1), (4,2)}为等价关 系。 • 其等价类为[1]={1,3} • [2]={2,4} • [3]={1,3} • [4]={2,4} • 划分={[1],[2]} • 前面是给定等价关系唯一确定划分，反 过来，给定一个划分，也可唯一确定一 个等价关系

设非空集A上划分I={A1,A2…,n},定义A 上二元关系R:aRb当且仅当存在A,使得 a,b∈A: 即R=(A1×A)∪(A2×A2)∪∴∪(An×An 容易证明R是等价关系 定理214:集合A上的任一划分可以确定A 上的一个等价关系R。 例:设A={a,b,c}的一个划分∏={a,b},{c}, 由Ⅱ确定A上的一个等价关系R: R=({a,b}×{a,b})U(e}×{e)={(a,a),(a,b),(b,a) ,(b,b),(C,c)

• 设非空集A上划分={A1 ,A2 ,…,An }，定义A 上二元关系R：aRb当且仅当存在Ai ,使得 a,bAi。 • 即R=(A1A1 )∪(A2A2 )∪…∪(AnAn ) • 容易证明R是等价关系。 • 定理2.14：集合A上的任一划分可以确定A 上的一个等价关系R。 • 例：设A={a,b,c}的一个划分={{a,b},{c}}, 由确定A上的一个等价关系R： • R=({a,b}{a,b})∪({c}{c})={(a,a),(a,b),(b,a) ,(b,b), (c,c)}

定理215:设R1和R2是A上的等价关系R1=R2 当且仅当AR1=A/R2 定理2.13和定理215说明集合A上的任一等 价关系可以唯一地确定A的一个划分。 定理214和定理215说明集合A的任一划分 可以唯一地确定A上的一个等价关系。 集合A上给出一个划分和给出一个等价关系 是没有什么实质区别的。 设集合A上的等价关系为R1和R2,它们通过并 和交运算而得到的关系是不是等价关系? 若是,其对应的划分与原来的两个划分有何联 系

• 定理 2.15:设R1和R2是A上的等价关系,R1=R2 当且仅当A/R1=A/R2。 • 定理 2.13 和定理 2.15 说明集合A上的任一等 价关系可以唯一地确定A的一个划分。 • 定理2.14和定理 2.15说明集合A的任一划分 可以唯一地确定A上的一个等价关系。 • 集合A上给出一个划分和给出一个等价关系 是没有什么实质区别的。 • 设集合A上的等价关系为R1和R2 ,它们通过并 和交运算而得到的关系是不是等价关系? • 若是,其对应的划分与原来的两个划分有何联 系

四、划分的积与和 1划分的积 定理216:设R和R2是A上的等价关系,则 R1∩R2是A上的等价关系。 定义2.16:设R1和R是A上的等价关系,由 R和R2确定的A的划分分别为∏1和I2,A上 的等价关系R1∩R2所确定的A的划分称为 I1与划分的积记为∏1∏2 定义2.17:设∏和m是A的划分,若I的每 块包含在∏的一块中,称I细分江,或称I 加细∏

• 四、划分的积与和 • 1.划分的积 • 定理 2.16：设R1和R2是A上的等价关系,则 R1∩R2是A上的等价关系。 • 定义 2.16：设R1和R2是A上的等价关系, 由 R1和R2确定的A的划分分别为1和2 ,A上 的等价关系R1∩R2所确定的A的划分,称为 1与2划分的积,记为1·2。 • 定义 2.17：设和'是A的划分, 若'的每 一块包含在的一块中, 称'细分,或称' 加细