动机
在计算中,相等往往过于严格:两个整数可以因为余数相同而被视为同一种情况,两个任务之间也可能只有先后约束。这两种情况都可以用一条规则描述:指明哪些有序对的元素算作相关。
定义
定义 12.5.1
(二元关系与关系图)
集合 上的二元关系 是 的一个子集; 时记为 。有序对的次序不能随意交换。关系图以箭头表示相关的有序对, 则画成环。
定义 12.5.2
(自反、对称、传递与反对称)
若每个 都满足 ,称关系自反;若 必然推出 ,称为对称;若 与 必然推出 ,称为传递。若 与 同时成立必然推出 ,称为反对称。反对称并不要求任意两个元素一定有一个方向的箭头:它们可以不可比较。这些条件都是全称命题,一个反例即可推翻;在空集上四者都因没有反例而成立。
常见错误
(反对称不等于不对称)
反对称只限制两个不同元素:它们不可在两个方向上都相关,并没有禁止对称。任何集合上的相等关系既对称又反对称, 上的关系 也是如此。若有 与 ,这一对符合对称,却违反反对称,因为 。
等价关系与划分
定义 12.5.3
(等价关系、等价类与划分)
自反、对称且传递的关系称为等价关系。 的等价类定义为 。 的一个划分是若干非空、两两不交的子集,其并集为 ;空族是空集的划分。
定理 12.5.4
(等价类恰好构成划分)
等价关系的不同等价类构成 的划分。反过来,规定两个元素当且仅当属于同一个划分块时相关,得到一个等价关系。
证明
(等价类覆盖 ,且相交的类相同)
由自反性,,因此等价类非空且覆盖 。若 ,则 且 。对称性给出 ,再由传递性得 。对任意 ,由 和 得 ;交换 的角色便得两个类相等。所以相交的类必定相同。反过来,同属一个块显然自反、对称;若 同属一个块而 同属另一个块,由块两两不交可知这两个块相同,传递性随之成立。
证明透视
一个公共元素为何足够?
不显眼的一步,是把公共元素 当作连接 与 的桥。对称性把 变成 ,传递性把 与 合成 ;同一模式说明每个类都含于另一个类,所以论证以相等作结。自反性只在开头使用,用来保证类非空并覆盖 。对称性不能省略:在 上,关系 自反且传递,而 、,这两个类相交却不相等。
定义 12.5.5
(商集与代表元)
所有不同等价类组成商集 。代表元只是类的一个名称,并非唯一选择。若想通过选代表元定义类上的运算,必须证明更换代表元不会改变所得的类。
例题 12.5.6
(余数及良定义运算)
给定整数 ,令 表示 整除 。 整除零,且整除性对取负和加法封闭,所以这是等价关系。共有 个类,可用 代表。定义 。若 且 ,则 整除 ,故 ;结果与代表元的选择无关。
反例模式
依赖代表元的规则
在模 的整数类上,试图定义整数值函数 并不良定义:,但规则分别给出 和 。使用代表元写出的公式不一定定义了商集上的函数。
偏序与依赖关系
定义 12.5.7
(偏序、最小元素与极小元素)
偏序 是自反、反对称且传递的关系; 称为偏序集。例如,包含关系给固定集合的子集定义偏序,整除关系给正整数定义偏序。最小元素位于每个元素之下;极小元素下方没有不同于它的元素。最小元素若存在则唯一且极小,但可以存在多个极小元素而没有最小元素。
定义 12.5.8
(严格序、覆盖关系与 Hasse 图)
当 且 时记为 。对于有限偏序集,画 Hasse 图时省略自环及由传递性得到的边:当 且不存在 的 时,在 和 之间画向上的边。每个严格比较都可由向上走边恢复:若不是覆盖关系,就插入中间元素并重复;有限性保证过程终止。因此图是关系的紧凑表示,并非所有相关对的完整列表。
常见错误
(把 Hasse 图当作整个关系)
图中省略自环,也省略所有由传递性得到的相关对。在 的整除关系中, 成立,但 与 之间没有边;要恢复这个比较,须沿向上的边经过中间元素。反过来,图中的边只记录覆盖关系,所以没有直接的边,并不表示两个元素不可比较。
定理 12.5.9
(有限偏序都有线性扩张)
每个有限偏序集都有一个排列 ,使得 蕴含 。 时空排列满足要求。
证明
(逐次删去极小元素)
若非空有限偏序集没有极小元素,不断选择严格更小的元素,最终必会重复。由传递性得到严格环,与反对称性矛盾。选一个极小元素放在首位,删去它,再对剩余元素诱导的偏序重复此过程。被删元素不可能有尚未列出的严格前驱,因此最终排列尊重所有严格比较。这就是安排有先后约束任务的原理。有限有向无环图可反复删除入度为零的顶点来排序;可达关系(包括长度为零的路径)是偏序。用邻接表和维护的入度,每个顶点和边只处理常数次,时间为 。
证明透视
有限性与反对称用在哪里
每个阶段都需要一个极小元素,假设就在这里被使用。在有限偏序集中,不断选取严格更小的元素,必定会重复出现某个元素;传递性把重复变成 ,而反对称性禁止这种情况。有限性不能去掉: 配上通常的顺序就没有极小元素。列表之所以正确,是因为每个被列出的元素在当时剩下的元素中都是极小的,所以它的每个严格前驱都已较早列出。对元素个数作归纳便完成论证。
例题 12.5.10
(极小不等于最小)
在 上按整除关系排序。 和 都是极小元素;二者不可比较,因此没有最小元素。覆盖关系为 、 和 。 与 都是线性扩张。虽然 Hasse 图不画 到 的边, 仍属于该关系。
尊重划分的函数
商集适用于某个问题不关心同一类内部区别的情况。令 把 送到 ,又设 。我们希望通过 在类上计算 。这要求 在每个类上为常数:只要 ,就有 。不同类的输出可以相同;条件并不要求它们不同。
定理 12.5.11
(因子分解的判据)
存在函数 使 ,当且仅当 蕴含 。存在时, 唯一。
证明
(在类上为常数,是必要且充分的)
若分解存在,相关元素属于同一类,故 。反过来,若 在类上为常数,对每个类 选 并令 。类非空,而假设保证这个值与选择无关。于是 。由于商集的每个元素都形如 ,等式决定了 的每个值,故其唯一。 时,商集为空,空定义域上的函数同样满足结论。
常见错误
(把因子分解判据读反)
判据要求相关的输入有相同的输出,并不要求不相关的输入有不同的输出:常数函数在每个类上都是常数,所以对任何商集都可分解。通过 分解也不表示 决定了等价类;只有在类上的诱导映射为单射时才是这样。
例题 12.5.12
(按长度归类字符串)
令 为所有有限二进制字符串,包括空串 ;令 表示 。长度相等构成等价关系,每个类含一种长度的全部字符串,长度零的类为 。函数 在每类上为常数,因而可写成 。但 若表示其中 的个数,就不能通过这个商集分解:,但 而 。商集丢掉的信息可能恰好是另一个任务所需的。
定义 12.5.13
(核关系)
任何函数 自身也定义一个关系,称为核关系 : 当且仅当 。
定理 12.5.14
(函数经由核关系双射分解)
核关系是 上的等价关系,其类是所有非空纤维 。诱导映射 ,,是双射。反过来, 上每个等价关系 都是商映射 的核关系。
证明
(纤维即等价类,每个关系都是核关系)
输出相等具有自反、对称和传递性, 的类就是纤维 。由因子分解判据,映射 是良定义的,因为相关的输入有相同的输出。按像的定义它是到 的满射;又因为 恰好表示 ,即 ,所以它是单射。 未取到的陪域元素不会产生空类;定义域为空时,像和商集都为空,双射仍然成立。反过来, 表示 ,由划分定理,这恰好等价于 。
概念视角结构
把等价关系看作标签
核关系的结论给出同一个对象的第二种描述。关系 是关于有序对的规则;商映射 则给每个元素贴上所属类的标签,而 恰是“标签相同”这个关系。用这种语言,“ 尊重 ”就是 只通过标签 依赖 ,这正是因子分解判据的直接读法。
这也说明类上的运算为什么需要相容性证明。若 是 上的二元运算,要定义 ,恰需对于所有代表元选择, 且 蕴含 。只检查几个方便的代表元不够。上面的模加法证明验证了该条件,下面关于余数类乘积的练习对乘法也作了验证。
构造和读取依赖偏序
以箭头列表给出的关系,可能没有列出偏序传递性要求的全部后果。对有限有向无环图,定义 表示存在从 到 的有向路径,允许长度为零。零长路径保证自反,连接两条路径保证传递;若不同的 互相可达,两条路径会包含有向环,与无环性矛盾,故也反对称。原始边不必列出该偏序的所有相关对,但每条原始边在每个线性扩张中都必须向前。
定理 12.5.15
(拓扑序恰对无环图存在)
设 是有限有向图。若 没有有向环,则可达关系是偏序,其线性扩张恰是使每条边都向前的排列。若 有有向环,则不存在这样的排列。反复删除入度为零的顶点,要么列出全部顶点,要么停在含有有向环的剩余顶点上。
证明
(边向前、有环不可能、卡住就有环)
可达偏序的每个线性扩张都是图的拓扑序;拓扑序也尊重每条路径,因为路径上的每条边都向前。因此两种说法得到完全相同的排列。若图有有向环,沿环会迫使起点严格排在自己之前,拓扑序不可能存在。对有限图反复删除入度为零的顶点:若未删完就停下,每个剩余顶点都有来自剩余顶点的入边。沿入边反向追踪必然重复顶点,于是得到有向环。这不只是算法找不到答案,还给出了失败的证据。
例题 12.5.16
(数出合法日程)
设任务 的直接约束只有 在 前、 在 前及 在 前。起初可选 。若先选 ,第二步必须选 ,随后 任意排序,得到 。若先选 ,接下来可选 :先选 得 ;先选 则余下次序被迫为 ,得 。因此恰有五个线性扩张。按下一个可选任务分支既不遗漏合法日程,也不会重复计数。孤立任务也是可选项,不是无法完成的任务。
一个线性扩张是与偏序相容的一个全序,并不表示不可比较的任务本来就有固有次序。上例中 的两种次序都出现; 在每个扩张中都早于 ,因为这是原约束。依赖图可能有大量合法日程:找一个可用线性时间,但列出所有结果本身可能需要指数大小的输出。
反例模式
有向环与无向环不同
边 、、 构成有向无环图,尽管忽略方向后它是三角形。其唯一线性扩张是 。有向环要求沿箭头方向走回起点;单有无向环并不表示依赖约束矛盾。
练习
快速检查
(在整数上令 表示 是偶数。求等价类,并说明 是等价关系。)
解答 · 答案
自反性成立,因为 是偶数。对称性成立,因为 为偶数时 也是偶数。传递性成立,因为 是两个偶数之和。等价类是偶整数集和奇整数集。
快速检查
(在 上令 表示 。自反、对称、传递性哪些成立?)
解答 · 答案
对称性成立。每个元素都违反自反性。传递性不成立,因为 和 成立而 不成立。
快速检查
(在 上按包含关系排序,求极小元素、最小元素及所有线性扩张。)
解答 · 答案
两个单元素集合都是极小元素,但没有最小元素。线性扩张恰有两个:先以任意次序列出两个单元素集合,最后列 。
快速检查
(若 且 (模 ),证明 。)
解答 · 答案
利用 ,右边两项都被 整除,所以 。因此乘法在余数类上也良定义。
快速检查
(设 ,,且 、。求核类和像。由商集到整个陪域的诱导映射是满射吗?)
解答 · 答案
核类是 和 ,像是 。诱导映射到 时漏掉 ,因而不满射;但它到像的映射是双射。
快速检查
(有向图的边为 、 和 。求全部拓扑序;若添加边 会怎样?)
解答 · 答案
都必须早于 , 必须晚于 ,故拓扑序为 。添加 后产生有向环 ,不存在拓扑序。
快速检查
(在模 的整数类上, 是否定义了类到类的函数?解释为何更换代表元不改变结果。)
解答 · 答案
是。若 整除 ,则也整除 。等价输入得到等价输出,由因子分解判据得到商集上的唯一函数。