动机
假设某个输入集合中的每个对象,都有一个满足指定条件的输出。每个输入可能对应很多合适的输出。我们能否找到一个集合,其中包含足以照顾所有输入的见证?能否为每个输入选定恰好一个输出?能否把所有可能的输出都收集起来?这其实是三个不同的问题。
替换公理模式立即处理其中一个特殊情况:每个输入的输出唯一时,所有输出组成一个集合。但不能直接删去替换中的唯一性条件。尽管如此,ZF 仍然能够证明:只要输入构成集合,就存在一个集合,为每个输入提供至少一个合适的输出。这就是收集公理模式。证明的关键,是限制合适输出的秩,而不是先替每个输入选择一个输出。
我们在 ZF 中工作,并使用前文已经建立的序数秩与累积层级。特别地,
除非明确说明,否则不假设任何形式的选择公理。
收集究竟断言什么
定义 1.3.1
(收集公理模式)
固定一个带有集合参数 的一阶公式 。它不必为每个 确定唯一的 ,其中的量词也不必有界。对于集合 ,相应的收集实例是
这里的 是一个见证的范围界:每个输入都能在其中找到至少一个合适的输出。 可以包含毫不相关的对象,也不必包含全部合适的输出。它甚至不必指定哪个输出应当分配给哪个输入。
定义 1.3.2
(强收集)
强收集还要求 的每个成员确实能为某个输入作见证:
这里的“强”指的是排除无用成员的附加条件,并不表示已经得到一个选择函数。同一个输出可以适合多个输入;同一个输入也可能在 中仍有多个合适输出。
收集与分离、替换一样,是一个公理模式:每个公式对应一个实例。我们没有在 ZF 中引入遍历全部公式的变量,也没有引入整个集合宇宙的真谓词。以下每次论证中的 都是一个固定公式。
不选择见证,先限制秩
定理 1.3.3
(ZF 中的收集与强收集)
对于每个固定公式 ,ZF 都能证明上述收集实例和强收集实例。证明不需要选择公理。
证明
(最小见证秩为输出定界)
假设 。对于每个 ,考虑所有合适输出可能具有的序数秩。这个由公式描述的非空序数类有最小成员,记为 。准确地说,它满足
我们还没有构造全部见证的秩所组成的集合,为什么仍能取最小秩?在固定一个 的论证中,先取一个已经存在的见证 。在序数 中使用分离,得到不超过 的所有可达秩。这个集合非空,因此有最小序数。任何更大的可达秩都不可能比这个最小序数更小,所以所得最小秩与 的选择无关。这证明了 的存在与唯一,而没有同时为全部 选择见证。
现在规则 是可定义的单值规则。替换因此给出集合
每个 至少有一个合适输出的秩恰好为 。由于 ,这些最小秩输出全部属于 。因此 满足收集。我们收集的是唯一确定的序数界,而不是一族选定的见证。
要得到强收集,再使用一次分离:
所有最小秩见证仍然保留在 中,所以每个输入仍然有见证。定义条件又保证 中每个成员都对某个输入有用。若 ,则 、,而 ,两个结论仍成立。
证明透视
唯一确定的辅助对象是秩,不是见证
前提保证每个输入有见证,却一般不保证见证唯一。不过,见证所能具有的最小序数秩是唯一的。替换应用于这个新的单值规则。幂集与超限递归提供相应的层级阶段,容纳这些最小秩的全部输出;需要时再用分离去掉无关成员。
证明没有从“每个纤维非空”直接跳到“在每个纤维中选一个成员”。即使最小秩论证中临时使用了一个见证 ,那也只是针对一个固定输入的局部论证;最终定义 时,不依赖一整族这样的选择。
这个构造也说明“界”的含义。它证明一个足够高的层级阶段存在,并没有给出由公式计算该阶段的有效算法。判断一个给定秩上是否存在见证,可能涉及任意无界的集合论量化。
如何恢复单值替换
定理 1.3.4
(收集加分离推出替换)
在通常的其余 ZF 公理之上,并保留分离时,收集与替换是等价的公理模式。刚才由替换推出收集的方向使用了 ZF 的秩定理;由收集推出替换的方向只需先收集,再分离。
证明
(由收集推出替换)
假设公式 对每个 都恰有一个输出。收集给出集合 ,其中为每个输入保留至少一个合适输出。分离得到
若某个 是输入 的输出,收集又保证同一个输入有一个输出 。由唯一性,,所以 。反过来,每个 按定义都是某个输入的输出。因此
这正是替换所要求的像集。
这里的唯一性是关键;下面的失败例子说明它不能省去。
反例模式
没有唯一性时从见证界分离
断言:若每个 至少有一个输出,则从收集界 中分离出输出,就得到全部输出组成的集合。取 ,令 表示 是序数。集合 是收集界,分离得到 。但 也是合适输出,而 。更进一步,这里没有任何集合能包含全部输出,因为序数构成真类。修正后的陈述要求每个输入恰有一个输出;这时上面的论证表明 就是完整的像集。
本定理并未断言在任意很弱的集合论片段中也有这种等价:从替换到收集的证明使用了秩、层级阶段及其余已经说明的 ZF 资源。
关系还不是选择函数
一旦收集给出 ,便可在 中分离出集合关系
定义 1.3.5
(处处有定义的关系与选择函数)
每个输入都有一个 -后继。这里称 在 上处处有定义,意思是每个输入至少有一个对应输出;这与全序关系没有关系。它未必是函数,因为纤维
可以有多个成员。原条件的一个选择函数,是定义域为 的集合函数 ,满足对每个 都有 。
定理 1.3.6
(任意集合指标的见证选择就是选择公理)
在 ZF 之上,“每个条件 都有选择函数”这一模式等价于选择公理。每个实例的定义域 都是集合;它不要求有一个在整个宇宙上选择的类函数。
证明
(在纤维中选择,并反推选择公理)
先假设 AC。使用收集,并构造上述非空纤维 。每个纤维由 唯一确定,所以替换给出集合 。AC 给出定义在 上的函数 ,使每个 都满足 。定义 。替换构造出其图,而 正好保证所需条件。不同输入的纤维即使相同也没有问题:相同纤维可以重复使用同一个被选元素。若 为空,取空函数即可。
反过来,设 是任意以集合为指标的非空集合族。把给定集合族作为参数,令 表示 。选择函数模式给出每个 都满足 的函数,这就是 AC。
这个等价定理辨认出了附加原则,但并不是在这里证明 AC 独立于 ZF。个别选择函数完全可能不需要 AC 就能定义。若所有合适输出都是序数,可以取最小的合适序数;若每个纤维都是 的非空子集,可以取其最小成员。真正要检查的是:当前的具体规则是否已经唯一确定输出。
例题
例题 1.3.7
(有限例子中的秩界计算)
取 ,令 表示 是满足 的序数。最小可能见证是 ,其秩也是 。因此一般构造给出 、、,以及 。
集合 为每个输入提供一个合适见证,但也包含许多无关对象。强收集删去无关成员后得到 。它仍不是选择函数:对于输入 ,其中的 、、 全部合适。另行定义的规则 才选定了一个见证;这里能这样做,是因为序数顺序给出了规范的最小选择。
例题 1.3.8
(已经给定的集合族可以直接取并集作界)
设 是定义在 上的集合函数,且每个 非空。它的值域是集合,所以 也是集合。每个 都包含在 中,因此对于条件 , 已经是见证界。这个特例不必调用一般收集定理。
例如,取 ,。最小秩依次是 ,因此秩构造用 就足够,其中有用的见证是 。直接的并集界还包含较大的见证 、、。不同的见证界可以保留不同数量的备选输出。但无论取并集,还是按秩筛选,都还不是为任意非空集合族逐一选择成员的一般任务。
例题 1.3.9
(秩界可能必须经过极限阶段)
对于 ,要求 。这些输出唯一,所以替换本来就能直接构造值域。为了与一般证明比较,回顾 : 的成员所具有的秩恰好是小于 的全部序数,代入秩定义中的上确界便得到 。
因此最小见证秩是 ,并且
每个指定的 都是 的成员。但有限 对应的阶段 不可能包含所有这些见证:它已经漏掉所要求的对象 自身,因为其秩等于该阶段的指标。输入虽然只有可数多个,成员关系深度的界却是一个极限序数,并非有限阶段,也不能用输入个数来理解。
例题 1.3.10
(收集并不收集全部可能输出)
取 ,令 表示“ 是序数”。 是一个有效界, 也是。但全部合适输出不可能构成集合,因为序数形成真类。事实上,如果集合 恰好包含全部序数,那么 是序数,其后继也属于 。于是 推出 ,与序数的性质矛盾。
所以,“有一个集合提供足够多见证”完全可以与“没有一个集合包含全部见证”同时成立。这里秩构造使用最小见证秩零,给出 。
常见误解与小结
常见错误
(把替换用于多值公式)
不要直接对多值公式使用替换。应当找出真正唯一的辅助对象,就像这里的最小见证秩;或者先给出一个已有集合,使分离能够在其中操作。
常见错误
(用每个输入各取一个见证来证明收集)
“为每个输入取一个见证”不是 ZF 中收集定理的证明,因为这恰恰引入了秩证明所避免的选择问题。
见证界不是函数,不是精确像集,不是可计算的搜索界,也不是全部可能性的集合。收集提供范围受限而又足够多的备选输出。输出唯一时,这些备选已经足以恢复替换中的精确像集。对每个任意的集合指标问题同时选定一个备选,则是等价于 AC 的附加选择函数原则。本节不据此声称独立性结果,也不声称已经覆盖整门课程。
练习
快速检查
(检查 时的收集与强收集。哪些集合 能满足强形式?选择函数是什么?)
每个条件都只对 中的输入量化。
解答 · 答案
断言 空真,所以每个集合 都满足普通收集。强收集还要求每个 都有一个来自 的输入,这是不可能的;因此只有 满足强形式。定义域为空的函数只有空图,其选择条件也是空真的。
快速检查
(对 重新计算有限例子,其中 表示 是大于 的序数。列出 ,找出有用见证组成的子集,并解释为什么该子集不是定义在 上的函数。)
先算出每个输入的最小见证秩。
解答 · 答案
最小秩是 和 ,所以 。各阶段为 、、、。其中大于至少一个输入的序数成员是 与 ,所以 。这是可能取值组成的集合,并没有指定每个输入的唯一输出;输入 仍有两个合适值。一个真正的选择函数图例如是 。
快速检查
(设 、,令 表示 。明确写出关系 ,证明它在 上处处有定义却不是函数,并给出两个选择函数。)
在 内分离出所需的有序对。
解答 · 答案
分离给出 。输入 有后继,所以 在 上处处有定义。但有限序数 和 不同,因而它有两个不同后继,不满足函数的唯一性条件。图 与 给出两个不同的选择函数,都满足题设条件。
快速检查
(假设 ,而 仅是一个收集界。证明精确像集包含在 中,并解释去掉唯一性后为什么该论证失效。)
把任意一个输出与 为同一输入提供的输出比较。
解答 · 答案
若 是某个输出,取满足 的输入 。收集给出 ,满足 。同一输入的输出唯一,所以 。没有唯一性时, 和 可能不同。例如只有一个输入、所有序数都合适时, 是收集界,却漏掉合适输出 。
快速检查
(设 是一个由序数组成的集合。对每个 ,要求一个序数 。在 ZF 中构造选择函数,并给出一个能同时为所有输入作见证的序数。包括空 的情形,并解释为什么两种构造都不需要 AC。)
后继与并集都是对序数唯一指定的运算。
解答 · 答案
定义 。后继唯一确定,所以替换能构造该函数的图,而且 。再令 、。序数的并集仍为序数,且每个 都满足 。因此 只用一个共同取值就构成见证界。若 , 为空、,共同取值的要求空真。后继与并集都是明确指定的构造,没有任意的同时选择。
快速检查
(假设 AC。当每个输入的合适见证具有无界多种秩时,应用选择函数定理。解释证明为什么仍然有效,以及它为什么没有先构造全部见证的集合。)
按照证明的次序:先收集,后选择。
解答 · 答案
收集先提供一个阶段 ,其中每个输入都有合适输出。分离出非空的有界纤维 ,然后按照定理,对这些纤维构成的集合指标族应用 AC。AC 只用于在已经存在的非空集合中选择。更高秩的见证可以忽略,因为目标是一个合适输出,而不是全部输出。全部见证构成的类未必是集合,也从未成为替换或 AC 的输入。