等价关系与集合的分类.ppt

三 集合的等价关系与分类 定理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 等价类 一 等价关系 元素的一个条件 如果对中任意一个有序元素对 的一个关系 relation 如果与满足条件 则称 与有关系 记作 否则称与无关系 关 系也称为二元关系 我们总能确定与是否满足条件 就称是 定义1 1 1设是一个非空集合 是关于的 例1设是一个非空集合 的所有子集组成的 集合记为 因为对的任意两个子集 或有且仅有一个成立 所以集合的包含关系 是的一个关系 进一步讨论可以发 这个关系还 具有下面两条性质 1 反身性 即对的任一子集 有 2 传递性 即对的任意子集 如果 则有 例2在整数集中 规定 因为 这个关系也具有反身性和传递性 例3在整数集中 规定 即与互 素 因为与有且仅有一个成立 所 以是的一个关系 这个关系既不满足反身性也不满 足传递性 但却满足所谓的对称性 即对任意两个整数 由 可推出 与有且仅有一个成立 所以 是的一个关系 定义1 1 2设是非空集合的一个关系 如 果满足 E1 反身性 即对任意的 有 E2 对称性 即若 则 E3 传递性 即若 且 则 则称是的一个等价关系 equivalencerelation 并且如果 则称等价于 记作 定义1 1 3如果 是集合的一个等价关系 对 令 称子集为的一个等价类 equivalenceclass 的全体等价类的集合称为集合在等价关系下的商集 quotientset 记作 例 易知 三角形的全等 相似 数域上阶 方阵的相等 相似等都是等价关系 而例1 例2 例3所述的关系都不是等价关系 例 设是正整数 在整数集中 规定 这个关系为同余关系 congruencerelation 并记作 则 1 对任意整数 则 读作 同余于 模 整数的同余关 系及其性质是初等数论的基础 二 集合的分类 定义1 1 4如果非空集合表成若干个两两不 相交的非空子集的并 则称这些子集为集合的一种 分类 partition 其中每个子集称为一个类 class 如果 的子集族构成的一种分类 则记作 例6设为数域上全体阶方阵的集合 令 表示所有秩为的阶方阵构成的子集 1 2 所以是的一种分类 例7是整数集的一 种分类 于 且 同一元素在两个子集中重复出现 例8对实数集 令子集 由 所以不是的一种分类 三 集合的等价关系与集合的分类这两个概念之间 联系 定理1 1 1集合的任何一个等价关系都确定 了的一种分类 且其中每一个类都是集合的一个等 价类 反之 集合的任何一种分类也都给出了集合 的一个等价关系 且相应的等价类就是原分类中的那 些类 证首先 为集合的一个等价关系 则 1 对任意的 由反身性知 所以 2 如果 从而由对称性知再由传递性知 又对任意的 则 这说明 不同的类没有公共元素 于是 因此 则有 同理 所以 于是 同样由传递性得 从而由 P1 P2 知 全体等价类形成的一种 分类 显然每一个类都是的等价类 其次 如果已知集合的一种分类 在中规 定关系 对任意的 由于与本身属于同一类 所以 如果 即与属于同一类 自然与也 属于同一类 所以 最后 如果 即与属于同一类 与属于同一类 因而与同在 所在的类中 所以 因此 是的一个等价 关系 显然 由此等价关系得到的等价类就是原分类中 那些类 例 设试确定集合上的全部等价 关系 解由定理1 1 1知 只要求出的全部分类 也 即求出的所有可能的子集分划即可 1 如果分划为一个子集 则有 2 如果分划为两个子集 则有 3 如果