等价关系与划分课件

例：设整数集I上的模2同余关系为R,这是I上的等价关系。在R下，把I中所有与0有关系即与0等价的整数划分为一类，记为E；与1等价的所有整数划分为一类，记为O集合I中的元素或者属于E，或者属于O,且它们互不相交。由关系R把I分为两类：E和O，这就是I的一个划分。例：设整数集I上的模2同余关系为R,这是I上的等价关系。1三、等价关系与划分定义2.14：设R是A上的等价关系,对于每个aA,与a等价的元素全体所组成的集合称为由a生成的关于R的等价类,记为[a]R,即[a]R={x|xA,xRa},a称为该等价类的代表元。在不会引起误解的情况下,可把[a]R简记为[a]。定义2.15：设R是A上的一个等价关系,关于R的等价类全体所组成的集合族称为A上关于R的商集,记为A/R,即A/R={[a]|aA}。三、等价关系与划分2例：整数集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]}例：整数集I上的模2同余关系R，其等价类为[0],[1]。3定理2.13：设R是A上的等价关系,则(1)对任一aA,有a[a];(2)若aRb,则[a]=[b];(3)对a,bA,如果(a,b)R,则[a]∩[b]=;此定理的(1)说明A中每个元素所产生的等价类是非空的定理的(2)、(3)说明：互相等价的元素属于同一个等价类，而不等价的元素其所对应的等价类之间没有公共元素定理的(4)说明：A上等价关系R所对应的等价类的并就等于A.由此定理说明A上等价关系R所对应的等价类集合是A的一个划分。该定理告诉我们，给定一个等价关系就唯一确定一个划分。定理2.13：设R是A上的等价关系,则此定理的(1)说明4证明：(1)对任一aA，因为R是A上的等价关系，所以有aRa(R自反)，则a[a]。(2)对a,bA,aRb,分别证明[a][b]，[b][a]。对任意x[a](目标证明x[b]，即xRb)。下面证明[b][a]对任意x[b](目标证明x[a]，即xRa)。(3)对a,bA,如果(a,b)R,则[a]∩[b]=采用反证法。假设[a]∩[b]≠，则至少存在x[a]∩[b]。证明：(1)对任一aA，因为R是A上的等价关系，所以有aR5等价关系与划分课件6例：设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={1,2,3,4}，R={(1,1),(2,2),7设非空集A上划分={A1,A2,…,An}，定义A上二元关系R：aRb当且仅当存在Ai,使得a,bAi。即R=(A1A1)∪(A2A2)∪…∪(AnAn)容易证明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)}设非空集A上划分={A1,A2,…,An}，定义A上二元关8定理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,它们通过并和交运算而得到的关系是不是等价关系?若是,其对应的划分与原来的两个划分有何联系。定理2.15:设R1和R2是A上的等价关系,R1=R2当且9四、划分的积与和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的划分,若'的每一块包含在的一块中,称'细分,或称'加细。四、划分的积与和10例：'={{1},{2},{3,4}}，={{1,2},{3,4}}因为{1}{1,2}，{2}{1,2}，{3,4}{3,4}，所以'细分若'细分,则与它们对应的二元关系R'和R它们之间有何联系？例：'={{1},{2},{3,4}}，={{1,2},11(1)若'细分,则与它们对应的二元关系R'和R满足R'R。证明：对任意(a,b)R‘，目标是(a,b)R(2)若R'R，是否有'细分？证明：对任意S‘’,目标是SS‘S定理2.17：设',是A的划分,它们确定A上的等价关系分别为R,R',则'细分当且仅当R'R。(1)若'细分,则与它们对应的二元关系R'和R满足R'12定理2.18：设1,2是A的划分,则(1)1·2细分1与2。(2)设'是A的划分,若'细分1与2,则'细分1·2。证明：(1)设1和2分别对应的A上关系是R1和R2，则1·2对应的关系为R1∩R2。(2)设'对应A上关系是R'，1和2分别对应的A上关系是R1和R2，则1·2对应的关系为R1∩R2。定理2.18：设1,2是A的划分,则132.划分的和设集合A上的等价关系为R1和R2,容易证明R1∪R2是A上的自反和对称关系,但不是A上的等价关系。然而R1∪R2的传递闭包是A上的等价关系。定理2.19:设R1和R2是集合A上的等价关系,则(R1∪R2)+是A上的等价关系。定义2.18:设R1和R2是A上的等价关系,R1和R2确定A的划分分别为1和2。A上的等价关系(R1∪R2)+所确定A的划分称为1与2划分的和,记为1+2。2.划分的和14定理2.20：设1,2是A的划分,则(1)1与2细分1+2；(2)设'是A的划分,若1与2细分',则1+2细分'。证明：(1)设1和2分别对应的A上关系是R1和R2，则1+2对应的关系为(R1∪R2)+

。(2)设'对应A上关系是R'，1和2分别对应的A上关系是R1和R2，则1+2对应的关系为(R1∪R2)+

。定理2.20：设1,2是A的划分,则152.7次序关系集合中还有一种重要的关系：次序关系。它可用来比较集合中元素的次序,其中最常用的是偏序关系和全序关系。1.偏序关系定义2.19,2.20:设R是集合A上的二元关系,若R是自反的,反对称的和传递的,则称R是A上的偏序关系。又记为≤(注意,此符号在这里并不意味着小于或等于)。若集合A具有偏序关系R,则称A为偏序集,记为(A,R)。2.7次序关系集合中还有一种重要的关系：次序关系。它可用16实数集R上的小于或等于关系≦；正整数集Z+上的整除关系；集合A的幂集P(A)上的包含关系。由于它们都是偏序关系，因此(R,≦)(Z+,|),(P(A),)都是偏序集。偏序集必须有一个具体给定的偏序关系例：A={1,2},P(A)={,{1},{2},{1,2}},则A的幂集P(A)上的包含关系{(,),(,{1}),(,{2}),(,{1,2}),({1},{1}),({1},{1,2}),({2},{2}),({2},{1,2}),({1,2},{1,2})}实数集R上的小于或等于关系≦；17定义：对于集合A上的偏序关系R,如果A中两个元素a,b有aRb,则称a与b是可比较的。在上例中，与,{1},{2}与{1,2}都是可以比较的，而{1}与{2}无包含关系，故不可比较由此可见：偏序集合中任意两个元素不一定可比较的。但对于实数集上的小于或等于关系≦，对任意两个实数x,y,或者x≦y,或者y≦x，必有一个成立，故x和y是可以比较的。全序关系定义：对于集合A上的偏序关系R,如果A中两个元素a,b有a18定义2.22,2.23：设≤是集合A上的二元关系,如果对于A中任意两个元素a,bA,必有a≤b或b≤a,则称≤是A上的全序关系(或称线性次序关系)。而该集合称为全序集或线性次序集,记为(A,≤)。整数集I上的小于或等于关系≦是全序关系,但I上的整除关系/不是全序关系。而前面给出的幂集P(A)上的关系也不是全序关系。定义2.22,2.23：设≤是集合A上的二元关系,如果对192．Hasse图偏序集(A,R)可以通过图形表示,该图叫哈斯图。是对关系图的简化。(1)由于偏序关系是自反的，即对每个元素a,都有aRa，因此在图上省去自环(2)由于偏序关系是传递的，即若有aRb,bRc则必有aRc,因此省去a与c之间的连线(3)对于aRb,规定b在a的上方，则可省去箭头。这样的图称为哈斯图。2．Hasse图20A={1,2},画出A的幂集P(A)上的包含关系的哈斯图P(A)={,{1},{2},{1,2}}A={1,2},画出A的幂集P(A)上的包含关系的哈斯图21例A={2,3,6,12,24,36},画出偏序集(A,/)的哈斯图。例A={2,3,6,12,24,36},画出偏序22设A上的小于等于关系≦,A={1,2,3,4,5,6},画出偏序集(A,≦)的哈斯图。设A上的小于等于关系≦,A={1,2,3,4,5,233.拟序关系定义2.21:集合A上的二元关系R是反自反的和传递的,称R为A上的拟序关系。称(A,R)为拟序集,或记为(A,<)(注意,此符号<在这里也不意味着小于)。常见的拟序关系有：实数集R上的小于关系<；集合A的幂集P(A)上的真包含关系。3.拟序关系24定理2.2