新基礎集合論

在數理邏輯中，新基礎集合論（NF）是公理化集合論的一種，由蒯因構想出來作為對《數學原理》中類型論的簡化。蒯因1937年於《數理邏輯的新基礎》一文中首次提及NF（此即其名稱的由來）。請注意，此條目大多是在談論NFU，這是Jensen於1969年所提出，並由Holmes於1998年闡述的一重要變體。

類型論TST

改進版本的類型論TST的基本謂詞是等於和成員關係。TST有一個線性的類型層次：類型0由不加描述的個體組成。對於每個（元-）自然數n，類型n+1的對象是類型n對象的集合；類型n的集合有類型為n-1的成員。用等號連接的對象必須有相同的類型。下列兩個原子公式簡潔的描述了定類型規則：${\displaystyle x^{n}=y^{n}\ }$和${\displaystyle x^{n}\in y^{n+1}}$（符號仍可改進）。

TST的公理是：

• 外延性：帶有相同成員的相同（正數）類型的集合是相等的；
• 概括公理模式，也就是：

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

換句話說，給定任何公式${\displaystyle \phi (x^{n})\ }$，存在集合${\displaystyle A^{n+1}\ }$使得${\displaystyle \forall x^{n}\exists A^{n+1}[x^{n}\in A^{n+1}\leftrightarrow \phi (x^{n})]}$為真。

這個類型論比於《數學原理》首次發表的類型論簡單許多，因為它還得包括其參數不必然都有同樣類型的關係類型。在1914年，諾伯特·維納展示了如何把有序對編碼為集合的集合。這使得以這裏描述的集合層次的方式消除了關係類型。

蒯因集合論

公理和層化

新基礎（NF）是通過放棄TST的類型區別而獲得的。NF的公理有：

• 外延性：有相同元素的兩個對象是同一個對象；
• 概括模式：所有TST的概括實例，但去掉了類型索引（並且不用引入在變量之間新的同一性）。

通過約定，NF的概括模式使用層化公式的概念來陳述，而不直接提及類型。一個公式${\displaystyle \phi }$被稱為是層化的，如果存在從語法片段到自然數的一個函數f，使得對於任何${\displaystyle \phi }$的原子子公式${\displaystyle x\in y}$有f(y) = f(x) + 1；而對於任何${\displaystyle \phi }$的原子子公式${\displaystyle x=y}$，有f(x) = f(y)。概括接着變成：

對於每個層化公式${\displaystyle \phi }$存在${\displaystyle \{x\mid \phi \}}$。甚至在層化概念內隱含的對類型的間接提及也可以消除。Hailperin在1944年證實了概括等價於它的一些推論的有限合取，所以NF可以有限的公理化而不提及類型的概念。

對於樸素集合論概括好像是不自洽的，但是在這裏不是。例如，不可能的羅素類${\displaystyle \{x\mid x\not \in x\}}$不是NF集合，因為${\displaystyle x\not \in x}$不能被層化。

有序對

關係和函數在TST（以及NF和NFU）中以通常的方式定義為有序對。首先由Kuratowski在1921年提議的有序對常用的定義對於NF和相關理論有個嚴重缺陷：結果的有序對必定有比它的參數（它的左和右投影）的類型高2的類型。所以為了決定分層，函數有比它的定義域的成員高3的類型。

如果能以其類型是同它的參數一樣的類型的方式定義對（導致一個類型齊平有序對），則關係或函數有隻比它的域的成員的類型高1的類型。所以NF和相關理論通常採用蒯因的有序對的集合論定義，這樣得出的是類型的類型-齊平的有序對。Holmes（1998）把有序對與它的左和右投影定為原始概念。幸運的是，無論有序對是通過定義或通過假定（就是作為原始概念）而類型齊平，通常是不重要的。

類型齊平有序對的存在蘊涵了「無窮公理」，而NFU +「無窮公理」解釋了NFU +「存在着類型齊平的有序對」（它們不是同樣的理論，但是區別無關緊要）。反過來，NFU +「無窮公理」+「選擇公理」證明了類型齊平有序對的存在。

有用的大集合的可容納性

NF（以及NFU +「無窮公理」+「選擇公理」，下面描述並已知是相容的）允許構造兩種集合，它們都是ZFC和它的真擴展所不允許的，因為「太大」的緣故（某些集合論在真類的名義下接受這些實體）：

• 全集V。因為${\displaystyle x=x}$是層化公式，通過概括存在全集${\displaystyle V=\{x\ |\ x=x\}\ }$。直接的推論是所有集合都有補集，而在NF下的整個集合論全集有一個布爾結構。
• 基數和序數。在NF（和TST）中，存在n個元素的所有集合的集合（這裏循環性只是外觀上的）。所以弗雷格的基數定義在NF和NFU中可行；基數是集合在等勢關係下的等價類：集合A和B是等勢的，如果存在它們之間的雙射，在這種情況下我們寫為${\displaystyle A\sim B\ }$。類似的，序數是良序集合在相似關係下的等價類。

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

