近世代数之等价关系与集合的分类优秀PPT.ppt

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