动机
假设程序为每条记录指定一个类别。先筛选记录再收集类别,与先收集类别再筛选标签,并不是同一种操作。多条记录可能属于同一类别,声明过的某些类别也可能从未出现。这两点解释了许多涉及函数的集合公式为什么失效。
本节补充计数与算法规格所需的集合和函数基础。我们把集合恒等式读成成员条件,跟踪映射的定义域、陪域,并区分把条件拉回输入与把集合送往输出。
定义
定义 12.4.1
(集合、子集与集合运算)
表示 是集合 的成员。 表示 的每个成员都属于 ;相等需要两个方向的包含。空集 没有成员,所以它是任何集合的子集。但 表示空集本身是 中的一个对象,不能由子集关系推出。集合 有一个成员,并非空集。
取补集前先固定全集 。对 ,并集表示“至少属于一个”,交集表示“同时属于两个”,差集 表示“属于 而不属于 ”。 的补集是 。幂集 由 的全部子集组成,包括空集和 自身。笛卡尔(Descartes)积 由满足 的有序对 组成;交换坐标通常改变对象。
定义 12.4.2
(函数、定义域与陪域)
函数 为定义域 中的每个输入指定陪域 中恰好一个输出。它的图是 的子集 。漏掉某个输入,或让同一输入对应两个不同输出的关系,都不是以 为定义域的函数图;不同输入则可以共享输出。
定义 12.4.3
(像、原像与纤维)
对 和 ,定义
它们分别是 的像和 的原像。前者是 的子集,后者是 的子集。每个函数都有原像运算,即使没有逆函数。输出 的纤维是 ,可以为空,也可以含多个输入。
定义 12.4.4
(复合、单射与满射)
若 ,复合 定义为 ,即先用右边的映射。恒等映射 把每个元素送到自身。单射要求相等输出只能来自相等输入,满射要求 ,双射同时满足两者。下文构造逆映射时集合均为有限集;集合恒等式本身不依赖有限性。
定理/命题
定理 12.4.5
(原像保持集合运算)
对 和 ,有
此外,,。对 和 ,
定理 12.4.6
(像与往返运算)
对 和 ,有
交集包含式对所有 都成为等式,当且仅当 单射。同样, 对所有 成立,当且仅当 单射。最后一式对所有 都等于 ,当且仅当 满射。
定理 12.4.7
(有限集上的逆映射与空集边界)
设 是有限集之间的函数。左逆是满足 的映射 ;它存在,当且仅当 单射,并且 与 至少一项成立。右逆是满足 的映射 ;它存在,当且仅当 满射。双侧逆存在,当且仅当 双射,此时逆唯一。
证明思路
先翻译成员条件
证明
(借成员条件证明原像公式)
任取 。它属于并集的原像,表示 ,即 或 ,恰好是属于右边并集的条件。把“或”换成“且”即得交集公式。由于 总属于 , 就是在全集 内有 ,得到补集公式。空集与全集的原像也直接由定义得到。复合公式则逐步写成
每步都考察同一个输入,没有使用逆函数。
概念视角算法
原像就是输入筛选
对有限编号集合,用输出下标表保存函数,用成员位数组保存子集。求原像时,遍历输入并读取其输出下标处的成员位。当下标和表项都能放入机器字时,这需要 次字操作。若从输入成员数组构造像,先清空输出数组,再遍历输入并标记被选输入的输出,需要 次操作。重复标记不产生重复集合成员。这说明拉回条件无需搜索逆函数,也说明像为何丢失了共享输出的输入数量。
证明
(像、见证与交集包含式)
对像的并集公式,输出 在 中有原像,恰好表示它至少在 之一中有原像。若原像属于 ,它同时属于两者,得到 。
设 单射,且 。则 ,其中 ;单射给出 ,故 。反过来,若 不单射,取 使 。令 ,则 ,而 ,等式不成立。
证明透视
一个共同见证与两个分别存在的见证
包含方向只需要一个见证,而这个见证本来就同时属于两个集合。反向包含才是证明性质改变之处:属于 只给出两个输入 与 ,它们共享一个输出;属于 却需要一个同时属于两集合的输入。因此关键的一步是由两个见证合成一个见证,单射正好在此处使用,用来确认 。这个假设不能减弱:任何碰撞 ()都会给出不相交的单点集,使等式失效。这段论证没有用到满射;只要找到同时属于两集合的输入,证明就完成。
往返时丢失了什么
证明
(往返运算补入与删去的内容)
若 ,则其输出属于 ,因此 。后者还包含与 中某个输入共享输出的全部输入。单射时没有额外输入;反之,若所有这样的往返都保持 ,取 ,任何满足 的 都只能等于 ,故函数单射。
一个输出属于 ,恰好表示它属于 且确实有输入,所以该集合等于 ,不需要满射。满射时它对所有 都等于 ;反之取 就得到 。若只对某一个 成立,仅说明该集合的所有输出都出现过,不能推出对整个陪域满射。
亲自构造逆映射
证明
(逆映射的存在条件)
若 ,对等式 应用 就得 。此外,非空 到空 的函数不存在。这给出左逆的两个必要条件。反过来,若 单射且 非空,选 ;对 令 为其唯一输入,对其他 令 ,就有 。若 为空,已有函数 的存在迫使 也为空,空映射满足要求。
若 ,每个 都有输入 ,故 满射。反过来,把有限集 的元素逐个列出,为每个元素选一个输入,就构成右逆; 为空时用空映射。双射的每个输出恰有一个输入,因而该构造给出双侧逆,且逆只能把输出送回这个唯一输入,所以唯一。双侧逆也必然使 同时单射和满射。更一般地,若左逆 和右逆 同时存在,则 。
例题详解
例题 12.4.8
(既有碰撞又有未使用输出的分类映射)
设 ,,且 ,。取 ,它们的交集为空,所以 ,而 。对 先取像再取原像,得到 。对 ,先取原像得 ,再取像只剩 :绿色从未出现。这展示了两种不同的信息损失。
例题 12.4.9
(在固定全集内证明集合恒等式)
对 ,证明 。任取 ,属于左边当且仅当既不属于 也不属于 ,恰好是同时属于两个补集。若 ,两边都是 。若中途改在 自身内取 的补集,得到空集,却已经改变了问题。
例题 12.4.10
(沿复合映射拉回筛选条件)
设 ,, 返回输入除以二的余数。映射 为两个余数命名。复合标签为奇数的输入是 。分步拉回时,先得 ,再得 。虽然 不单射,原像公式仍完全成立。
例题 12.4.11
(左右逆承担不同义务)
包含映射 有左逆 ,却没有右逆,因为输出 没有输入。映射 有右逆 ,却没有左逆,因为同一输出无法同时恢复两个不同输入。最后,唯一的映射 单射却没有左逆:左逆应是从 到空集的映射,而这样的映射不存在。
常见错误
常见错误
(把原像与原函数直接约去)
不能把 与 当作形式符号直接约去。像的原像会补进整个纤维,原像的像会删掉从未出现的输出。双射的逆函数作用于元素,原像运算作用于子集;即使两者有联系,也不能忽视对象类型。
反例模式
像不一定保持补集
直观上容易猜测 。在分类映射中取 ,则 ,但 。红色出现在左边,是因为 与 碰撞;绿色出现在右边,是因为没有记录带有这个标签,所以两边的失效方向并不相同。普遍成立的是原像的补集公式 ,输出侧全集为 ,输入侧为 。
常见错误
(把单向包含当作等式)
证明 或 只得到一个界,并没有证明等式。反向包含是另一个命题;如上面的证明所示,它对所有集合成立,恰好需要单射或满射的假设。
常见错误
(把左逆与右逆的作用次序弄反)
复合前先标出每个映射的类型。左逆 在 中作用于 之后,右逆 在 中作用于 之前。空集要用这些类型检验,不能当作记号问题略过:空映射 单射,却没有左逆。
总结
集合恒等式来自等价的成员条件。原像把条件拉回同一个输入,因而保持并、交与补。像需要存在见证,碰撞使两个见证未必相同,缺失输出又限制了往返恢复。单射与满射刻画这些信息能否恢复,有限逆映射的构造则明确了存在性与空集条件。
练习
快速检查
(逐元素证明 。判断 与 是否成立。)
解答 · 答案
属于左边等价于属于 而既不属于 也不属于 ,即同时属于 和 。空集唯一的子集是空集,故 ;成员断言为真,与空集相等的断言为假。
快速检查
(对任意 和 ,证明 。给出严格包含的例子,并证明单射时成为等式。)
解答 · 答案
若 ,选 使 。该 不属于 ,否则 ,所以 。分类映射中取 ,左边为空,右边为 。单射时若 且 ,则 中不可能另有输入得到 ,给出反向包含。
快速检查
(证明对某个固定 , 当且仅当 是若干完整非空纤维的并。包括 的情况。)
解答 · 答案
像的原像补入与 中某个元素共享输出的全部输入。若没有补入新元素,每个这样的完整纤维都已包含在 中,故 是这些纤维的并。反过来,纤维的并已包含所有共享输出的输入,往返便不会扩大它。空集是空族纤维的并,也满足等式。
快速检查
(有限集 大小分别为 。对给定单射 ,若 ,求左逆数量。对给定满射,用纤维大小表示右逆数量。另行解释空双射。)
解答 · 答案
在 的 个输出上,左逆已被迫确定;其余 个输出各有 种取值,故有 个左逆。满射的每个 必须从非空纤维中选取,故右逆数为 。空双射恰有一个逆,即空映射,与空积为一相符。左逆计数限定 ,是为了无需借助 的约定。