把对象归类,为什么还需要证明
设一个程序存储了许多单词,而某项操作只需要知道单词的长度。保留每个字母,就保留了这项操作不会使用的信息。我们可以把所有长度为三的单词看成一个对象,把所有长度为四的单词看成另一个对象,依此类推。但后续操作若要直接作用于这些组,就必须保证:同一组中的任何单词都给出相同结果。
这里有两个不同的问题。第一,提出的规则是否真的把原集合分成互不重叠的组?第二,操作是否尊重这种分组?等价关系回答第一个问题,公式的良定义性回答第二个问题。给对象加上一对方括号,并不能自动解决其中任何一个问题。
关系及其不同性质
定义 1.2.1
(集合上的二元关系)
集合 上的二元关系是一个子集 ,其中 是所有由 中元素组成的有序对的集合。当 时,记作 。关系的常见性质为:
- 自反性:每个 都满足 ;
- 对称性:对任意 , 蕴含 ;
- 反对称性: 与 同时成立时,必有 ;
- 传递性:对任意 , 与 蕴含 。
同时具有自反性、对称性和传递性的关系称为等价关系。
每个性质都有自己的量词。要否定传递性,必须找到三个元素,使前提中的两个有序对都属于关系,而结论中的有序对不属于关系。如果某个必要前提也不成立,那么仅仅找出一个不属于关系的有序对,并不能反驳传递性。
常见错误
(反对称并非对称的反面)
对称性与反对称性并不是彼此的逻辑否定。相等关系同时具有两者:等式可以反向书写,而两个方向都相等的元素当然是同一元素。整数上的通常大小关系具有反对称性和传递性,却不具有对称性。等价关系一般不具有反对称性,因为它正是为了容许不同元素被视为等价。
例题 1.2.2
(接近不一定能形成分类)
在 上定义 当且仅当 。这个关系自反且对称,但不传递:、 成立, 却不成立。与 有关系的元素组成 ,与 有关系的元素组成 ;这两个集合有交集却不相等。因此,看似表达相似性的规则,未必能把集合划分为若干类。
等价类与集合划分
定义 1.2.3
(等价类与商集)
设 是 上的等价关系。元素 的等价类为
商集 是所有不同等价类组成的集合 。它的元素是 的子集,而不是 原来的单个元素。商映射 把 映为 。
的一个划分,是一族非空、两两不交且并集为 的子集。空集的划分是空族。等价类的代表元是从该类中取出的一个元素;等价类本身是整个子集,并不等于选定的代表元。
定理 1.2.4
(等价关系与集合划分描述同一种分组)
对于 上的等价关系,有
所有不同等价类构成 的一个划分。反过来,每个划分都能定义一个等价关系:两个元素等价,当且仅当它们属于同一个块。这两个构造互为逆过程。
证明
(由关系得到类,由块得到关系)
设 。若 ,则 ,结合 ,由传递性得到 。所以 。由对称性得到 ,同理可得反向包含。若 ,由自反性可知 ,于是 。
每个类都非空,因为 ;每个元素也都属于自己的类。如果两个类有公共元素 ,则 且 。利用对称性和传递性可得 ,所以这两个类相等。因此,不同的类两两不交,而且覆盖整个 。
反过来,给定一个划分,每个元素恰好属于一个块。元素与自己属于同一块,说明关系自反;同属一个块显然具有对称性。如果 属于同一块, 属于同一块,那么这两个块都包含 ,因此必须相等,于是 也属于同一块。这就证明了三个等价关系公理。每个元素的等价类恰好是原来的块,所以两个构造确实互为逆过程。当 为空时,所有结论都按空集的约定成立。
证明透视
为什么一个公共元素就迫使两个类相等
关键不只是每个元素都有所属的类。给定交集中的一个点,对称性让我们转向其中一个代表元,传递性再把它与另一个代表元连接起来。先证明两个代表元等价,才能进一步证明一个类的每个元素都属于另一个类。如果没有传递性,前面“接近”的例子中那种相交而不相等的集合就仍然可能出现。
例题 1.2.5
(余数把无穷多个整数分成有限个类)
固定整数 ,定义 当且仅当 整除 。由于 ,关系具有自反性;把可整除的差取负,得到对称性;把两个可整除的差相加,得到传递性。
记 的类为 。由带余除法,每个整数都有唯一一个位于 的余数。两个整数余数相同,当且仅当它们的差能被 整除。因此,商集 恰有 个元素。例如 ,尽管 是不同整数。每个类都是无限集,但所有类组成的集合是有限集。
常见错误
(类是集合,不是它的代表元)
不能由 推出 :因为 ,两个类是 的同一个子集。类是否相等由关系判定,即 当且仅当 ,而不是比较所选的代表元。选取代表元 也不会使类变小: 是无限集。
合并分类规则时要小心
同一个集合上两个等价关系的交仍是等价关系。一个元素与自己在两个关系中都有关系;反向关系在两者中都成立;两步关系的传递推论也可以分别在两者中使用。取交的含义是:只有两个原规则都判定等价,才把对象分到同一类。对整数而言,要求模二余数相同且模三余数相同,等价于要求模六余数相同。
反例模式
等价关系的并未必是等价关系
声称:同一集合上两个等价关系的并是等价关系。在 上,第一个划分的块为 ,第二个划分的块为 。在并关系中, 经由第一个关系与 有关系, 经由第二个关系与 有关系,但 不属于任何一个,所以并关系不传递。自反性与对称性在并之下仍然保持,因为两者都是逐对检验的。修正方法是改用由并生成的等价关系(见下文),在这个例子中它把三个元素合并为一类。
如果确实需要包含一批指定有序对的最小等价关系,可以这样构造:当两个元素能由有限条指定关系连接起来,而且每条关系允许向任一方向经过时,声明它们等价。允许长度为零的链。零步链保证自反性,反向经过整条链保证对称性,拼接两条链保证传递性。任何包含指定有序对的等价关系,都必须把每条这种链的两个端点判为等价,因此这个构造是最小的。上面的例子中,它把三个元素全部合并。“两个规则都要满足”与“任一规则都可用于连接”,产生的是不同分类。
函数、纤维与信息的丢失
函数 给每个 指定唯一一个 。它的像为 。对于 ,它在 上的纤维是 ;这里的符号表示原像,并不要求存在反函数。像集之外的元素对应空纤维,空纤维不是划分中的块。
若 蕴含 ,则称 为单射;若每个 都有原像,则称它为满射。既单又满的函数称为双射。这些定义要求区分定义域、声明的陪域以及实际的像集。
定理 1.2.6
(每个函数恰好把同一非空纤维内的元素视为等价)
设 ,定义 当且仅当 。这给出一个等价关系,其等价类正是所有非空纤维。函数
是双射。特别地, 为单射,当且仅当它的每个等价类都是单元素集。
证明
(纤维就是等价类)
自反性、对称性和传递性直接来自 中相等关系的对应性质。按照定义, 所在的类由所有函数值为 的输入组成,恰好是在 上的纤维。
检查 是否单射或满射之前,必须先检查它是不是一个函数。若 ,则 ,所以 。输出不依赖代表元的选择。 中每个元素都形如 ,因此映射是满射。如果两个类输出相同,那么它们的代表元有相同的 值,因而等价,所以这两个类相等,证明了单射性。最后,每个纤维都不含两个不同输入,恰好等价于 为单射。
例题 1.2.7
(有限映射、它的等价类与陪域)
设 ,,并规定
非空纤维为 。共有三个等价类, 把它们分别对应到 。在 上的纤维为空。因此,诱导到像集的映射是双射,但原来以 为陪域的函数并不是满射。各类大小也不相同:不能因为第一个类有两个元素,就把六个输入除以二来论证类的总数。
操作什么时候能直接作用于类
现在独立于函数 ,固定 上的一个等价关系 。我们想只保留 ,仍然能够计算 。这恰好要求:分类时丢掉的信息不影响 的值。
定理 1.2.8
(代表元无关性的判据)
存在函数 满足 ,其中 ,当且仅当
若 存在,则它唯一,而且由 给出。
证明
(通过代表元定义函数)
若 且 ,则 ;在两边作用 ,就得到 。反过来,设上述蕴含成立。要给一个类指定 值,可以任取一个代表元 ,使用 。其他代表元都与 等价,因此给出相同值。这就定义了一个函数,且有 。对于唯一性,每个类都形如某个 ;任何满足分解等式的函数都必须把它映到 。证明不需要集合有限这一假设。
例如,字母重排不改变单词长度,所以长度能定义为字母重排等价类上的函数。它不是单射:ab 与 aa 属于不同的重排类,但长度都是二。在非空单词上,“取第一个字母”是一个普通函数,却不能诱导重排类上的函数,因为 ab 与 ba 等价,而首字母不同。
输出也是等价类的情形
设 是 上的等价关系, 是一个普通函数。规则
良定义,当且仅当 蕴含 。证明只需把前面的判据应用于函数 。所需的输出是类,因此必须作为类相等;输出的代表元只需等价,不必是同一个元素。若要求 ,就比实际需要更强了。
例题 1.2.9
(完整检验一个等价类上的算术公式)
设 ,,考虑
这个规则良定义,当且仅当 整除 。对于必要性,取同一个输入的两个代表元 。只有当 时,输出 和 才相等。对于充分性,若 ,则 ;在所给假设下,这个差被 整除。
因此, 是合法规则,因为 。它在 上的输出分别是 ,所以既不是单射,也不是满射。规则 则不合法: 表示同一个输入,却给出不同的输出类。只用代表元 列一张有限表,当然可以定义某个函数,但这不能证明所声称的公式对所有代表元都成立。
练习
快速检查
(在 上,当 为偶数时定义 。列出所有等价类,并计算这个关系包含多少个有序对。)
分别计算每个块内部的有序对,包括对角线上的有序对。
解答 · 答案
等价类为 和 。关系为 ,这里的并是不交并,因此共有 个有序对。如果只数不同元素组成的无序对,就会漏掉对角线上的有序对,并把一个有序对与其逆序对看成同一个对象;这回答的是另一个计数问题。
快速检查
(证明: 上的一个关系同时是等价关系和偏序,当且仅当它就是 上的相等关系。)
偏序具有自反性、反对称性和传递性。利用等价关系额外具备的对称性。
解答 · 答案
若 ,由对称性得 ,再由反对称性得 。因此 除了相等的有序对之外,不含其他有序对。自反性又保证每个相等的有序对都在 中,所以 。反过来,相等关系具有自反性、对称性、反对称性和传递性,因此同时具有这两种结构。论证也适用于 。
快速检查
(设 的划分为 、。一个函数把 映到红色,把 映到蓝色。证明它能诱导商集上的函数。若另一个函数只把 映到红色,其余输入都映到蓝色,还能诱导吗?)
对于失败的规则,给出同一输入类的两个代表元,并比较输出。
解答 · 答案
第一个函数在每个块上都是常值,因此它诱导的函数把类 映到红色,把类 映到蓝色。代表元无关性判据证明其存在,商映射的满射性证明其唯一。对于第二个规则,,但提出的输出分别为红色和蓝色,所以它不能诱导商集上的函数,尽管它在原四元素集合上是一个合法的普通函数。
快速检查
(求所有使规则 良定义的整数 。当 时,求这个商集映射的像,以及每个非空纤维的大小。)
定义域有六个类,陪域有八个类。先检查代表元无关性,再计算输出。
解答
所需条件是 ,等价于 ,也等价于 。最后一个推论可由 以及 得出 。反过来,若 是四的倍数,则 显然是八的倍数。
当 时,定义域中的偶数类 都映到 ,奇数类 都映到 。因此像有两个元素,每个非空纤维由三个定义域中的类组成。陪域中其余六个类的纤维为空。模六的同一个类,其代表元的奇偶性不变,这也与良定义性的证明一致。
快速检查
(设 、 是 上的等价关系。证明:交关系的等价类恰好是一个 类与一个 类的所有非空交集。说明 为空时的结论。)
先确定一个元素在交关系中的等价类。
解答
令 。它是等价关系,并且对每个 ,
这个交集包含 ,所以非空。反过来,若一个 类 与一个 类 的交非空,取 。由等价类定理, 且 ,所以 。因此这些非空交集恰好给出全部等价类。当 为空时,三个划分都是空族,也不存在非空交集。
联系与边界
划分计数笔记研究这里构造出的块;自动机把未来行为相同的前缀归类;强连通分支把能够互相到达的顶点归类。每项应用都必须证明自己的等价性和相容性条件。这里建立的是共同的集合论基础,不表示已经完整讲授自动机最小化、图算法或代数商结构。