馮·諾伊曼-博內斯-哥德爾集合論

馮·諾伊曼-博內斯-哥德爾集合論(英語:von Neumann–Bernays–Gödel Set TheoryNBG)是種以為直觀動機的一階公理化集合論,它是配上選擇公理策梅洛-法蘭克爾集合論(英語:Zermelo-Fraenkel Set Theory with the axiom of ChoiceZFC)的保守擴展ZFC裡可以證明的定理也都是NBG的定理)[1],而且NBG僅需在一階邏輯基本的公理模式上添加有限數目的公理,但ZFC需添加與集合有關的公理模式[2]

NBG首先由馮·諾伊曼在1920年代提出,從1937年開始由保羅·博內斯英語Paul Bernays作修改,在1940年由哥德爾進一步簡化。

基本符號

編輯

NBG下,「屬於關係」以一個雙元斷言符號   來表示,   通常簡記為   ,並被直觀理解成「x屬於y」;類似地,   的否定   通稱被簡記為   ,並被直觀理解為「x不屬於y」。

以下都把   簡寫為普通的  

本條目定理的證明會頻繁引用一階邏輯的定理,定理的代號可以參見一階邏輯#常用的推理性質一節。

類與集合

編輯

「類」這個名詞在公理化集合論出現之前,通常被理解為「以集合元素的集合。」或是集合(如等價類)。

NBG所談及的一切對象(變數和都是類。而所謂的集合,是屬於某個類的類,也就是說以下的合式公式  來自德語的"集合"「Menge」)式

 

可直觀理解為「x是集合」,特別注意到,為了避免跟其他合式公式的變數產生混淆,   必須是展開   時首次出現的變數。反之合式公式

 

可稱為「  真類proper class)」。

子類

編輯

直觀上「x包含於y」意為「所有x的元素a都會屬於y」,以此為動機,NBG有以下的符號簡寫

 

以上可稱為「x包含於y」或「x是y的子類subclass)」;在    成立的前提下(也就是「x和y都是集合」),可稱為「x是y的子集subset)」。

與集合相關的量詞簡寫

編輯

