动机
从一个非空集合取一个成员是存在量词的实例化,有限次重复也不成问题。但这不等于存在一个函数,为任意无限集合族同时选取成员。选择公理正是额外断言这种函数存在。
独立集延拓为基、偏序集中存在极大对象,看似与选择无关,却与它等价。这类工具在没有显式算法时尤其有用,但假设必须检查。极大不是最大;每对元素有上界,也不能取代每条链有上界。
定义
定义 4.1.1
(选择函数与选择公理)
对集合索引的非空集合族 ,选择函数是定义域为 且 的函数。选择公理 AC 断言每个这样的族都有选择函数。输入族必须是集合;AC 没有提供全体非空集合这个真类上的统一选择函数。
定义 4.1.2
(链、上界与极大元素)
偏序具有自反、反对称、传递性。链是其中任意两个成员都可比较的子集。 的上界 满足每个 都有 ,但不必属于 。 是极大元素,若 总推出 ;它是最大元素,若所有 都有 。
定义 4.1.3
(良序原理与 Zorn 引理)
良序原理说每个集合都可赋予良序。Zorn 引理说,非空偏序集中若每条链都有上界,则存在极大元素。空链的上界可取任意成员。
定理/命题
定理 4.1.4
(Hartogs 定理(ZF))
每个集合 都有一个不能单射到 的序数,可取最小者 。不必先假设 可良序。
定理 4.1.5
(ZF 上选择公理、良序原理与 Zorn 引理等价)
在 ZF 上,AC、良序原理、Zorn 引理彼此等价。
定理 4.1.6
(基延拓(使用 AC))
域上的向量空间 的任意线性无关子集 都包含于某个基 。
证明思路
证明
(超越子集上一切良序的序数)
的子集上的全部良序可编码为 中的对 ,因而构成集合。替换收集其唯一序型为集合 。令
若 单射到 ,在像上运输它的良序,就有 ,从定义推出 ,矛盾。故存在失败的序数;在 内分离并取最小者,得到 。没有一步要求为整个 先选良序。
证明
(AC 推出良序原理)
由 AC,对非空 的全部非空子集取选择函数 ,并固定 。在 递归:若尚有未取元素,从剩余集合用 取一个;否则取 。若始终没有取尽,各值互异,就得到 ,矛盾。因此某个较早阶段已取尽;此前的无重复枚举把一个序数的良序运输到 。空集本身已良序。这给出了严格的停止界,而不是含糊地说“一直取到完”。
证明透视
Hartogs 提供停止的界
递归沿预先固定的序数 进行,因此不需要含糊的“取到完为止”。选择只出现一次,就是 的非空子集上的单一选择函数 ;此后每一步都由先前的值唯一确定。默认值 只是让递归在取尽之后仍有定义。
关键一步是与 的定义矛盾。若每个阶段 的剩余集合都非空,每个值都与先前所有值不同,就得到单射 。因此某个阶段的剩余集合为空。在最小的这种阶段 , 之前的值互不相同且取尽 ,所以 是双射 ,把 的次序运输到 。
证明
(良序原理推出 Zorn 引理)
由良序原理,给 Zorn 假设中的 一个良序。依次遍历,某元素若与此前已取的每个元素可比较,就加入 。递归所得 是链,而且是按包含关系极大的链:若 与整个 可比较,它在自己的阶段就会被加入。设 是 的上界。若 ,则 与整个 可比较,故 ,从而 ,矛盾。所以 是 的极大元素。
证明透视
为什么极大链的上界是极大元
上的良序使遍历成为每一步只有一个结果的递归,所以构造 时不再作任何选择。真正的想法是 在链之中是极大的:与 每个成员都可比较的元素早已在 中。把这一点用于上界 ,就知道 属于 并且是其最大成员;用于假想的 ,便迫使 。Zorn 的链条件只用了一次,就是用于这一条链。良序的第一个元素必定被加入,所以 非空保证 非空。
证明
(Zorn 引理推出 AC)
由 Zorn 推出 AC:把所有部分选择函数按延拓排序。其图像属于 ,所以这是集合,并含空函数。一条链的并仍是部分选择函数,因为同一指标的两个值出现在可比较的函数中,必相同。这个并是上界。极大部分选择函数若遗漏 ,从一个非空 取一个成员就能延拓,矛盾。因此定义域是 。这里取一个集合的一个成员,并没有循环使用 AC。
证明
(用 Zorn 引理延拓为基)
基延拓中,把包含 的线性无关子集按包含排序。非空链的并 仍线性无关:任何线性关系只涉及有限多个向量,链中有限多个承载它们的成员有最大者,所以关系已在一个无关集中,全部系数为零。空链以上界 处理。Zorn 给出极大 ;若 ,则 仍无关,矛盾。故 张成并为基。
例题
例题 4.1.7
(极大不等于最大)
的真子集按包含排序,、 都极大,没有最大者。极大无关集不需要包含每个向量,只要求再加入任何向量都会破坏无关性。整个向量空间还含零向量,当然不会作为一个向量集线性无关。
反例模式
每对元素有上界不足以用 Zorn
声称:若非空偏序集中每对元素都有上界,则它有极大元素。正整数通常序中,每对元素都有上界,即较大者,但没有极大元素。全部正整数这条链没有整数上界,故缺少的 Zorn 假设是真正的障碍。
例题 4.1.8
(规范选择无需 AC)
有限非空集合族可按族的大小归纳构造选择函数。对任意非空自然数子集族,可取每个集合的最小元,再用替换收集唯一值。因此无限集合族也可能因存在统一规范而无需 AC。
例题 4.1.9
(延拓线性泛函)
设 是子空间, 线性。取 的基 并延拓为 的基 。在 上保留 的值,在 上赋零;唯一有限基展开定义线性延拓 。依赖选择的是基的存在,基固定后公式唯一。这是代数结论,没有声称连续性。
例题 4.1.10
(极大理想为何产生域)
下面练习中的极大理想还有重要用途。若 是有单位交换环 的极大真理想,则 是域。取非零陪集 ,即 。理想 真包含 ,故等于 。因此存在 ,使 。模 化简得到 ,每个非零陪集都有逆。 为真还保证 。
反过来,若 是域,且理想 真包含 ,取 。非零陪集 有逆 ,所以 。又 ,相减得 ,故 。这证明极大性与商环为域等价,也说明极大对象达到了什么数学目的。
依赖选择的存在性与后面的商环运算作用不同。某个极大理想一旦给定,证明它的商为域不需要新增任意选择;每个非零陪集的逆唯一。类似地,Zorn 可给出基的存在,而坐标唯一性由有限线性无关性证明。分开这些步骤,就能准确指出应用中 AC 出现在哪里,而不把整段代数计算笼统归为“使用选择”。
旁注
唯一答案无需额外任意选择
具有唯一见证的存在断言与 AC 所处理的集合族不同。若一个集合中的每个输入恰有一个输出,ZF 的替换已能收集输出及其函数图像;没有备选项,就不必另作选择。域中非零元素的唯一逆、相对于固定基的唯一坐标都是例子。
反之,满射的每个纤维可能有许多点。构造右逆需要为每个纤维取一点;定义域已有良序时可以规范地取最小点,没有这种结构时,同时选取就是另一个问题。区分二者可以避免两种相反错误:无规则地挑代表却忽略 AC,或见到“对每个”就不必要地援引 AC。关键不在指标集是否无限,而在已有数据是否唯一指定所需值。特别地,基存在可能依赖选择,固定该基之后的有限坐标运算却不因此每步都需要重新选择。清楚标明这条界线,会使代数应用的公理依赖更容易检查。
可比较性与有限特征
实际应用中还常见另外两种形式的选择。第一种关于大小:没有选择时,两个集合甚至未必能用单射比较。第二种把基延拓证明中的取并论证抽出,成为可以反复使用的引理。
定理 4.1.11
(大小的可比较性等价于 AC)
在 ZF 上,选择公理等价于以下命题:对任意集合 、,存在单射 或单射 。
证明
(把集合与它的 Hartogs 序数比较)
设 AC 成立。由良序原理,有双射 及 ,其中 为序数。序数比较给出 或 。前一情况下,经包含 理解的 是单射 ;后一情况下, 是单射 。
反过来,设可比较性成立,并任取集合 。把 与 Hartogs 定理给出的序数 比较。按定义 不能单射到 ,所以存在单射 。规定 当且仅当 ,便在 上得到良序:它是序数集合 的成员序沿单射拉回的结果。因此每个集合都可良序,由上面的等价定理得 AC。这个论证只用到集合与一个序数之间的可比较性。
定义 4.1.12
(有限特征的集合族)
设 为集合。若对每个 , 当且仅当 的每个有限子集都属于 ,则称集合族 具有限特征。
有限特征的集合族对子集封闭:若 且 ,则 的每个有限子集都是 的有限子集,因而属于 ,故 。向量空间的线性无关子集组成这样的集合族,因为一个线性关系只涉及有限多个向量。偏序中的链亦然,因为可比较性是对每对元素的条件。
定理 4.1.13
(Tukey 引理)
设 AC 成立, 是集合 上具有限特征的集合族。则 的每个成员都包含于 中某个按包含关系极大的成员。在 ZF 上,对所有具有限特征的集合族成立的这个命题等价于 AC。
证明
(有限特征保证链的并仍然合格)
固定 ,令 ,按包含排序。在 内分离可知它是集合;它含 ,而 也是空链的上界。设 是 中的非空链,。 的有限子集 中每个 都属于 的某个成员。这有限多个成员两两可比较,所以其中有一个 包含其余各个,该有限子集便落在 中(空子集落在任何成员中)。由对子集封闭,它属于 。由有限特征得 ,且显然 ,故 是 中的上界。Zorn 引理给出 的极大元素 。若 ,则 ,所以 且 。因此 在 中极大。
反方向:设 是非空集合族,令 。子集 是某个部分选择函数的图像,当且仅当其中没有两个有序对第一坐标相同而第二坐标不同。这是对二元子集的条件,所以这些图像组成含 的有限特征集合族。其极大成员在每个指标处都有定义,因为若遗漏指标 ,就可以用 的一个元素把它延拓。所以它是选择函数。
例题 4.1.14
(每个偏序都可延拓为线性序)
设 为偏序。考虑所有包含 的偏序 ,按包含排序。其中非空链的并仍是包含 的偏序:自反性自然保留,而检查反对称性或传递性时涉及的两三个有序对都落在链的同一个成员中。空链以 本身为上界。Zorn 引理给出极大的 。
假设某对 在 下不可比较,令
它含 ,且自反。传递性:取 。若两者都在 中, 也在。若只有 是新的,则 且 ,所以 是 的新有序对;只有 是新的情况对称。若两者都是新的,则 ,与不可比较矛盾,所以这种情况不会出现。反对称性:设 且 。两者不能都在 中。若其中之一,例如 ,是新的,则 且 ;另一个有序对给出 ,或者若它也是新的,则给出 及 。每种情况都推出 ,不可能。所以 是严格大于 的偏序,与极大性矛盾。因此 是延拓 的线性序。若 有限,把这一步延拓重复有限次,不用任何选择原理即得结论。
常见错误
常见错误
(链不是序列)
链在给定的偏序下是全序的;它不必是序列,可能不可数。
常见错误
(取并集还不是上界证明)
“取并集”不是完整的上界证明,必须检查定义性质仍成立。无关性的有限特征保证该例成功,闭性或完备性却未必在并下保持。
常见错误
(Zorn 给出存在,不给出唯一性或独立性结果)
Zorn 不给出唯一对象,也不指定算法。这些等价不证明 AC 是 ZF 定理,也不证明其否定;独立性与相对相容性需要本节以外的元数学。
总结
Hartogs 给出集合大小的停止界。AC 产生良序,良序构造极大链,Zorn 把部分选择函数补全。大小的可比较性与 Tukey 引理是另外两种等价形式;后者把线性无关集的取并论证变成一般工具。应用极大性时依次检查非空、每条链的上界,以及极大对象为何具有目标性质。
练习
快速检查
(设满射 的陪域非空,且定义域、陪域都可良序,证明它有右逆。真正用于选择的是哪一个良序?)
解答 · 答案
良序 ,对每个 取非空纤维 的最小元 。替换给出函数,且 。真正选择来自 的良序, 可良序的条件其实多余。
快速检查
(详细证明向无关集 加入 后仍无关。)
解答 · 答案
若 ,其中 互异, 会把 表为 的有限线性组合,矛盾。故 ,再由 无关得所有 。不含 的关系本来就受控制。
快速检查
(用 Zorn 证明有单位交换环的每个真理想包含于极大真理想,说明链的并为何仍真。)
解答 · 答案
所有包含 的真理想组成非空偏序集。非空链的并是理想,因为任意两元素同属某个链成员,可在那里完成加法及乘环元素。若并含 ,某个成员已含 ,就等于整个环,矛盾。空链以上界 处理。Zorn 给出的极大成员不能再包含于更大的真理想,否则仍在此偏序集中。
快速检查
(解释无限集合的有限子集按包含排序时,为何不自动满足 Zorn 假设。)
解答 · 答案
链的并可能无限,从而不属于有限子集偏序集。取 ,链 没有有限上界,就足以反驳一般断言。对有限个成员有上界(有向性)并不足够。在 ZF 中讨论任意无限 时,也不能暗中预设能选出可数无穷个不同元素。
快速检查
(用 Tukey 引理证明 Hausdorff 极大原理:偏序集中的每条链都包含于某条按包含关系极大的链。)
解答 · 答案
子集 是链,当且仅当它的每个二元子集都是链,亦即当且仅当它的每个有限子集都是链。所以链在 中组成具有限特征的集合族,Tukey 引理把任何链延拓为极大链。极大只表示没有链真包含它。在按包含排序的 中, 与 是两条不同的极大链。
快速检查
(设 AC 成立。证明 作为 上的向量空间,有一个同时包含 与 的基。)
解答 · 答案
在 上的线性无关性具有限特征。 线性无关:若 , 且 ,则 为有理数,矛盾;所以 ,从而 。Tukey 引理把 延拓为极大线性无关集 。与基延拓的证明相同,若 ,则 仍线性无关,矛盾;故 张成 。
快速检查
(在 ZF 中证明:能单射到某个可良序集合的集合本身可良序。这一步出现在可比较性证明的哪里?)
解答 · 答案
设 为单射, 是 上的良序。规定 当且仅当 。它反自反、传递,并因 迫使 而线性。非空 使 非空,其最小元恰为某个唯一 的像 ,而这个 就是 中的 最小元。在可比较性证明中,这正是从单射 得到 上良序的一步,其中 扮演可良序集合。