2.6 等价关系与划分
本章目录 · 1 节
本章导读
定义2.6.1:在非空集合 上,同时满足自反、对称和传递的关系称为等价关系。若 ,说 关于 等价于 ,可记为 。等价关系把对象按同一种判断标准归类;它不要求对象本身相等,分类标准也必须明确。
【例2.6.1】在 上,定义 当且仅当 ,证明这是等价关系并观察关系图。
解:,所以自反;若3整除 ,也整除 ,所以对称;若3分别整除 、,则整除二者之和 ,所以传递。图分成 、 和 三组,每组内每个顶点都有自环,任意两个不同顶点都有双向边,不同组之间没有边。
定义2.6.2:对等价关系 和 ,集合 称为 关于 的等价类,简称 。它是一个由与 等价的全部元素构成的集合,而不是一个被任选的代表元素。在同一等价类中任选不同代表,得到的类完全相同。
上一例中,,,。这里代表必须属于底集 ;虽然0与3模3同余,但0不在这个有限底集中,不能不加说明就把0也写成该底集中的代表。
把底集改为全体整数 ,并固定正整数 ,可定义整数上的模 等价关系 。除法定理保证每个整数都有唯一表示 ,其中 、。负数同样按非负余数划分,例如 ,所以 与1同属模3余数为1的类。全部等价类为
这里每类都是无限集合,但类的总数是有限的 个。底集有限时,类只包括底集中的对应元素;底集为整数集时,类包括所有对应的整数,不能混用这两个范围。
定理2.6.1:等价类有四项基本性质:(1) 是 的非空子集;(2)若 ,则 ;(3)若 与 不等价,则 ;(4)。
第一项由自反性得到 。证明第二项,若 ,即 ,由 的对称性得到 ,再用传递性得到 ,所以 ;交换 可得反向包含。第三项可反证:若有 同时属于两类,则 、,再用对称与传递推出 ,与不等价矛盾。第四项中,每个类都包含于 ,且每个元素都属于自身的类,所以类的并恰等于 。
因此任意两个等价类要么完全相同,要么完全不交,不会出现只重叠一部分的情况。还可得到 当且仅当 :反向利用 即可。
定义2.6.3:以全部不同等价类为元素构成的集合称为商集,记为
重复出现的相同等价类只保留一次。上一例的商集是 ,有三个元素,每个元素本身又是一个集合;不能把商集写成 而不解释代表与等价类之间的区别。整数模 的商集由上述 个不同余数类组成。
定义2.6.4:若非空集合 的子集族 满足 、不同成员两两不交、,则称 为 的一个划分,成员称为划分块。三个条件分别要求没有空块、没有重复归属、没有遗漏元素;同时 已排除了含底集外对象的块。
【例2.6.2】设 ,判断下列集族是否为划分:,,,,,。
解:只有 是划分。 的两块共同包含 ; 漏掉 ; 含空块; 的第一块含对象 ,它不是给定底集的元素,所以甚至不满足 。这里仍按字母代表彼此不同的基本对象理解。
等价关系与划分一一对应。等价关系的商集因上述定理满足划分的三个条件。反过来,给定划分 ,令 当且仅当 在同一划分块中:每个元素恰在一块内保证自反;同块关系显然对称;若 同块且 同块,两块因共同含 必相同,所以 同块,保证传递。所得关系的等价类恰好是原来的划分块,因此两种构造互相恢复,既没有多算也没有遗漏。
【例2.6.3】给出 上全部等价关系。
解:先按划分块数列出全部划分。一块时只有 ;两块时,单元素块可分别为1、2或3,得到 、、;三块时只有 ,共五个。
相应的等价关系依次为 、、、、。任何等价关系均由某一划分唯一得到,所以上述五个就是全部结果,不只是一组举例。
