等价关系与集合的分类课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,18,18,18,18,18,目录,退出,下一页,上一页,最后一页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,三、集合的等价 关系与分类,定理,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,-,等价类,三、集合的等价 关系与分类 定理1,一、等价关系,元素的一个条件如果对 中任意一个有序元素对,的一个关系,(relation),如果 与 满足条件 ，则称,与 有关系 ，记作 ；否则 称 与无关系 关,系 也称为二元关系,，我们总能确定 与 是否满足条件 ，就称 是,定义,1.1.1,设 是一个非空集合,是关于 的,一、等价关系元素的一个条件如果对 中任意一个有序元素,例,1,设 是一个非空集合， 的所有子集组成的,集合记为 因为对 的任意两个子集 ， ，,或 有且仅有一个成立，所以集合的包含关系“ ”,是 的一个关系进一步讨论可以发，这个关系还,具有下面两条性质：,(1),反身性，即对 的任一子集 ，有 ；,(2),传递性,即对 的任意子集, , ,如果, ,则有 ,例1设 是一个非空集合， 的所有子集组成的 集合记为,例,2,在整数集 中,规定 因为,这个关系也具有反身性和传递性,例,3,在整数集 中,规定,(,即 与 互,素,), 因为 与 有且仅有一个成立,所,以是 的一个关系这个关系既不满足反身性也不满,足传递性,但却满足所谓的对称性,即对任意两个整数,由 ，可推出 ,与 有且仅有一个成立,所以“,|”,是 的一个关系,例2 在整数集 中, 规定,定义,1.1.2,设 是 非空集合的一个关系,如,果 满足,(E1),反身性,即对任意的,有 ；,(E2),对称性,即若,则 ；,(E3),传递性,即若,且,则 ,则 称是 的一个,等价关系,(equivalence relation),并且如果,则称 等价于,记作 ,定义1.1.2设 是 非空集合的一个关系, 如,定义,1.1.3,如果是集合 的一个等价关系,对,令,称子集 为 的一个,等价类,(equivalence class),的全体等价类的集合称为集合 在等价关系下的,商集,(quotient set),记作 ,定义1.1.3如果是集合 的一个等价关系, 对,例,易知,三角形的全等,相似,数域 上 阶,方阵的相等,相似等都是等价关系,而例,1,例,2,例,3,所述的关系都不是等价关系,例易知, 三角形的全等,相似, 数域 上 阶方阵的相,例,设 是正整数,在整数集 中,规定,这个关系为,同余关系,(congruence relation) ,并记作,(2),若,则 ；,(3),若,有,则 ,与 等价当且仅当 与 被 除有相同的余数,因此称,所以 是 的一个等价关系,显然,(1),对任意整数,则,(,读作“ 同余于,模 ”,),整数的同余关,系及其性质是初等数论的基础,例设 是正整数, 在整数集 中, 规定这个关系为同,二、集合的分类,定义,1.1.4,如果非空集合 表成若干个两两不,相交的非空子集的并,则称这些子集为集合 的一种,分类,(partition),其中每个子集称为一个,类,(class).,如果,的子集族 构成 的一种分类,则记作,二、集合的分类定义1.1.4如果非空集合 表成若干个两,例,6,设 为数域 上全体 阶方阵的集合,令,表示所有秩为 的 阶方阵构成的子集,.,(1) ;,(2),所以 是 的一种分类,例,7,是整数集 的一,种分类,例6 设 为数域 上全体 阶方阵的集,于,且,同一元素在两个子集中重复出现,例,8,对实数集,令子集, .,由,所以 不是 的一种分类,于 ,且 , 同一元素在,三、集合的等价关系与集合的分类这两个概念之间,联系,定理,1.1.1,集合 的任何一个等价关系都确定,了 的一种分类,且其中每一个类都是集合 的一个等,价类,.,反之,集合 的任何一种分类也都给出了集合,的一个等价关系,且相应的等价类就是原分类中的那,些类,三、集合的等价关系与集合的分类这两个概念之间 联系定理1.1,证,首先,为 集合的一个等价关系,则,(1),对任意的,由反身性知,所以,(2),如果,从而由对称性知 再由传递性知,又对任意的,则,.,这说明,不同的类没有公共元素,.,于是,因此,.,则有 ,同理,所以,于是,同样由传递性得,证首先, 为 集合的一个等价关系, 则 (1,从而由,(P1), (P2),知,全体等价类形成的 一种,分类,显然每一个类都是 的等价类,其次,如果已知集合 的一种分类,在 中规,定关系“”：,对任意的,由于 与本身属于同一类,所以,.,如果,即 与 属于同一类,自然 与 也,属于同一类,所以,.,最后,如果, ,从而由 (P1), (P2)知, 全体等价类形成的,即 与 属于同一类,与 属于同一类,因而 与 同在,所在的类中,所以 因此“”是 的一个等价,关系,.,显然,由此等价关系得到的等价类就是原分类中,那些类,即 与 属于同一类, 与 属于同一类,因而,例,设 试确定集合 上的全部等价,关系,解,由,定理,1.1.1,知，只要求出的 全部分类,也,即求出的 所有可能的子集分划即可,(1),如果 分划为一个子集,则有,;,(2),如果 分划为两个子集,则有,(3),如果 分划为三个子集,则有,例设 试确定集合,因此,上共有五个不同的等价关系,它们是,因此, 上共有五个不同的等价关系, 它们是,参考文献及阅读材料,1,闵嗣鹤,严士健 初等数论（第版）北京,:,高等教育出版社, 1990,本书的第,1,章有关于整数整除性的详细讨论,第,3,章,则介绍了同余的概念及其性质,2 AignerM.Combinatorial,Theory:Springer-Verlag;New,York:Heiderberg,1979,参考文献及阅读材料1闵嗣鹤, 严士健 初等数论（第,