冯·诺伊曼-博内斯-哥德尔集合论

冯·诺伊曼-博内斯-哥德尔集合论(英语: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.