仿造量詞的簡寫,對於任意變數   與合式公式   ,可作如下的符號定義

  (對所有    是集合則  
  (存在   不但是集合且  

也有書籍以小寫字母來表示被量化的集合變數[3],但考慮到一般的非邏輯數學書籍都將大小寫的差異挪作他用,為避免混淆本條目採用以上的上標表示法。

等號公理

編輯

看待等號的不同方式

編輯

直觀上,兩個集合相等意為「x的元素就是y的元素」,也就是樸素集合論外延公理,換句話說,可用以下的嚴謹合式公式重寫為

 

但一階邏輯的等號可以視為單獨的斷言符號,也可以視為一條複合的合式公式。具體來說,視為一個新的斷言符號   並簡記為   的話,需在NBG內額外添加以下的公理

  —  

直觀上可理解為「類x的元素就是類y的元素,等價於類x等於類y」。

但視為一條合式公式,則僅需做以下的符號定義

 

不管是何種看待方法,習慣上都會把   簡記成   (直觀上的「不相等」)。

等號的良置

編輯

為了確保   的確符合直觀上對等號的要求,還需添加以下的公理

  —  

直觀上,這個公理確保「x等於y,則x屬於z等同於y屬於z」。

這樣,以下的元定理就確保了如此定義的等號是「成功的」。

元定理 — NBG是帶相等符號  一階邏輯理論

證明
以下的證明會逐條檢驗等式定理一節所條列的定義

(E1):

  展開來是(或等價於)

 

那考慮到恆等關係(AND)

 

那再套用(GEN),就會有

 

所以(E1)得證。

(E2):

因為目前的NBG理論內沒有任何函數符號,所以對變數   來說,NBG原子公式只有    兩種可能,這樣的話,(E2)等同於要求以下兩式是NBG的定理

(1)  
(2)  

但依據量詞公理(A4),(1)可從本節一開始添加的公理(T)所推出;類似地,把   視為斷言符號時,(2)都可以從(T')配合(A4)推出;若把   視為合式公式的簡寫,(2)也可以用   的定義配上(A4)推出。

(E3):

本條定義要求以下的合式公式為NBG的定理

 

且的交換性

 

對上式使用(AND)(D1)就有

 

再對上面式使用(AND)(D1)又有

 

所以(E3)的確是NBG的定理。

綜上所述,定理得證。 


真子類

編輯

在定義「相等」以後,可以把「相等的類」排除出子類的定義中,換句話說,NBG有以下的符號定義

 

可直觀理解為「x是y的真子類proper subclass),定義為x包含於y且x不等於y」;在    成立的前提下(也就是「x和y都是集合」),可稱為「x是y的真子集proper subset)」。

外延定理

編輯

為以下的定理可直觀理解為「x等於y等價於,對所有集合z,z屬於x等價於z屬於y」,也就是說,等於的定義可以「限縮」成元素為集合的狀況。

外延定理 —  

證明

以下取一個不曾出現的變數   來展開  

( ) 

(1)  (Hyp)
(2)  (MP with 1, A4)
(3)  (MP with 2, A1)
(4)  (GEN with 3)

( ) 

 
(1)  (Hyp)
(2)  (MP with A4, 1)
(3)  (MP with T, 2)
(4)   (D1, with A4, 3)
(5)  (MP with T, 4)
(6)  (GEN with 5)
(7)  (MP with A4, 6)
(8)  (MP with A4, 6)
(9)  (D1 with AND, 7)
(10)  (D1 with AND, 8)
(11)  (MP twice with A2, I, 9)
(12)  (MP twice with A2, I, 10)
(13)  (AND with 11, 12)
(14)  (GEN with 13)

引入新的函數符號前,常需要唯一存在性的證明,而外延定理大大簡化了證明的難度。

特定條件下的存在性

編輯

以下關於一階邏輯的一般性定理,也大大簡化了 NBG 引入新公理的過程所需的證明

(DC, Definition under certain condition) —  合式公式   完全不自由且  常數符號。若

  

則有

 

證明

(1)  (Hyp)

(2)  (Hyp)

(3)  (MP with A4, 2)

(4)  (MP with 3, DIS)

(5)  (MP with AND,4)

(6)  (MP with AND, 4)

(7)  (MP with DIS, DN 5)

(8)  (MP with DIS, DN, 5)

(9)  (MP with T, 8)

(10)  (GENe with 9)

(11)  (MP with T, 11)

(12)  (A3' with 1, 11)

(13)  (MP with 7, 12)

(14)  (GEN with 13)

再套用一次(DN)也就是

 

但由一階邏輯的等式性質

 

對上式以變數   套用一次(GENe)有

 

所以由(C2)本定理就會得證。 

空集合公理

編輯

  —  

這個公理的直觀意思是「存在集合x,使的所有集合y都不屬於x」。

事實上這個公理還確保了空集的唯一性,嚴格來說,它確保了:

定理 —  

證明

假設

 
 

那根據量詞公理的(A4)有

 
 

另一方面,根據常用的推理性質的(M0)有

 
 

這樣根據演繹定理的推論(D1)有

 
 

這樣根據常用的推理性質(T)有

 
 

這樣根據德摩根定律邏輯與的(DisJ)有

 

這樣再根據(T)有

 

這樣根據普遍化

 

那這樣根據上節的外延定理

 

換句話說

 

這樣根據邏輯與的直觀性質和(D1)有

 

這樣根據普遍化

 

再綜合本節的空集合公理(N),本定理就得証了。 

也就是直觀上,「空集是唯一存在的」,這樣根據函數符號與唯一性一節,可以在NBG加入新的常數符號   和以下的新公理(嚴格來說,把完全沒有函數符號和常數符號的NBG擴展成有   的新NBG,但兩個理論是等效的)

  —  

這個新公理直觀上以「 為集合,且任意集合y都不屬於 」,把   定義成了空集的表示符號。

配對公理

編輯

  —  

這個公理的直觀意思是「對所有集合x和集合y,存在一個僅以x跟y為元素的集合p」。

這個公理還確保了以下的唯一性:

定理(P-1) —  

證明

根據量詞的簡寫,配對公理(P)等價於

 

這樣對上式套用兩次量詞公理的(A4)有

 

這樣在有   的前提就有

 

所以

 

另一方面,若假設

 
 

這樣根據邏輯與的直觀性質

 
 

再根據(A4)有

 
 

如果再假設   ,根據MP律

 
 

這樣根據演繹定理的推論(D1)和邏輯與的直觀性質

 

也就是說

 

其中  

因為變數     內完全不自由,對上式套用演繹定理(D)將   移到右方後,再對   套用普遍化會有

 

這樣根據本條目的外延定理

 

那以演繹定理(D)將   移到右方,然後接連對    使用普遍化

 

故本定理得証。 

這樣的話會有

定理 —  

證明
根據(P-1)和本條目的特定條件下的存在性(DC)會有
(P-2) 

 
 
 

那連續套用邏輯與合邏輯或的分配律邏輯與的交換性會有

 

但考慮到邏輯與的直觀性質邏輯與的定義

 
 
 

那根據恆等關係 常用的推理性質(T)有

 
 

所以根據邏輯或的定義來重複使用演繹定理的推論(D1)會有

 

然後從NBG等式定理會有

 

另一方面,根據(P-1)有

 

這樣結合邏輯與的(DisJ)有

 

再對    套用普遍化

 

這樣結合剛剛的(P-2)與邏輯與的直觀性質,本定理就得證了。 

所以根據函數符號與唯一性一節,可以在NBG加入新的雙元函數符號  (簡記為   )和以下的新公理

  — 
 
 

這個新公理的直觀意思是「若x和y為集合,則   就是那個只以x和y為元素的集合;但反之,若x和y不全為集合,則  空集」。

有序對

編輯

 

 

 

 

在不跟括弧產生混淆的情況下,也可以把 記為 

關係

編輯

 

類函數

編輯

 

類函數跟普通函數的差別在於普通函數是個集合

類的存在公理

編輯

屬於類公理

編輯

  —  

交類公理

編輯

  —  

補類公理

編輯

  —  

定義域公理

編輯

  —  

積類公理

編輯

  —  

置換類公理

編輯

  —  

  —  

類的存在元定理

編輯

這個元定理對應到ZFC爾集合論的分類公理

首先需要遞歸地定義「可敘述公式」(predicative well-formed formula):

  • 對任意變數     為可敘述公式。
  •    為可敘述公式,   為任意變數,則     都是可敘述公式。

這樣依據上列諸類存在公理,就有以下元定理:

類的存在元定理 — 
  為一條只內含變數   的可敘述公式,則有

 
證明

集合的公理

編輯

併集公理

編輯

  —  

冪集公理

編輯

  —  

子集公理

編輯

  —  

無窮公理

編輯

  —  

取代公理及其替代

編輯

  —  

直觀意義為「  為類函數則對任意集合   ,存在一個集合   ,正好就是在   的規則下映射出的」。

大小限制公理

編輯
  • 對於任何類 C,存在一個集合 x 使得   (謂 xC 的表示,即 Cx 所包含的元素一樣),若且唯若沒有在 C 和所有集合的類 V 之間的雙射。

這個公理貢獻自馮·諾伊曼,並一下實現了分離公理、替代公理和全局選擇公理。他效力相當於原始的替代公理加上這選擇公理。完全的大小限制公理蘊涵了全局選擇公理,因為序數的類不是集合,所以有從序數到全集的雙射。

選擇公理

編輯

引用

編輯
  • Bernays, Paul. Axiomatic Set Theory. Dover Publications. 1991. ISBN 978-0-486-66637-2. 
  • John von Neumann, 1925, "An Axiomatization of Set Theory." English translation in Jean van Heijenoort, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard University Press.
  • Mendelson, Elliott, 1997 (1964). An Introduction to Mathematical Logic, 4th ed. Chapman & Hall. The classic textbook treatment of NBG set theory, showing how it can found mathematics.
  • Richard Montague, 1961, "Semantic Closure and Non-Finite Axiomatizability I," in Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, (Warsaw, 2-9 September 1959). Pergamon: 45-69.
  • von Neumann-Bernays-Gödel set theory. PlanetMath. 
  1. ^ Cohen, Paul J. Set Theory and the Continuum Hypothesis. New York: W. A. Benjamin. 1966 [2023-05-15]. (原始內容存檔於2023-05-15). 
  2. ^ Montague, Richard. Semantical Closure and Non-Finite Axiomatizability I. Journal of Symbolic Logic. 1964, 29 (1) [2023-05-15]. doi:10.2307/2269797. (原始內容存檔於2023-05-15). 
  3. ^ Mendelson, Elliott. Introduction to Mathematical Logic (6th Edition). Chapman & Hall. 2015: 233–233. ISBN 9781482237726.