[音乐] 嗨,欢迎回来。 那么我们上一节呢,我们提到了这个等价关系以及 这个等价类,而且呢说明了等价类之间,它们有一种 类似于这种切蛋糕,所以呢它是说等价类要么之间,它们之间呢是完全重复, 或者呢,说等价类之间呢不会共享任何的这个元素。 所以呢我们就把这个切蛋糕这件事情, 再进行一个型化,更准确的一个说法, 所以引入了这个概念,叫做划分。 那什么叫划分呢?划分呢是集合 A 的一个子集族, 所以呢划分它首先是一个集合族。 那么其次呢,它的每一个成员都是 A 的一个子集,所以呢它叫做子集族, 那么一般我们用 π 来代表这个划分。 那我们来看看它满足什么样的条件呢?首先,第一 叫做不空。 什么是不空呢?就是它的成员 不可能是一个空集。 也就是说任意的 B ,B∈ π ,那么蕴含呢 B ≠ ∅。 也就空集不能够作为子集族 π 的一个成员。 第二个呢是把这个 π 呢进行广义并,然后正好等于 A。 也就是说它的这个子集族的成员取 一个大的一个并集之后,它恰好要能够完整的覆盖这个 A。 所以呢,称作为不漏,不被漏掉 A 当中的任何 元素。 第三呢,是任何 B ,任何的 B' , B 呢是 B' 都属于 π。 那么,而且呢 B 和 B' 是不相等的话,那么就意味着 B 和 B' 的交集是空集。 那么这就是第三个,叫做不交,也就是子集族它的这个子集之间 不会有任何的这个交集。 所以呢划分呢是适合于 具有如下三个性质的这个子集族,也就是不空,不漏,不交。 那么我们就把这个 π 当中的这个元素,也就是 A 的子集,就称之为一个划分的一个单元,这个单元。 那么我们特别约定,如果 A 是空集的话,那么就只有一个空划分,就是空集。 我们来看看一些划分的例子。 比如说 A 呢等于{ 1, 2, 3, 4 }, 那么第一个 π1 那就等于{{ 1 }, { 2 }, { 3 }, { 4 }},那么都是单元集。 那我们发现它有不空,它没有空集在里头; 不交,它们之间的交集为空;不漏,它们的这个并集正好等于 A。 然后 π2 = {{ 1, 3 }, { 2, 4 }}, { 1, 3 }和{ 2, 4 },那这也是一个划分的例子, 它的每一个单元也都符合不空,不交,不漏的这个特性。 π3 = {{ 1, 3, 4 }, { 2 }}, 那么这个划分里头呢就有两个单元,它有两个单元。 那么还有呢 π4 ,就是{{ 1, 2, 3, 4 }},就是把这个 A 呢,整个的放在这儿。 那当然,它的单元数为 1 ,它也是不空,不交,不漏的。 那么我们来看看如果是{{ 1, 2 }, { 4 }},它是不是一个划分呢? 那么显然不是,因为它虽然满足不空,不交, 但是呢它不满足不漏,它漏了一个元素 3 ,对吧? 那么这一题,{{ 1, 2, 3 }, { 2, 4 }}, 请你在题目当中来选择一下。 然后很明显呢就是我们如果把 这个划分单元和这个等价关系的这个等价类来进行一个对比, 我们就能够知道这个等价关系 R 的所有的等价类,如果把它做成一个集合的话, 那么就正好能够构成 A 的一个划分。 因为等价类它正好满足,每个等价类它至少都有一个元素吧, 就是自身,所以呢,它满足不空; 那么等价类之间呢,它不会有共享的元素,所以呢它也不交; 那么等价类会覆盖所有的 A 当中的元素,所以它也不漏。 所以呢 A 上的等价关系所包含的所有的等价类,把它收集在一起形成一个集合族, 那么它显然就能够构成 A 上的一个划分。 那么我们就把这种划分就称作为是 等价关系 R 所对应的一个划分。 那么这个呢定义就是这样,所有的 x ∈ A , 那么 x 的等价类, x 作为代表元素的等价类,把它们所有都放在一起, 那么这样的一个集合,它就是一个划分。 那么这个呢就是 等价关系 R 所对应的一个划分。 那么反过来,因为这个划分的单元它满足不空,不交,不漏 这些它们之间的关系。 那么显然呢它也类似于这个等价类,所以呢 A 上的一个划分 π ,它也会对应 A 上的一个等价关系 R。 那么这个呢就称之为划分 π 所对应的 等价关系。 那么这个呢定义为,说 R 等于然后{< x, y >},然后这个 x 呢,和 y 呢是都是属于同一个划分单元, 同一个划分单元。 那这样呢我们就明白了, 它属于同一个划分单元的话,那么在等价关系里面它就会属于同一个 等价类,对吧?那么所以呢有另外一种表达方式,就是把这个 划分单元,每一个划分单元进行这个笛卡尔积, 笛卡尔积以后得到的这个二元组,把它全部进行一个 广义并,给它并在一起,那这样呢也 能够得到一个等价关系。 那么我们就把这种 由划分 π 所推出来的等价关系就称之为划分所对应的 等价关系。 那么现在我们正过去有等价关系 对应的划分 π ,那么反过来也有 划分 π 所对应的等价关系,那么我们显然就会 有一个疑问,它们是不是一一对应的呢?那 这个表述就是这样,对应 π 的等价关系为 R 的话,那么当且仅当 R 对应 的划分正好为 π,这个呢就表示它们一一对应。 那我们的结论是, 对,确实是这样的,等价关系和划分是一一对应的。 我们可以来证明这一点。 首先呢我们来证明一个必要性,也就是 从左到右。 我们先假设这个对应 π 的这个等价关系为 R , 那么这个 R 呢它显然也会对应一个划分 π , 那么我们就把这个划分呢记作为 π'。 那么现在我们要证明这个 π 是等于 π' , 如果能够得到证明,那么好,这个必要性就完成了。 那我们就从这个 A 当中取出任意一个元素小 a ,那么这个小 a ,既然 π 是这个 A 的划分,那么小 a 呢肯肯定会属于,因为不漏嘛, 它肯定就是属于 π 当中的一个单元,某一个单元。 那我们就把这个包含 a 的单元就称作为 B ,包含 a 的单元 B ,B 是属于 π 的。 那么 π' 既然也是一个划分,那么它肯定也有某一个单元包含 了 a ,那么我们就把这个包含了 a 的单元就记作为 π'。 接下来如果我们能够证明说 B 等于 B' 的话, 那么我们就可以证明说,因为 a 的这个任意性, 所以 π 是等于 π' 的。 我们现在来看看怎么证明 B 等于 B'。 B 等于 B' 呢是这样,我们从左半部开始。 左半部呢表示说 π 所对应的等价关系是 R ,所以呢 在 B 当中取出一个元素小 b ,那么它 肯定会有 aRb ,因为 a 也属于 B ,b 也属于 B ,所以会有 aRb。 那么右半部来看, R 所对应的这个划分是 π' , 那么也就是说它这个 b 呢是属于 某一个 a 所在的这个等价类, b 属于 a 所在的等价类,那么就意味着 b 是属于 B' 的, 属于 B' ,然后呢中间呢有一个桥梁把它们搭在一起。 也就是既然有 aRb ,那么就说明呢 a 和 b 是在同一个等价类里边, 在这个 R 的这个等价类里。 所以呢有 b 属于 a 的等价类, a 在 R 当中的等价类。 所以这样呢给它搭在一起,那么全部都是逻辑等价。 所以呢我们就从 b ∈ B ,然后得到了 b ∈ B' ,因为呢 a 是任意的,所以呢我们说 π 等于 π' ,这样呢我们就证明了这个必要性。 接下来我们来看如何证明这个充分性。 也就是说我们假设 R 所对应的划分是 π , 而 π 所对应的等价关系是 R' ,那么我们要证明 R = R'。 那么思路也是一样的,我们在 A 当中任意取出两个元素 a, b , 那当然这个虽然说是两个元素 a, b 啊,我们 并没有说这个 a, b 肯定是不一样的,它也许是一样的,但是这个呢不影响我们的证明。 那么 a, b ,那么有 aRb 的话, 如果 aRb 的话,那么就等价于 b 呢是属于 a 的所在的等价类, a 所在的等价类。 那么既然这个 R 所对应的划分是 π 的话, 那么这个 a 所在的等价类呢必然是 π 的一个划分单元。 所以我们就会有存在 B , B 是属于 π 的,然后 aR 呢等于 B , 并且呢,小 b 是属于这个大 B , 因为小 b 呢是在这个 aR 里面的, 对吧?那么我们把中间这个 aR 等于 B 给它这个做一个转换, 也就是说 a 作为代表元素的这个等价类既然等于这个划分单元了, 那么也很明显,这个 a 作为代表元素是属于这个 B 的,我们就把中间这个式子变成这个。 那么接下来我们就用刚才的条件,就是 π 所对应的等价关系是 R'。 那么既然π 所对应的等价关系是 R' ,而且呢 a 和 b ,小 a , 小 b 都是属于 π 当中的 同一个划分单元,那么很显然它在 R' 当中 是具有 aR'b 的, 具有 aR'b。 所以呢那这一系列的这个逻辑等价下来, 我们就有了 aRb 是逻辑等价于 aR'b , 那么这个呢就证明了说 R 是等于 R' 的。