“偏序与链上界构成假设,选择公理和良序定理与 Zorn 引理等价。它广泛证明任意向量空间有基、每个真理想包含于极大理想,以及代数闭包和部分映射等延拓对象存在;但它通常不给出可计算构造,也绝不能…”
形式陈述 ​
良序是满足以下条件的全序
良序定理断言:对任意集合
在 ZF 集合论中,良序定理与选择公理等价;在默认采用 ZFC 的语境中,它因而是一条定理。等价性意味着,不能把“任意集合可良序”视为完全不带选择强度的普通排序事实。
直觉
良序比全序多出“任何非空部分都有第一个元素”。全序只保证两元素可以比较,仍可能存在没有起点的下降方向;良序则允许不断选取当前剩余集合的最小元,从而把集合沿序数阶段逐步枚举。
定理并不说集合原有的自然次序已经良序。实数的通常大小关系不是良序,因为区间
“存在一个良序”与“能够有效算出下一个元素”也不同。选择公理提供集合论存在性,却不自动给出可计算结构。把良序用于算法或构造时,必须额外说明表示方式和有效性。
例子与边界
自然数的通常次序是良序。整数的通常次序不是良序,因为整个
这个次序与通常大小无关,却使每个非空整数子集都有最先出现的元素。
有限二进制串的普通字典序可以是全序,却不是良序。在
集合
良序也不同于一般偏序上的良基性。良基关系排除无限下降并保证非空子集有极小元,但极小元可能不唯一;良序还要求全序,所以极小元自动是唯一最小元。超限递归通常需要完整良序,而某些终止性证明只需良基关系。
推论与应用
每个良序集都与唯一的序数同构。因而良序定理等价于:每个集合都可以与某个序数建立双射。这个观点把任意集合纳入序数和基数的统一框架,并允许比较任意两个集合的基数。
良序支持超限归纳与超限递归。构造在每个阶段只依赖更早阶段,极限阶段再汇总此前结果;良序保证不存在尚未处理却没有第一个元素的残余部分。
在 ZF 中,良序定理、选择公理和Zorn 引理互相等价。实际证明通常选择最符合问题形状的版本:递归构造偏好良序,极大对象存在性偏好 Zorn 引理,逐族选取元素则直接使用选择函数。
参考资料
- Thomas Jech, Set Theory, 3rd millennium ed., Springer, 2003, Chapter 5.
- Herbert B. Enderton, Elements of Set Theory, Academic Press, 1977, Chapter 7.
- Kenneth Kunen, Set Theory, College Publications, 2011, choice and well-ordering.