离散数学 - 等价关系与划分

·例：设整数集I上的模2同余关系为R，这是I上的等价关系。·在R下，把I中所有与0有关系即与0等价的整数划分为一类，记为E；，与1等价的所有整数划分为一类，记为0·集合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的一个划分

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

• 三、等价关系与划分 • 定义 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]。其中[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,...]这些类又称上模n同余类。I上关于R的商集I/R={[0],[1],...,[n-1]

• 例：整数集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]}

·定理2.13：设R是A上的等价关系.则·(1)对任一aEA,有ae[a];· (2)若aRb, 则[a]=[b];·(3)对a,beA,如果(a,b)R,则[a]n[b]=;(4)U[a] = AaeA此定理的（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)对任一aEA，因为R是A上的等价关系，所以有aRa(R自反)，则aE[a]。(2)对a,beA,aRb,分别证明[a]二[b][b]c[a]。，对任意xE[al(目标证明xE[bl，即xRb)。下面证明[b]二[a]对任意xE[bl(目标证明xE[a]，即xRa)。(3)对a,bEA,如果(a,b)史R,则[a|n[b|=の·采用反证法。假设[a]n[b]+の，则至少存在xe[a]n[b]

• 证明：(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]