正则性公理
正则公理(也叫做基础公理)是 Zermelo-Fraenkel 集合论的公理之一。在一阶逻辑中,这个公理可叙述如下:
翻译为较容易理解的说法就是:
从这个公理可得出两个结果,其一为“不存在以自身为元素的集合”,其二为“没有无限序列 an 使得对于所有 i,ai+1 是 ai 的元素”。
通过选择公理可以证明後者的逆命题也成立:如果这樣的无限序列不存在,则正则公理为真。所以在假定选择公理的情況下,两个陈述是等价的。
正则公理被认为是Zermelo-Fraenkel 集合论中应用最少的公理,因为数学分支中的所有关键性结果都可用集合论中的其他公理證明得到。另外,不包含正则公理的康托的集合论,实际上假定了以自身为一个元素的集合的存在。
基本蕴涵
不存在以自身为元素的集合
反證,假设有一个集合A,使得 A 是自身的一个元素,即。这时,根据配对公理,可以构造出 B = {A},B也是一个集合。由于B中只有一个元素A,根据正则公理,我们得到。但是根据我们的假定,所以,矛盾!所以不存在這樣的集合A。
不存在无限递降的集合序列
设 f 為一定義在自然数集上的函数,且对每个 n,f(n+1) 都是 f(n) 的一个元素。定义 f 的值域 S = {f(n): n 是自然数},按照函数的形式定义S是一个集合。對S应用正则公理,可知S中有一个元素f(k),其与S不相交。但按照 f 和 S 的定义,f(k) 和 S 有一个公共元素(就是 f(k+1))。这是个矛盾,所以不存在这样的 f。
注意这个论证只有在集合(而非不可定义的类)的情況下才對 f適用。继承有限集合 Vω 是满足正则公理的,所以如果你構造Vω的一个非平凡的超冪,那么它也會满足正则公理,但是,它會包含无限递减的元素序列。例如,假定 n 是非标准自然数,则有 和 ,如此類推,对于任何標準的自然数 k 有 。所以这是个無限递降的元素序列。但是这个序列在这个模型中是不可定义的,因此它并不是集合,也就沒有違反正则公理。
假定选择公理,则"无限递减的集合序列不存在"蕴涵正则公理
设非空集合 S 是正则公理的一個反例;就是说 S 的所有元素都与 S 有非空交集。设 g 是 S 的选择函数,就是说对于 S 的每个非空子集 s,g 會把s 映射到 s 自身的一个元素。然後,在非负整数上递归的定义函数 f 为如下:
那么对于每个 n,f(n) 是 S 的一个元素,因此它与 S 的交集是非空的。從而f(n+1) 是良好定义的,并且是 f(n) 的一个元素。所以 f 是一個无限递降的链。这是一个矛盾,所有这样 S 不存在。
确使有序对 (a,b) 可定义为 {a,{a,b}}
这个定义消除了有序对的 Kuratowski 规范定义 (a,b) = {{a},{a,b}} 中的一对花括号。
良基性和超集合
在 1917 年,Dmitry Mirimanoff引入了良基性概念:
- 一个集合 x0 是良基的,当且仅当它没有无限递降的集合序列:
- · · ·
在 ZFC 中通过正则公理而没有无限递降 ∈序列(不然,請試想{, …}並運用正則公理的定義)。实际上,正则公理经常叫做基础公理,因为可以证明在 ZFC-(没有正则公理的 ZFC)中,良基性蕴涵了正规性。
在一些没有正则公理的 ZFC 变体中,非良基集合是可以存在的。在这种系统中工作的时候,不必然良基的集合叫做超集合。明显的,如果 A ∈ A,则 A 是非良基超集合。
超集合的理论已经应用于计算机科学(进程代数和最终语义)、语言学(情景理论)和哲学(谎言者悖论)中。
較知名的反基础公理有三个:
- AFA(反基础公理)— 由 M. Forti 和 F. Honsell 提出;
- FAFA(Finsler 的 AFA 版本)— 由 P. Finsler 提出;
- SAFA(Scott 的 AFA 版本)— 由 Dana Scott 提出。
其中第一個的 AFA 是基于Accessible pointed graph(apg),它斷言两个超集合是相等的,当且仅当它们可被同一个 apg 描绘。在这个框架下,可以证明那定义为 Q={Q} 的所谓蒯因原子,是唯一存在的。
值得强调的是,超集合理论是经典集合论的扩展而非替代者:在超集合领域内的良基集合符合经典集合论。可以在新基础或正集合论(或更一般的说带有是自身的元素的全集的任何集合论)中找到的非良基种类是非常不同的。
罗素悖论和正则公理的联系
罗素悖论的存在说明了朴素集合论(无超集限制的概括公理模式和外延公理)不具有一致性。为避免产生悖论,只需将无限制的概括公理模式替换成弱很多的分类公理模式。这样做会大大限制集合论的表达能力,不过丢失的表达能力可以通过引入ZF集合论中的其他公理(配对公理、并集公理、幂集公理、替换公理、无穷公理)来找回。到目前为止,这些公理应该不会导出任何矛盾。随后可以在此基础上添加选择公理和正则性公理,将一些性质不好的类排除出集合论的讨论范畴。已知这两条公理相对具有一致性。
罗素悖论源于全集的存在。在ZF集合论中,使用分类公理模式,罗素悖论成为“不存在包涵()一切的全集”的反证法归谬(如果全集存在,那么会产生罗素悖论)。虽然也可以通过正则性公理和配对公理来证明全集不存在(如果存在全集U,那么{U}不满足正则性公理),但无需正则性公理,仅分类公理模式一条就已经禁止了全集的存在性。
如果向一个公理体系添加更多公理,那么原体系中的任何(包括不想要的)结论仍然会是扩展体系的结论。如果去掉正则性公理的ZF集合论本身是不一致的(比如说会导致罗素悖论),那么引入正则性公理的ZF集合论仍然会导致同样的矛盾。所以在ZF集合论中引入正则性公理不是为了避免罗素悖论。
蒯因原子的存在性(满足x = {x}的集合),与去除正则性公理的ZFC集合论是独立的(不会导致矛盾)。有很多非良基集合论允许特定的循环属于的集合存在,而不会产生罗素悖论。[1]
參考文獻
- ^ Rieger 2011,第175,178頁.
- Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
- Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.
外部链接
- https://web.archive.org/web/20021118032213/http://www.trinity.edu/cbrown/topics_in_logic/sets/sets.html contains an informative description of the axiom of regularity under the section on Zermelo-Fraenkel set theory.
- Axiom of Foundation. PlanetMath.