新基础集合论

在数理逻辑中，新基础集合論(NF)是公理化集合論的一種，由蒯因构想出來作为对《数学原理》中类型论的简化。蒯因 1937 年於《数理逻辑的新基础》一文中首次提及NF（此即其名稱的由來）。請注意，此条目大多是在談论 NFU，這是Jensen於1969年所提出，並由Holmes於1998年闡述的一重要变体。

类型论 TST

改进版本的类型论 TST 的基本谓词是等式和成员关系。TST 有一个线性的类型层次: 类型 0 由不加描述的个体组成。对于每个(元-)自然数 n，类型 n+1 的对象是类型 n 对象的集合；类型 n 的集合有类型为 n-1 的成员。用等式连接的类型必须有相同的类型。下列两个原子公式简洁的描述了定类型规则：$x^{n} = y^{n} \$ 和 $x^{n} \in y^{n+1}$ (符号仍可改进)。

TST 的公理是:

• 外延性: 带有相同成员的相同(正数)类型的集合是相等的；
• 概括公理模式，也就是:

如果 $\phi(x^n)\$ 是公式，则集合 $\{x^n \mid \phi(x^n)\}^{n+1}$ 存在。

换句话说，给定任何公式 $\phi(x^n) \$，存在集合 $A^{n+1}\$ 使得 $\forall x^n \exists A^{n+1} [x^n \in A^{n+1} \leftrightarrow \phi(x^n)]$ 为真。

这个类型论简单许多于《数学原理》首次发表的类型论，它包括其参数不必然都有同样类型的关系类型。在 1914 年，諾伯特·維納展示了如何把有序对编码为集合的集合。这使得以这里描述的集合层次的方式消除了关系类型。

蒯因集合论

公理和层化

新基础(NF)是通过放弃 TST 的类型区别而获得的。NF 的公理有:

• 外延性: 有相同元素的两个对象是同一个对象；
• 概括模式: 所有 TST 的概括实例，但去掉了类型索引(并且不用介入在变量之间新的同一性)。

通过约定，NF 的概括模式使用层化公式的概念而陈述的而不直接提及类型。一个公式 $\phi$ 被称为是层化的，如果存在从语法片段到自然数的一个函数 f，使得对于任何 $\phi$ 的原子子公式 $x \in y$ 有 f(y) = f(x) + 1，而对于任何 $\phi$ 的原子子公式 $x=y$，有 f(x) = f(y)。概括接着变成:

对于每个层化公式 $\phi$ 存在 $\{x \mid \phi \}$。

甚至在层化概念内隐含的对类型的间接提及也可以消除。Hailperin 在 1944 年证实了概括等价于它的实例的有限合取，所以 NF 可以有限的公理化而不提及类型的概念。

对于朴素集合论概括好像是不自洽的，但是在这里不是。例如，不可能的罗素类 $\{x \mid x \not\in x\}$ 不是 NF 集合，因为 $x \not\in x$ 不能被层化。

有序对

关系和函数在 TST (与 NF 和 NFU)中以通常的方式定义为有序对。首先由 Kuratowski 在1921年提议的有序对常用的定义对于 NF 和相关理论有个严重缺陷: 结果的有序对必定有比它的参数(它的左和右投影)的类型高 2 的类型。所以用途是决定分层的函数有比它的域的成员高 3 的类型。

如果能以其类型是同它的参数一样的类型的方式定义对(导致一个类型-齐平有序对)，则关系或函数有只比它的域的成员的类型高 1 的类型。所以 NF 和相关理论通常采用蒯因的有序对的集合论定义，它生成类型的类型-齐平的有序对。Holmes (1998) 把有序对与它的左和右投影接受为基本的。幸运的是，有序对是否通过的定义或通过假定(就是接受为基本的)而是类型-齐平，通常是不重要的。

类型-级别有序对的存在蕴涵了“无穷”，而 NFU +“无穷”解释了 NFU +“存在着类型齐平的有序对”(它们不是同样的理论，但是区别无关紧要)。反过来，NFU +“无穷”+“选择”证明了类型-齐平有序对的存在。

有用的大集合的可容纳性

NF (和 NFU +“无穷”+“选择”，下面描述并已知是相容的)允许构造 ZFC 和它的真扩展因为“太大”而不允许的两种集合(某些集合论在真类的名义下接受这些实体):

• 全集 V。因为 $x=x$ 是层化公式，通过概括存在全集 $V = \{x \ | \ x=x \} \$。直接的推论是所有集合都有补集，而在 NF 下的整个集合论全集有一个布尔结构。
• 基数和序数。在 NF (和 TST) 中，存在 n 个元素的所有集合的集合 (这里循环性只是外观上的)。所以弗雷格的基数定义在 NF 和 NFU 中可行: 基数是集合在等势关系下的等价类: 集合 A 和 B 是等势的，如果存在它们之间的双射，在这种情况下我们写为 $A \sim B \$。类似的，序数是良序集合在相似关系下的等价类。

NF(U) 如何避免集合论悖论

NF 清除了三个周知的集合论悖论。NFU 是{相对}相容的理论也避免了这些悖论，增强了我们在这个事实上的信心。

罗素悖论：$x \not\in x$ 不是层化公式，所以 $\{x \mid x \not\in x\}$ 的存在不被任何概括的实例所断言。蒯因构造 NF 的时候大概最关注于这个悖论。

