1、1 1 1 1 1目录退出下一页上一页最后一页 三、集合的等价三、集合的等价 关系与分类关系与分类 定理1.1.1 -类 例7 例8 例9 二、集合的分类二、集合的分类 定义1.1.4 -集合的分类 例3 例61.11.1 等价关系与集合的分类等价关系与集合的分类 一、等价关系一、等价关系 定义1.1.1 -关系 定义1.1.2 -等价关系 例1 例2 例5 例4 定义1.1.3 -等价类2 2 2 2 2目录退出下一页上一页最后一页一、等价关系一、等价关系元素的一个条件如果对 中任意一个有序元素对 S 的一个关系(relation)如果 与 满足条件 ，则称 Saba与 有关系 ，记作 ；否
2、则 称 与无关系 关 babab系 也称为二元关系 ，我们总能确定 与 是否满足条件 ，就称 是 , a bab定义定义1.1.1设 是一个非空集合, 是关于 的 SS3 3 3 3 3目录退出下一页上一页最后一页例例1设 是一个非空集合， 的所有子集组成的 SSA集合记为 因为对 的任意两个子集 ， ， ( )P SSBAB或 有且仅有一个成立，所以集合的包含关系“ ” AB是 的一个关系进一步讨论可以发，这个关系还 ( )P S具有下面两条性质：(1) 反身性，即对 的任一子集 ，有 ；SAAA(2) 传递性, 即对 的任意子集 , , , 如果 SA B C , ,则有 ABBCAC4
3、4 4 4 4目录退出下一页上一页最后一页例例2 在整数集 中, 规定 因为 a b|a b|a b这个关系也具有反身性和传递性 例例3 在整数集 中, 规定 ( 即 与 互 a bab素) 因为 与 有且仅有一个成立, 所 ,1a b ,1a b 以是 的一个关系这个关系既不满足反身性也不满 足传递性, 但却满足所谓的对称性, 即对任意两个整数 ,由 ，可推出 , a b,1a b ,1b a 与 有且仅有一个成立, 所以“|”是 的一个关系 |a b5 5 5 5 5目录退出下一页上一页最后一页定义定义1.1.2设 是 非空集合的一个关系, 如 S果 满足 (E1) 反身性, 即对任意的
4、, 有 ；aSa a(E2)对称性, 即若 , 则 ； a bb a(E3) 传递性, 即若 ,且 ,则 a bb ca c则 称是 的一个等价关系等价关系(equivalence relation), S并且如果 ,则称 等价于 ,记作 a babab6 6 6 6 6目录退出下一页上一页最后一页定义定义1.1.3如果是集合 的一个等价关系, S对 , 令 aS |axS xa 称子集 为 的一个等价类等价类 (equivalence class) aSS的全体等价类的集合称为集合 在等价关系下的商集商集 S(quotient set), 记作 / S7 7 7 7 7目录退出下一页上一页最
5、后一页例例易知, 三角形的全等,相似, 数域 上 阶n方阵的相等,相似等都是等价关系, 而例1,例2,例3所述的关系都不是等价关系 8 8 8 8 8目录退出下一页上一页最后一页例例设 是正整数, 在整数集 中, 规定m这个关系为同余关系同余关系 (congruence relation) , 并记作 |m aa (2) 若 , 则 ； |m ab|m ba(3) 若 , |m ab有 , 则 |m bc|m acZ与 等价当且仅当 与 被 除有相同的余数, 因此称所以 是 的一个等价关系,显然 ababm|,a bm aba b (1)对任意整数 , a则(读作“ 同余于 , 模 ”)整数的
6、同余关 modabmabm系及其性质是初等数论的基础 9 9 9 9 9目录退出下一页上一页最后一页二、集合的分类二、集合的分类定义定义1.1.4如果非空集合 表成若干个两两不 S相交的非空子集的并, 则称这些子集为集合 的一种 S分类分类 (partition),其中每个子集称为一个类类 (class). 如果 S 的子集族 构成 的一种分类,则记作|iSiIS|iSiI 1010101010目录退出下一页上一页最后一页例例6 设 为数域 上全体 阶方阵的集合,令 MFn 表示所有秩为 的 阶方阵构成的子集. rMrn(1) ;0niiMM(2) ,ijMMij所以 是 的一种分类|0,1,
7、iMinM例例7 是整数集 的一 |0,1,2,1ma am 种分类 1111111111目录退出下一页上一页最后一页于 ,且 , 同一元素在两个子集中重复出现, iiR1iiR例例8 对实数集 , 令子集 , .由 R,1iRi ii 所以 不是 的一种分类 ,1 |i iiR1212121212目录退出下一页上一页最后一页三、集合的等价关系与集合的分类这两个概念之间三、集合的等价关系与集合的分类这两个概念之间 联系联系定理定理1.1.1集合 的任何一个等价关系都确定 S了 的一种分类,且其中每一个类都是集合 的一个等 SS价类.反之,集合 的任何一种分类也都给出了集合 SS的一个等价关系,
8、且相应的等价类就是原分类中的那 些类 1313131313目录退出下一页上一页最后一页设证证首先, 为 集合的一个等价关系, 则S (1) 对任意的 , 由反身性知 , 所以 aS aa a sSa(2) 如果 , ab , ,cb ca从而由对称性知 再由传递性知 ,bc .ba又对任意的 ,则 , bbbbba.这说明, 不同的类没有公共元素 .于是 , 因此 . ba ba cab则有 同理 , 所以 ab ab于是同样由传递性得1414141414目录退出下一页上一页最后一页从而由 (P1), (P2)知, 全体等价类形成的 一种 S分类,显然每一个类都是 的等价类 S其次, 如果已知
9、集合 的一种分类 , 在 中规 SS定关系“”： ,.ababa bS与 属于同一类，对任意的 , 由于 与本身属于同一类, 所以 aSa.如果 , 即 与 属于同一类, 自然 与 也 aaababba属于同一类, 所以 . 最后, 如果 , , baabbc1515151515目录退出下一页上一页最后一页即 与 属于同一类, 与 属于同一类,因而 与 同在 abbcac 所在的类中, 所以 因此“”是 的一个等价 bacS关系.显然, 由此等价关系得到的等价类就是原分类中那些类1616161616目录退出下一页上一页最后一页例例设 试确定集合 上的全部等价 , ,Sa b cS关系 解解由定
10、理1.1.1知，只要求出的 全部分类,也 S即求出的 所有可能的子集分划即可 S(1) 如果 分划为一个子集, 则有 ;S 1S (2) 如果 分划为两个子集, 则有S 234,;ab cba cca b (3) 如果 分划为三个子集, 则有 S 5,abc 1717171717目录退出下一页上一页最后一页因此, 上共有五个不同的等价关系, 它们是S1 , , , , , , , , aa bb cc ab ba ac ca bc cb2 , , , , aa bb cc bc cb3 , , , , aa bb cc ac ca4 , , , ,aa bb cc ab ba5 , , aa bb cc1818181818目录退出下一页上一页最后一页参考文献及阅读材料参考文献及阅读材料1闵嗣鹤, 严士健 初等数论（第版）北京: 高等教育出版社, 1990 本书的第1章有关于整数整除性的详细讨论, 第3章 则介绍了同余的概念及其性质 2 AignerM.Combinatorial Theory:Springer-Verlag;New York:Heiderberg,1979
