除明确指出额外选择原则外,均在 ZF 中工作。使用完备度量空间的基本分析知识,不预设选择原则的等价性或独立性定理。
动机
有限次存在性选择可以用归纳证明。但无限次连续选择需要更谨慎:若下一次决定依赖之前的决定,知道每个有限阶段都可延伸,还没有直接给出一个无限序列。递归定理根据已经指定的规则构造数值,并不会把一个未指定选法的非空后继集合自动变成规则。
可数选择从一个固定集合序列的每个成员取一个元素;依赖选择则容许每次新选择依赖前一个状态。树使区别清楚:节点记录已经完成的有限决定,无限分支给出相容的全部完成。Baire 定理的嵌套球证明是有用的分析例子,因为下一球必须装入刚选好的球。
定义
定义 4.2.1
(可数选择与依赖选择)
可数选择 指:对每个由非空集合组成的序列 ,存在函数 满足每个 都有 。各集合本身不必有限或可数;可数的是指标集。
关系 称为处处有后继,若每个 都有 满足 。本文使用带指定起点的依赖选择 DC:对非空 、处处有后继的 及指定 ,存在以 为首项的序列,满足每个 都有 。
定义 4.2.2
(树、无终端树与分支)
集合 上的有限序列树是非空的 ,且对取前缀封闭,根为空序列。若每个节点 都有一步延伸 ,称树无终端节点。分支是函数 ,满足每个 都有 。这些树与函数空间在 ZF 中都是集合,不假设 已经有枚举。
定义 4.2.3
(无处稠密集与 Baire 空间)
度量空间中,一个集合的闭包若内部为空,称该集合无处稠密。每个可数开稠密集交都稠密的空间称为 Baire 空间。完备性指每个 Cauchy 序列都收敛到该空间中的一点。
定理/命题
定理 4.2.4
(这里实际证明的蕴涵)
在 ZF 之上,
可数选择还推出可数个可数集的并仍可数。后者必须选出一整族编码,不能只指出各编码分别存在。
定理 4.2.5
(DC 等价于无终端树分支原则)
在 ZF 之上,DC 等价于任意集合上的每棵无终端有限序列树都有无限分支。对于任意分支数的树,不能把“无终端”直接换成“有任意大有限长度的节点”。
定理 4.2.6
(DC 下的 Baire 定理)
假设 DC,每个完备度量空间都是 Baire 空间。特别地,非空完备度量空间不能是可数个无处稠密集的并。
证明思路
证明
(后继函数、无终端树与部分选择)
在 AC 下,所有后继集合 有选择函数 。现在才用普通的 递归,从指定 定义 。这证明 AC 推出 DC,也说明选择规则来自哪里。
假设 DC,令 无终端。把节点当作状态,以一步延伸为处处有后继的关系,从空节点开始。DC 给出 ,其中 且各步相容。它们的并是定义于 的函数,就是所需分支。反向,给定 上的 及 ,取空序列和所有以 开始的有限 -链构成树。根可延伸为 ,非空节点由后继性质可延伸,故无限分支从 出发且一直沿 ,证明 DC。
要推出 ,取全部有限部分选择构成的树:长度 的节点满足 ,。因为下一个单独的集合非空,每个节点均可延伸。这里只为一个节点验证存在性,没有同时作整族选择;分支原则才提供无限相容的选择函数。
最后设每个 可数。所有单射 组成非空集合 ,当 为空时也有唯一空单射。可数选择同时取 。对并集元素 ,取最小所属指标 ,将它送到 ,便单射到已由显式配对证明可数的 。从逐项存在编码到实际编码序列,使用的正是所述选择原则。
证明透视
递归需要规则,不只是可能的下一步
后继关系可能有许多输出。递归在得到一个单值后继函数后才适用,第一证明通过 AC 得到它。DC 则直接断言存在相容链。在知道分支存在前,有限选择树已经无终端;逐点核实存在延伸并没有暗中完成无限分支的构造。
证明
(依赖地选取嵌套闭球)
证明 Baire 时,设 是完备度量空间中的开稠密集, 是任意非空开集。构造闭球
使 、。这里 表示闭度量球 ,它由三角不等式可知是闭集;没有断言它在一般度量空间中等于对应开球的闭包。
首球存在,因为 非空且开,取一点和充分小的正半径即可。给定第 球,开球 与 相交。在交集中选一点,利用开性取更小闭球装入其中,半径再限制为至多 。
要正当化无限继续,取所有合格三元组 为状态,条件为 、。将一个状态关联到第 层、且闭球包含于原开球内的状态。前面的观察证明关系处处有后继。由一个第零层状态出发,DC 给出所需序列。把层数包含在状态中,才会保证下一要求是 ,而非不确定的稠密集。
若 ,嵌套性使 ,所以 时 ,球心序列 Cauchy。设极限为 ;每个 闭且包含尾段球心,故包含 。于是 。 是任意非空开集,故交集稠密。空完备空间的稠密性陈述直接成立。
若 且各 无处稠密,则 开且稠密。 非空时,已证稠密性使这些 的交非空,却与声称覆盖全空间的并不交,矛盾。证明没有使用球的紧致性,也没有用收敛子序列定理;完备性和半径趋零才是收敛机制。
例题
例题 4.2.7
(任意长有限路径却没有无限路径)
令 为空序列和全部自然数严格递减有限序列组成的树,取前缀仍在 。每个 都有长度 的节点,例如 时的 。但起于 的递减序列长度至多为 ,所以没有无限分支。以零结束的节点不能延伸,树并非无终端,故不违反 DC。这说明分支数不受限制时,只有无界有限高度并不够。
例题 4.2.8
(二元树有规范的下一步)
对于 上的无终端树,若补零仍在树中就补零,否则补一;无终端性保证后一选择存在。这样已指定后继函数,普通递归便在 ZF 中给出分支。一般分支原则处理任意标签集合,不带规范次序;不能从这个特殊二元情况判断它的全部强度。
例题 4.2.9
(有理数直线缺少完备性)
通常度量的 中,单点集闭且内部为空。因此可数集 是可数个无处稠密集的并,不是 Baire 空间。完备性失败:逼近 的二进有理数构成 Cauchy 序列,却没有有理数极限。Baire 构造仍会产生 Cauchy 球心,但最后缺少空间中的落点。
例题 4.2.10
(给定可数数据能消去一次选择)
假设完备度量空间带有指定的可数稠密序列,枚举以这些点为球心、正有理数为半径的所有球。任意非空开集内都有这样的球,连同其闭球也在该开集内:先取小环境球,再取附近稠密点及更小有理半径。嵌套球的每一步便选满足包含关系和半径界的最小指标。这是唯一指定的规则,所以 Baire 构造可在 ZF 中递归进行。最小合格指标未必可计算,因为未假定集合包含条件可判定。规范的数学选法与有效算法是不同断言。
常见错误
常见错误
(可数选择计算的是指标集,不是各成员)
可数选择中的各集合本身不必可数。另一方面,有限选择可在 ZF 中归纳证明,却不能据此跳到无限多次相容选择。“依此继续”必须给出后继规则,或指出产生序列的原则。
常见错误
(特殊树不能推出完整的 DC)
分支原则涉及任意集合上的每棵无终端树。标签已良序的特殊树可作规范选择,并不会单独推出完整 DC。本文只证明了给定的正向蕴涵和一个特定等价关系,没有建立模型论的逆向失败或独立性结论。
在 ZF 中两个箭头都不能反转,而 Baire 定理其实与 DC 本身一样强。
自然的下一个问题
这些蕴涵能否反过来?
在 ZF 中两个箭头都不能反转,而 Baire 定理其实与 DC 本身一样强。
两个正向蕴涵都不能反转。若 ZF 一致,则存在可数选择成立而 DC 不成立的 ZF 模型,也存在 DC 成立而 AC 不成立的 ZF 模型;这些模型用力迫法和对称模型方法构造,超出本课程范围。另一方面,已知在 ZF 上,完备度量空间的 Baire 定理蕴涵 DC,所以嵌套球证明中对 DC 的使用一般无法避免。
常见错误
(完成 Baire 论证的是完备性,不是紧致性)
Baire 证明需要稠密集开,才能装入下一闭球;极限要留在定义域内,则需要完备性。闭球未必紧致。半径即使趋零,若无完备性,交集仍可能为空。
反例模式
不开的稠密集可以互不相交
声称:在完备度量空间中,可数多个稠密集的交总是稠密。在带通常完备度量的 中,取
两者都稠密:区间 含有有理数,而 含有有理数 ,于是 。若 ,则 且 ,其中 ,于是 会是有理数。因此 。嵌套球证明在第一步就失效: 不含任何区间,放不进半径为正的闭球。定理要求稠密集是开集,正是这一点使每个新闭球能放进下一个 。
总结
AC 提供后继函数,进而给出 DC;DC 恰好等价于任意无终端树有分支,并提供可数同时选择。可数选择使分别存在的可数编码成为一个整族。Baire 的嵌套球证明显示依赖选择的步骤;有指定可数数据时,有时能用规范规则替代这一步。
练习
快速检查
(在 ZF 中证明有限选择。若一个非空可数集的可数族有可数并,直接说明它有选择函数,不要分别选取各成员的枚举。)
解答 · 答案
零个集合用空函数。若一个有限族已有选择函数,再加入一个非空集合,只需取其中一个元素来延伸。存在性归纳证明每个有限断言,并未选择无限族。对题设可数族,固定一个单射 ,它由并集可数性提供。从 取唯一的元素,使其 值为非空集合 的最小元。替换公理收集这个唯一确定的选择函数,无须整族分别枚举。
快速检查
(设 已良序、 处处有后继,在 ZF 中由指定起点构造链。若 且 可判定,为何所得链可计算?)
解答 · 答案
定义 为给定良序下最小的 -后继,后继性质保证存在,再递归令 。若底集为 且 可判定,按 搜索,直至 ;后继性质保证终止,逐次搜索便计算每项。任意抽象良序却未必提供“取最小元”的算法。
快速检查
(去掉开性后,证明实直线的可数个稠密子集之交未必稠密,只需用两个不同稠密集。)
解答 · 答案
取 ,每个 取 。有理数和无理数都稠密:任意区间有有理数,也可用足够小的无理数倍移位得到无理数。它们的交为空。这两个集合在通常实拓扑中都不开,故不违反 Baire 定理。
快速检查
(构造 中非空闭球的嵌套序列,半径趋零而交为空。使用包含 的二进区间。)
解答 · 答案
令 ,取 。二进区间嵌套,端点有理且非空,在 中是中心 、半径 的闭球。相应实区间都含 ,直径趋零,故在 中交为 ,在 中则为空。障碍是缺失极限,不是嵌套失败。
快速检查
(有些 DC 定义只要求每个非空且处处有后继的关系有链,不指定首项。在 ZF 中证明这种无指定起点的形式推出本文指定起点的形式。)
解答 · 答案
给定 ,用所有以 开始的非空有限 -链为状态,以一步延伸为关系。至少存在单项状态 ,关系处处有后继。无指定起点的原则给出这些有限状态的无限链,即使从较长状态开始也无妨。各状态相容之并定义于整个 ,从 开始且沿 。定义域确为 ,因为每步有限长度增加一。这样,指定起点已编码入状态空间。反向只须忘掉指定起点。