NF清除了三個周知的集合論悖論。NFU這個{相對}相容的理論也避免了這些悖論，增強了我們對這些理論的信心。

羅素悖論：${\displaystyle x\not \in x}$不是層化公式，所以不會通過概括的任何推論得出${\displaystyle \{x\mid x\not \in x\}}$的存在性。蒯因構造NF的時候大概最關注於這個悖論。

關於最大基數的康托爾悖論利用了康托爾定理對全集的應用。康托爾定理聲稱（假定ZFC）任何集合的${\displaystyle A\ }$的冪集${\displaystyle P(A)\ }$大於${\displaystyle A\ }$（沒有從${\displaystyle P(A)\ }$到${\displaystyle A\ }$的單射函數）。但如果${\displaystyle V\ }$是全集的話，當然有從${\displaystyle P(V)\ }$到${\displaystyle V\ }$的單射。為了解決這個問題，我們需要注意到${\displaystyle |A|<|P(A)|\ }$在類型論中沒有意義：${\displaystyle P(A)\ }$的類型比${\displaystyle A\ }$的類型高1。正確的有類型版本（它是在類型論中的定理，成立的原因就像康托爾定理在ZF中成立那樣）是${\displaystyle |P_{1}(A)|<|P(A)|\ }$，這裏的${\displaystyle P_{1}(A)\ }$是${\displaystyle A\ }$的單元素子集的集合。在這個定理中，使我們感興趣的特殊實例是${\displaystyle |P_{1}(V)|<|P(V)|\ }$：單元素集合們少於集合們（因此一個元素的集合們少於全體對象，如果我們在NFU中的話）。從全集到這些單元素集合明顯的雙射${\displaystyle x\mapsto \{x\}\ }$不是一個集合；它不是集合是因為它的定義是非層化的。注意在所有已知的NFU的模型中${\displaystyle |P_{1}(V)|<|P(V)|<<|V|\ }$都成立；「選擇公理」允許我們不只證明有基本元素，而且在${\displaystyle |P(V)|\ }$和${\displaystyle |V|\ }$之間有很多基數。

我們現在引入某些有用的概念。若集合${\displaystyle A\ }$滿足${\displaystyle |A|=|P_{1}(A)|\ }$，就被稱為康托爾式的：康托爾式集合滿足通常形式的康托爾定理。集合${\displaystyle A\ }$滿足進一步條件${\displaystyle (x\mapsto \{x\})\lceil A\ }$，即單元素集合映射在A上的限制，則不只是康托爾式的而且是強康托爾式的。

下面是關於最大序數的布拉利-福爾蒂悖論。我們定義(跟從樸素集合論)序數是良序排序在相似性下的等價類。在序數上有一個明顯的自然的良序排序；因為它是良序排序所以它屬於一個序數${\displaystyle \Omega \ }$。(通過超限歸納法)可直接證明在小於一個給定序數${\displaystyle \alpha \ }$的序數們上的自然次序的序類型是${\displaystyle \alpha \ }$自身。但是這意味着${\displaystyle \Omega \ }$是小於${\displaystyle \Omega \ }$的序數們的序類型，因此它嚴格小於所有序數的序類型 -- 但是通過定義，後者是${\displaystyle \Omega \ }$自身！

在NF(U)中對這個悖論的解決開始於觀察到在小於${\displaystyle \alpha \ }$的序數們上的自然次序的序類型的類型比${\displaystyle \alpha \ }$的類型高。因此類型齊平有序對的類型比它的參數的類型高1，而常規的Kuratowski有序對高3。對於任何序類型${\displaystyle \alpha \ }$，我們可以定義比${\displaystyle \alpha \ }$的類型高1的序類型：如果${\displaystyle W\in \alpha \ }$，則${\displaystyle T(\alpha )\ }$是次序${\displaystyle W^{\iota }=\{(\{x\},\{y\})\mid xWy\}}$的序類型。T運算的煩瑣只是外觀上的；可以輕易的證明T是在序數們上的嚴格的單調(序保持)運算。

我們可以用層化的方式重申關於序類型的引理：在小於${\displaystyle \alpha \ }$的序數們上的自然次序的序類型是${\displaystyle T^{2}(\alpha )\ }$或${\displaystyle T^{4}(\alpha )\ }$，依賴於使用哪個有序對定義(我們在下文中假定類型齊平有序對)。從此我們可演繹出在小於${\displaystyle \Omega \ }$的序數們上的序類型是${\displaystyle T^{2}(\Omega )\ }$，從它我們演繹出${\displaystyle T^{2}(\Omega )<\Omega \ }$。因此T運算不是個函數；我們不能有從序數到序數的嚴格單調集合映射，它向下映射一個序數！因為T是單調的，我們有${\displaystyle \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. （頁面存檔備份，存於互聯網檔案館）