近世代数集合的等价------关系与分类

前页前页前页1目录后页返回1前页三、集合的等价关系与分类定理1.1.1---类例7例8例9二、集合的分类定义1.1.4---集合的分类例3例6§1.1等价关系与集合的分类一、等价关系定义1.1.1---关系定义1.1.2---等价关系例1例2例5例4定义1.1.3---等价类前页前页前页2目录后页返回2前页一、等价关系元素的一个条件．如果对中任意一个有序元素对S的一个关系(relation)．如果与满足条件，则称Saba与有关系，记作；否则称与无关系．关babab系也称为二元关系．，我们总能确定与是否满足条件，就称是,abab定义1.1.1设是一个非空集合,是关于的SS前页前页前页3目录后页返回3前页例1设是一个非空集合，的所有子集组成的SSA集合记为．因为对的任意两个子集，，()PSSBAB或有且仅有一个成立，所以集合的包含关系“”AB是的一个关系．进一步讨论可以发，这个关系还()PS具有下面两条性质：(1)反身性，即对的任一子集，有；SAAA(2)传递性,即对的任意子集,,,如果SABC,,则有．ABBCAC前页前页前页4目录后页返回4前页例2在整数集中,规定．因为ab|ab|ab这个关系也具有反身性和传递性．例3在整数集中,规定(即与互abab素)．因为与有且仅有一个成立,所,1ab,1ab以是的一个关系．这个关系既不满足反身性也不满足传递性,但却满足所谓的对称性,即对任意两个整数,由，可推出．,ab,1ab,1ba与有且仅有一个成立,所以“|”是的一个关系．|ab前页前页前页5目录后页返回5前页定义1.1.2设是非空集合的一个关系,如S果满足(E1)反身性,即对任意的,有；aSaa(E2)对称性,即若,则；abba(E3)传递性,即若,且,则．abbcac则称是的一个等价关系(equivalencerelation),S并且如果,则称等价于,记作．abab~ab前页前页前页6目录后页返回6前页定义1.1.3如果～是集合的一个等价关系,S对,令aS|~axSxa称子集为的一个等价类(equivalenceclass)．aSS的全体等价类的集合称为集合在等价关系下的商集S(quotientset),记作．/~S前页前页前页7目录后页返回7前页例４易知,三角形的全等,相似,数域上阶n方阵的相等,相似等都是等价关系,而例1,例2,例3所述的关系都不是等价关系．前页前页前页8目录后页返回8前页例５设是正整数,在整数集中,规定m这个关系为同余关系(congruencerelation),并记作|maa(2)若,则；|mab|mba(3)若,|mab有,则．|mbc|macZ与等价当且仅当与被除有相同的余数,因此称所以是的一个等价关系,显然ababm|,,abmabab(1)对任意整数,a则(读作“同余于,模”)．整数的同余关modabmabm系及其性质是初等数论的基础前页前页前页9目录后页返回9前页二、集合的分类定义1.1.4如果非空集合表成若干个两两不S相交的非空子集的并,则称这些子集为集合的一种S分类(partition),其中每个子集称为一个类(class).如果S的子集族构成的一种分类,则记作|iSiIS|iSiI前页前页前页10目录后页返回10前页例6设为数域上全体阶方阵的集合,令MFn表示所有秩为的阶方阵构成的子集.rMrn(1);0niiMM(2)．,ijMMij所以是的一种分类．|0,1,,iMinM例7是整数集的一|0,1,2,,1maam种分类．前页前页前页11目录后页返回11前页于,且,同一元素在两个子集中重复出现,iiR1iiR例8对实数集,令子集,.由R,1iRiii所以不是的一种分类．,1|iiiR前页前页前页12目录后页返回12前页三、集合的等价关系与集合的分类这两个概念之间联系定理1.1.1集合的任何一个等价关系都确定S了的一种分类,且其中每一个类都是集合的一个等SS价类.反之,集合的任何一种分类也都给出了集合SS的一个等价关系,且相应的等价类就是原分类中的那些类．前页前页前页13目录后页返回13前页~设证首先,为集合的一个等价关系,则S(1)对任意的,由反身性知,所以aSaaasSa(2)如果,ab~,~,cbca从而由对称性知再由传递性知~,bc~.ba又对任意的,则,'bb'~bb'~ba.这说明,不同的类没有公共元素．.于是,因此.'babacab则有．同理,所以abab于是同样由传递性得前页前页前页14目录后页返回14前页从而由(P1),(P2)知,全体等价类形成的一种S分类,显然每一个类都是的等价类．S其次,如果已知集合的一种分类,在中规SS定关系“～”：~,.abababS与属于同一类，对任意的,由于与本身属于同一类,所以aSa.如果,即与属于同一类,自然与也~aa~ababba属于同一类,所以.最后,如果,,~ba~ab~bc前页前页前页15目录后页返回15前页即与属于同一类,与属于同一类,因而与同在abbcac所在的类中,所以．因此“～”是的一个等价b~acS关系.显然,由此等价关系得到的等价类就是原分类中那些类．前页前页前页16目录后页返回16前页例９设试确定集合上的全部等价,,,SabcS关系．解由定理1.1.1知，只要求出的全部分类,也S即求出的所有可能的子集分划即可．S(1)如果分划为一个子集,则有;S1S(2)如果分划为两个子集,则有S234,,,,,,,,;abcbaccab(3)如果分划为三个子集,则有S5,,abc前页前页前页17目录后页返回17前页因此,上共有五个不同的等价关系,它们是S1~~,~,~,~,~,~,~,~,~aabbccabbaaccabccb2~~,~,~,~,~aabbccbccb3~~,~,~,~,~aabbccacca4~~,~,~,~,~aabbccabba5~~,~,~aabbcc前页前页前页18目录后页返回18前页参考文献及阅读材料[1]闵嗣鹤,严士健．初等数论（第２版）．北京:高等教育出版社,1990本书的第1章有关于整数整除性的详细讨论,第3章则介绍了同余的概念及其性质．[2]AignerM..CombinatorialTheory:Springer-Verlag;NewYork:Heiderberg,1979