新基础

在數理邏輯中，**新基礎集合論**（**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\ $ 的單射函數）。但如果 $V\ $ 是全集的話，當然有從 $P(V)\ $ 到 $V\ $ 的單射。為了解決這個問題，我們需要注意到 $|A|<|P(A)|\ $ 在類型論中沒有意義： $P(A)\ $ 的類型比 $A\ $ 的類型高 1。正確的有類型版本（它是在類型論中的定理，成立的原因就像康托爾定理在 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 年，王浩展示了如何修正蒯因的公理來避免這個問題，蒯因在 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. （頁面存檔備份，存於網際網路檔案館）