动机
商集构造从一个决定开始:把某些不同描述视为同一个对象。这个决定会产生进一步的后果。如果描述 与 被认同,而 又与 被认同,那么 也必须与 被认同。因此,仅仅列出最初想认同的那些有序对,未必已经得到了新对象之间合理的相等关系。
商集存在以后,还要回答另一个问题:用代表元写出的公式,在换用同一类的另一个代表元时,是否给出相同答案?这就是商集上的公式良定义的含义。它是一项需要证明的结论,不能靠约定把本来有歧义的规则变成有效定义。
本篇在 ZF 中说明这两个步骤。我们使用前文对有序对、函数图像、自然数和商集的构造,不假设选择公理。
从有限认同生成关系
固定集合 及关系 。记 表示 。这里不要求 自反、对称或传递;它的有序对只是指定我们最初要施加的认同。
定义 1.4.1
(-路径与生成的关系)
从 到 的一条 -路径是有限序列 ,其中 ,并满足 、,而且对每个 ,
路径的长度是步数 ,所以长度零的路径仍有一个顶点。我们允许沿 中的有序对朝任一方向走,因为两个对象是否被认同,不应取决于最初把哪一个写在前面。定义
在 内使用分离公理,就得到集合关系 。路径本身也有明确的集合界限:每个序列的图像都包含于 ,因而所有候选图像均属于 。再用分离选出定义域为有限非空初始段、并满足边条件的函数即可。这里没有使用所谓“任意定义域上所有函数构成的集合”。
定理 1.4.2
(包含给定关系的最小等价关系)
是 上包含 的等价关系。如果 是 上任意包含 的等价关系,那么 。
证明
(路径给出最小等价关系)
只有顶点 的路径说明 。把一条路径倒过来便证明对称性,因为每一步都允许双向通过。给定从 到 及从 到 的路径,把它们连接起来,共同端点 只写一次,就得到从 到 的路径;其中一条长度为零时也成立。因此 传递。若 ,就有长度一的路径,所以 。
现在设 如命题所述。路径的每一步都是一个 -步骤:如果该步反向经过某个 -有序对,就使用 的对称性。对路径长度归纳,长度零时使用自反性,每增加一步使用传递性,便知两端点 -相关。因此 。
同一个构造也可以写成交集。令
这是非空集合,因为 属于其中;即使 也一样。其成员的交集仍然自反、对称、传递,并包含 :每一项性质都能从所有成员传到交集。于是,由刚证明的最小性,
交集描述的是每一种允许的认同体系都必须包含的关系;有限路径则为属于该关系提供了具体见证。两个构造都没有选择代表元。
证明透视
有限路径为什么恰好完成所需的闭包
证明需要两个方向。先证明路径关系足够大:它包含原有的有序对,而且满足等价关系公理。再证明它没有过大:任取一个包含原关系的等价关系,把所有路径的端点关系都放进其中。第二个方向排除了意外增加不必要认同的可能。
“把缺少的有序对补进去”这一说法会隐藏这两个任务。有限路径使传递性的来源具体可见,而与任意包含关系比较的论证,给出了不依赖逐项搜索所有闭包的最小性证明。
等价关系与分划
定义 1.4.3
(分划与商集)
的一个分划是集合 ,其成员称为块,要求每块非空、各块的并为 ,而不同的块互不相交。空集的分划是 ,不是 ,因为后者含有空块。
对 上的等价关系 ,定义
前文用 作为界限构造了 。商集的成员是 的完整子集,并非某个未指明的“首选元素”的名称。
定理 1.4.4
(分划恰好是等价类的全体)
等价关系 的各等价类构成 的分划,而且
反过来,一个分划 通过“某一块同时包含 ”定义等价关系。这两个构造互为逆构造。
证明
(等价类与块互相决定)
自反性给出 ,所以每个类非空,而所有类覆盖 。若 且 ,由对称性、传递性得到 ;交换角色得到反向包含,因此两个类相等。反过来,若两个类相等,那么 ,所以 。
若 同时属于 和 ,则 、,再次使用对称性和传递性得到 。因此有交点的类必相等,不同类便互不相交。
现在从分划出发。每个点都属于唯一一块:存在性来自并集条件;两块若包含同一点,就因相交而相等。“同属一块”显然自反、对称。若 同属一块,而 同属另一块,这两块因都包含 而相等,所以 同属一块。这证明了传递性。所得关系中 的等价类恰好是包含 的唯一块,因而恢复原分划。若从 出发,命题显示的等价式又从类的分划恢复 。空集情形同样满足所有结论。
投影 定义为 ,它是满射。商集中的点 在 下的纤维,恰好就是原集合的子集 。同一个类在这里有“目标中的点”和“定义域中的一组点”两种角色,分清两个集合便很重要。
函数何时能够经过商集
定义 1.4.5
(核等价关系)
给定函数 ,定义它的核等价关系为
这里的“核”表示输出相等,不要求存在群或向量空间结构。由相等关系的自反、对称、传递性,立即知道 是等价关系。
定理 1.4.6
(经过等价类的分解)
设 是 上的等价关系。存在唯一函数 满足 ,当且仅当 。条件成立时, 是满射当且仅当 是满射; 是单射当且仅当 。
证明
(用唯一输出经过商集分解)
若已有这样的分解,且 ,则 ,所以 。这证明必要的包含关系。
反过来,设 。在 内定义图像
每个类至少有一个这样的输出。若 都代表 ,则它们 -相关,所以 ,输出唯一。分离公理因而给出函数图像 ,定义所需的 。任何其他分解都必须把 送到 ,而每个类都有这种形式,所以分解唯一。
与 的值域完全相同,故有关于满射的结论。若 是单射,且 ,两个输入类就必须相等,因而 。于是 ,结合已知包含关系得到相等。反过来,若 ,且 ,则 ,故 ,两个类相等。这证明单射性。
特别地,我们得到一个典范双射
因此,任意集合函数都能分成三个步骤:满射投影、到像集的双射、以及像集到原定陪域的包含映射。这是 ZF 中关于任意集合的定理。
概念视角结构
唯一输出取代了代表元选择
写下 ,不是要求从每一个类选一个 。图像证明考察所有可能代表元,并证明它们给出同一个输出。唯一性使我们无需选择规则便得到函数。
若不同代表元给出不同答案,加入额外数据后选择首选代表元,也许能定义另一个函数。但这并不能证明原规则与代表元无关。当我们由不同描述的等价类构造数系或模型时,这一区分尤其有用。
对于由生成元指定的关系,检验还可以简化: 能经过 分解,当且仅当 总蕴含 。必要性来自 。充分性来自输出相等能沿每条路径传递,因此 。也可以说, 是包含 的等价关系,直接应用最小性即可。
比较与合并等价关系
固定集合 上的等价关系都是 的子集,所以它们构成一个集合,并按包含关系形成偏序。较小的关系认同较少的有序对,对应的分划也较细。于是有两个问题:两个可比较的关系给出的商集之间有什么联系?能认同两个关系中任何一个所认同之物的最小关系又是什么?
定理 1.4.7
(较细与较粗关系的商集)
设 是 上的等价关系,投影分别为 与 。存在唯一函数 满足 ,即 ,而且它是满射。在 上由
给出的关系 是良定义的等价关系。它等于核关系 ,而 诱导出双射 。
证明
(两次应用分解定理)
分划一节证明的类等式说明 当且仅当 ,所以 。因此假设 正是分解定理所需的条件 ,由此得到唯一的 。由于 是满射, 也是满射。
其次, 的意思是 ,即 。所以上式描述的正是核关系 ,它是 上的等价关系。 只由类本身定义,因此这个条件不可能依赖所取的代表元 。最后,对 及 应用分解定理,得到诱导映射 :它是满射,因为 是满射;它是单射,因为 就是整个核。
定义 1.4.8
(两个关系的复合)
对关系 ,定义
与函数一样,先作用的是 。关系的复合满足结合律: 与 都恰好在存在 使 、、 时包含 。此外 。
定理 1.4.9
(两个等价关系的交与合)
设 与 是 上的等价关系。
- 是等价关系,并且是同时包含于 与 的最大等价关系。
- 包含 的最小等价关系是 ,称为 与 的合。 成立,当且仅当对某个 ,存在 中的 ,使每个 都满足 及 。
- 是等价关系,当且仅当 。此时 。
证明
(交替链与可交换的复合)
第 1 部分。 自反、对称、传递三条性质,各自都是说:只要某些有序对属于关系,另一些有序对也属于它。若这些性质对 与 都成立,则对 也成立。任何同时包含于 与 的等价关系都包含于 。
第 2 部分。 由本篇第一条定理, 是包含 的最小等价关系。交替链是一条 -路径,由此得到一个方向的包含。反过来,取一条从 到 的 -路径。由于 与 都对称,每一步不论沿哪个方向走,都可看作向前的 -步或向前的 -步。若相邻两步类型相同,就在它们之间重复中间的顶点,并利用另一个关系的自反性,用该关系标记这个平凡的新步。若路径以 -步开始,就在前面重复第一个顶点并标记为 ;若以 -步结束,就在末端重复最后一个顶点并标记为 。新路径端点不变,并按 交替,所以长度是偶数。长度为零的路径就是 的情形。
第 3 部分。 在定义中取 或 ,由 与 的自反性得 ;特别地, 是自反的。由于 与 都等于自身的逆,。若 是等价关系,它便是对称的,所以 。
反过来,设 。此时 等于自身的逆,所以是对称的。 的自反性与传递性给出 ,同理 。由结合律,
这特别给出传递性。所以 是包含 的等价关系,因而包含 。 中每个有序对都由一条两步的 -路径连接,所以 。
例题 1.4.10
(同余关系总是可交换)
对正整数 ,用 表示 上的模 同余。设 为正整数。若 且 ,则 。反过来,若 ,令 ,则 且 。因此
这个描述关于 与 对称,所以两个关系可交换。由 Bézout 恒等式(裴蜀定理),,其中 是最大公因数,所以两者的合是 。由于 ,其中 是最小公倍数,两者的交是 。
取 、,合就是奇偶性,交就是模 同余。由于 ,比较定理给出从模 的四个类到两个奇偶类的满射。关系 有两块 与 ,正好对应 。
例题详解
有序对列表会迫使更大的类出现
例题 1.4.11
(三个描述成为一个等价类)
令 ,四个标签互不相同,且 。 内任意两点之间都有路径;但没有路径能把 连接到其他顶点,因为没有允许的边接触 。所以 的块是 和 。关系包含第一块内全部九个有序对,以及 这一个有序对。
上的函数能下降到这个商集,当且仅当 ;在 处的值没有限制。只检查 会漏掉另一个指定认同;允许 则违反传递性迫使成立的认同。
两个等价关系的并未必是等价关系
反例模式
两个等价关系的并
断言:集合上两个等价关系的并仍是等价关系。在 上,令 的块为 , 的块为 。它们的并使 与 相关、 与 相关,却没有使 与 相关,因此不传递。包含二者的最小等价关系是 ;本例中它只有一块,即整个集合。
相比之下, 就是这个集合上的相等关系。交集保留等价关系公理,并集一般需要再取有限路径闭包。
忘掉正负号后,像集仍须准确描述
例题 1.4.12
(按平方相等对整数取商)
定义 为 。由 得到 ,所以 或 。核的类是 ,以及每个正整数 对应的 。诱导映射把每个类送到其共同的平方。
它是到 的双射,却不是到整个 的满射;例如 不是平方数。按输出相等取商,恰好消除了不单射的问题,却不会扩大值域。如果改为按奇偶性认同整数,则平方规则不能下降为取值在整数中的函数,因为 与 同奇偶,但平方不同。
运算也有相容性条件
例题 1.4.13
(类之间的变换不必保持代表元相等)
令 是 上“奇偶性相同”的关系。映射 能诱导 ,当且仅当 蕴含 。这里不要求同一类上的输出逐字相等,只要求它们仍属于同一个目标类。
若 ,偶数差 在应用 后仍为偶数,所以诱导映射交换两个类。相反, 不满足条件:,但 与 奇偶性不同。即使商集只有两个点,一个看起来合理的代表元公式也可能无效。
常见错误
常见错误
(等价类既不是 的元素,也不是它的代表元)
等价类是 的子集,也是 的元素;它通常不是 的元素。类也不等于它的某个代表元:不同代表元可以给出完全相同的类。
常见错误
(最小不是最大)
最小性与最大性的包含方向不同。 包含所要求的有序对,却包含于每一个含有这些有序对的等价关系。它不是最大的这种关系;最大的关系是 。
常见错误
(输出相等与输出类相等)
取值在 中的函数要下降到以 为目标的函数,就必须在每个类上有相等的输出。取值在另一个商集中的函数,则需要输出的类相等。最后的例题说明这两个条件不能互换。
快速检查
快速检查
(当 及 时, 与 分别是什么?)
分开处理 非空与 的情形。
解答 · 答案
若 ,则只能有长度零的路径,所以 是相等关系,没有不同点被认同。若 且 非空,任意两点都可一步相连,商集只有一个点。若 ,商集则为空。这些边界情形同时检验了路径长度约定与分划中块非空的约定。
练习
快速检查
(生成的块)
令 ,。求 ,并证明不会被迫产生其他认同。
解答 · 答案
所求块为 与 。在 内,路径 反向经过第二个指定有序对,因此任意两点连通; 中两点直接连通。“属于 中同一块”是包含 的等价关系,故由最小性,不会产生跨越两块的路径认同。因此 。
快速检查
(对序关系取闭包)
在 上令 为通常的 关系。求 ,并解释为什么这个构造没有保留原有序信息。
解答 · 答案
对任意 ,总有 或 ,所以两点有长度一的路径。于是 ,商集为 。取等价闭包时,每个生成关系都被允许反向使用。它记录认同所迫使的相等关系,因此不可能保留真正的序关系中的方向与区别。
快速检查
(商集的子集)
设 是 上的等价关系。证明 的子集与那些由 -类的并构成的子集 一一对应,并用特征函数 解释这一对应。
解答 · 答案
把 送到 ,所得显然是类的并。反过来,对类的并 ,取 。每个类非空,而不同类不交,所以一个包含于 的类必属于 。两个构造因而互为逆,包括空集情形。特征函数 在每个类上为常数,当且仅当是否属于 在每个类上保持不变,也就是 为类的并。分解定理把它与 中对应子集的特征函数联系起来。
快速检查
(限制到子集)
设 , 是 上的等价关系。把 限制到 ,证明 定义单射 。它何时是满射?
解答 · 答案
这里 ,且 。若两个代表元给出相同的限制类,它们就 -相关,因而给出相同的完整类,证明映射良定义。若完整类相同,这两个属于 的点便在限制关系下相关,所以限制类相同,证明单射。其像恰好是与 相交的完整类,因此满射的充要条件是 与每个 -类相交。构造此映射无需同时选取代表元。
快速检查
(投影的右逆)
证明投影 有右逆,当且仅当存在 的子集,恰好与每个 -类相交于一个点。说明商集分解定理的哪一步避免了这一额外要求。
解答 · 答案
若 满足 ,则 。其值域与每个类相交,而为不同类选出的值不可能落入 ,所以交点唯一。反过来,若 与每个类恰交于一点,则“ 当且仅当 ”由唯一存在定义函数,并满足 。 为空时, 都取空集,结论也成立。分解证明使用的是:所有代表元在 中本来已有同一个输出,因此每个类有唯一输出;它并不需要从类本身选出一个点。这个关于给定商集的等价命题,没有断言 ZF 中每个商映射都有右逆。
快速检查
(诱导运算)
对二元运算 ,证明公式 良定义,当且仅当 与 蕴含 。若 满足结合律,证明诱导运算也满足结合律。
解答 · 答案
必要性来自 、:良定义的运算必须给出相同的结果类。充分性来自所给蕴含保证输出类与两个代表元都无关。每对类有唯一输出类,用分离便能定义图像,无需同时选择代表元。若 结合,则对任意代表元 ,两种加括号方式分别由 与 代表,而这两者在 中相等,所以其类相等。每三个类可由商集定义局部取得代表元;这个证明只用了有限次存在见证。
快速检查
(不可交换的复合)
在 (三个标记互不相同)上,如前述关于并的反例,令 的块为 , 的块为 。计算 与 ,证明两者都不是等价关系,并求 。
解答 · 答案
有序对 属于 ,当且仅当有某个 使 且 。从 出发,唯一的 是 ,所以 。从 或 出发,可取 ,所以 可以是 中任何一个。因此 由除 以外的全部九个有序对组成;它的逆 由除 以外的全部有序对组成。两者都不对称,这正是定理第 3 部分对不可交换关系的预测。交替链 连接 与 ,所以 ,只有一块。
快速检查
(加细的三种说法)
设 与 是 上的等价关系。证明以下三者等价:(i) ;(ii) 每个 -类都包含于某个 -类;(iii) 每个 -类都是若干 -类的并集。
解答 · 答案
(i)⇒(ii):若 ,则 ,所以 。(ii)⇒(i):若 ,设 是包含 的 -类。则 ,又因各类分划 ,,所以 。(ii)⇒(iii):对 -类 及 , 的 -类包含于唯一含 的 -类,即 。所以 。(iii)⇒(ii): 的 -类是若干 -类的并集,其中一个含 ;同样因为各类分划 ,这个类必定是 。因此 。
总结
有限的可逆路径恰好构造出由指定认同所迫使的等价关系,其等价类分划了原集合。函数能经过商集分解,恰好要求它在各类上的输出为常数;按函数的整个核取商,便得到到像集的双射。证明始终使用集合界限和唯一输出,而从每个类选取一个代表元是另一项问题。