关于最大基数的康托尔悖论利用了康托尔定理对全集的应用。康托尔定理声称(假定 ZFC)任何集合的 $A \$ 的幂集 $P(A) \$ 大于 $A \$ (没有从 $P(A) \$ 到 $A \$ 的单射函数(一一映射))。当然有从 $P(V) \$ 到 $V \$ 的单射，如果 $V \$ 是全集的话！解决这个问题需要我们观察到 $|A| < |P(A)| \$ 在类型论中没有意义：$P(A) \$ 的类型高 1 于 $A \$ 的类型。正确的有类型版本(它是与在 ZF 中工作的最初形式的康托尔定理本质上同样道理的类型论中的定理)是 $|P_1(A)| < |P(A)| \$，这里的 $P_1(A) \$ 是 $A \$ 的一个元素的子集的集合。我们感兴趣的这个定理的特殊实例是 $|P_1(V)| < |P(V)| \$：一个元素的集合们少于集合们(因此一个元素的集合们少于全体对象，如果我们在 NFU 中的话)。从全集到这些一个元素集合明显的双射 $x \mapsto \{x\} \$不是一个集合；它不是集合是因为它的定义是非层化的。注意在所有已知的 NFU 的模型中 $|P_1(V)| < |P(V)| << |V| \$ 都成立；“选择”允许我们不只证明有基本元素而且在 $|P(V)| \$ 和 $|V| \$ 之间有很多基数。

我们现在介入某些有用的概念。集合 $A \$ 满足直觉上吸引人的 $|A| = |P_1(A)| \$ 就被称为康托尔式的：康托尔式集合满足通常形式的康托尔定理。集合 $A \$ 满足进一步条件 $(x \mapsto \{x\})\lceil A \$，即单元素集合映射于 A 的限制，则不只是康托尔式的而且是强康托尔式的。

下面是关于最大序数的布拉利-福尔蒂悖论。我们定义(跟从朴素集合论)序数是良序排序在相似性下的等价类。在序数上有一个明显的自然的良序排序；因为它是良序排序所以它属于一个序数 $\Omega \$。(通过超限归纳法)可直接证明在小于一个给定序数 $\alpha \$ 的序数们上的自然次序的序类型是 $\alpha \$ 自身。但是这意味着 $\Omega \$ 是小于 $\Omega \$ 的序数们的序类型，因此它严格小于所有序数的序类型 -- 但是通过定义，后者是 $\Omega \$ 自身！

在 NF(U) 中对这个悖论的解决开始于观察到在小于 $\alpha \$ 的序数们上的自然次序的序类型的类型比 $\alpha \$ 的类型高。因此类型齐平有序对的类型比它的参数的类型高 1，而常规的 Kuratowski 有序对高 3。对于任何序类型 $\alpha \$，我们可以定义比 $\alpha \$ 的类型高 1 的序类型: 如果 $W \in \alpha \$，则 $T(\alpha) \$ 是次序 $W^{\iota} = \{(\{x\},\{y\}) \mid xWy\}$ 的序类型。T 运算的烦琐只是外观上的；可以轻易的证明 T 是在序数们上的严格的单调(序保持)运算。

我们可以用层化的方式重申关于序类型的引理: 在小于 $\alpha \$ 的序数们上的自然次序的序类型是 $T^2(\alpha) \$ 或 $T^4(\alpha) \$，依赖于使用哪个有序对定义(我们在下文中假定类型齐平有序对)。从此我们可演绎出在小于 $\Omega \$ 的序数们上的序类型是 $T^2(\Omega) \$，从它我们演绎出 $T^2(\Omega)<\Omega \$。因此 T 运算不是个函数；我们不能有从序数到序数的严格单调集合映射，它向下映射一个序数！因为 T 是单调的，我们有 $\Omega > T^2(\Omega) > T^4(\Omega)\ldots$，在序数们中的“递减序列”不能是集合。

某些人已经断言这个结果证实了没有 NF(U) 的模型是“标准”的，因此在任何 NFU 的模型中序数们外在的不是不是良序的。我们不接受这种立场，而我们注意到还有一个 NFU 的定理，任何 NFU 的集合模型都有非良序的“序数”；NFU 不结论出全集 V 是 NFU 的模型，尽管 V 是集合，因为成员关系不是集合关系。

关于数学在 NFU 中的进一步开发，和与在 ZFC 中相同的开发的比较，请参见数学的集合论实现（en:Implementation of mathematics in set theory）。

蒯因在 1940 年第一版的《数理逻辑》的集合论中，结合了von Neumann-Bernays-Gödel 集合论的真类于 NF，并为真类包括了一个无限制概括的公理模式。在 1942 年，J. Barkley Rosser 证明了蒯因的集合论遭受 Burali-Forti 悖论。在 1950 年，Hao Wang 展示了如何修正蒯因的公理来避免这个问题，蒯因在 1951 年第二和最终版本的《数理逻辑》中包括了结果的公理化。

参见

• 公理化集合论
• 罗素公理体系
• ZFC
• 数学的集合论实现
• 自然数的集合论定义
• 正集合论
• 可替代的集合论

引用

• Holmes, Randall, 1998. Elementary Set Theory with a Universal Set. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this introduction to NFU via the web. Copyright is reserved.
• Jensen, R. B., 1969, "On the Consistency of a Slight(?) Modification of Quine's NF," Synthese 19: 250-63. With discussion by Quine.
• Quine, W. V., 1980, "New Foundations for Mathematical Logic" in From a Logical Point of View, 2nd ed., revised. Harvard Univ. Press: 80-101. The definitive version of where it all began, namely Quine's 1937 paper in the American Mathematical Monthly.

外部链接

• Stanford Encyclopedia of Philosophy:
  • Quine's New Foundations -- by Thomas Forster.
  • Alternative axiomatic set theories -- by Randall Holmes.
• Randall Holmes: New Foundations Home Page.
• Randall Holmes: Bibliography of Set Theory with a Universal Set.