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

维基百科,自由的百科全书
跳转至: 导航搜索

数学基础中,冯·诺伊曼-博内斯-哥德尔集合论von Neumann–Bernays–Gödel Set TheoryNBG)是设计生成同Zermelo-Fraenkel 集合论选择公理一起(ZFC)同样结果的集合论公理系统,但只有有限数目的公理,即是不使用公理模式

NBG首先由冯·诺伊曼在1920年代提出,從1937年开始由保罗·博内斯英语Paul Bernays作修改,在1940年由哥德尔进一步简化。

不像ZFC,NBG只有有限多个公理。Richard Montague在1961年证明,不可能找到在逻辑上等价于ZFC的有限数目的公理;因此NBG的语言有能力谈论真类同谈论集合一样,并且关于集合的陈述在NBG中是可证明的,当且仅当它在ZFC中是可证明的(就是说NBG是ZFC的保守扩展)。

理论[编辑]

这个理论的标志特征是集合的區分。类可以非常大——实际上你可以谈论“所有集合的类”。但是有一个结构性限制以避免“所有类的类”或“所有集合的集合”這樣的描述。

成员关系

a \in s

只定义在 a 是集合而 s 是集合或类的条件下。

类的構建反映了朴素集合论的構建過程。由於給出了抽象原理,因此從任何带有成员关系的谓词邏輯的陈述,都可以形成相應的类。等於、序对、子类等等的概念都變成定义而不是公理的事情——這些定义都是從公式而來的抽象。

集合的構建跟ZF裡的處理很相似。有一个谓词“Rp”定义如下:

\mathrm{Rp}(A,a) := \forall x(x \in A \iff x \in a)

就是说,一个集合 a 表示(represent)一个类 A,如果 a 的所有元素都是 A 的元素,反之亦然。有些类没有表示,比如不包含自身的所有集合的类。这样的类叫做真类

这种系统的优点是它搭建出一個框架,以允許談論“大对象”,而不會有涉及悖論的顧慮。比如,在范畴论的某些構建中,若然在一個範疇裡,对象的搜集和态射的搜集可以被表示为真类,那這范畴便稱為大範疇。在另一方面,如果一個範疇的对象和态射能“裝進”集合,就稱之為小範疇。因此我们可以容易的谈论“所有小范畴的范畴”而不會衍生問題。当然,這樣得出的會是个大范畴。

NBG的公理化[编辑]

在本节中會展示一个NBG的公理化(实际上有两个不同的公理化,第二个是第一个的改進)。可以把它跟Morse-Kelley集合论的公理化比較一下。

我們把NBG看作有两种类別(two-sorted)的理论,小写字母充当集合变量而大写字母充当类变量。成员关系的陈述需要是如下形式之一: x \in yx \in Y,而等式的陈述需要是如下形式之一 x=yX=Y。通过符号滥用英语Abuse of notation,我们把 (\forall x.x \in a \leftrightarrow x \in A) 写为 a=A

这个理论也可以被表达为单一类別(one-sorted)的理论,通过如下定义来区分集合和类:一个类是集合,如果它是另一个类的元素。

公理如下,不带类字样的公理是关于集合的。

  • 类外延性公理:(\forall x.x \in A \leftrightarrow x \in B)\rightarrow A=B:有相同元素的类是相同的。
  • 外延性公理:(\forall x.x \in a \leftrightarrow x \in b)\rightarrow a=b:有相同元素的集合是相同的。
  • 类概括公理(模式):如果公式 \phi 不包含修飾類的量詞(但\phi還是可以包含类和集合参数),則存在一个對應的类 A使得对于所有 xx \in A \leftrightarrow \phi

在樸素集合論裡,使用非限定的公式構成集合,是產生悖論的原因。在NBG系統裡,限定了概括公理的適用情況,並藉此有加以限制的公式構成一個類,從而避免了樸素集合論的悖論。

若把這個公理模式強化,允許量詞修飾類,這樣它就不再是有限可公理化的,可由另一個理论叫做 Morse-Kelley 集合论來描述。

  • 配对公理对于任何集合 xy,有一个集合 \{x,y\},它的元素精确的是 xy

注意这个公理允许有序对的定义,并与类概括一起,允许把在集合上的关系適用於類的情況(對於特定的类关系,也可以使用函数、单射或双射的術語了,只不過是「由類到類」而不是「由集合到集合」)。

  • 大小限制公理对于任何类 C,存在一个集合 x 使得 Rp(C,x) (謂 xC 的表示,即 Cx 所包含的元素一樣),当且仅当没有在 C 和所有集合的类 V 之间的双射。

这个公理贡献自冯·诺伊曼,并一下实现了分离公理、替代公理和全局选择公理。如果需要的话,它可以被弱化为“若类函数的定义域被包含在一个集合中,則其值域亦為集合”;这将去除选择公理(如果需要可以把它替代为更加有用的局部形式的选择公理)。完全的大小限制公理蕴涵了全局选择公理,因为序数的类不是集合,所以有从序数到全集的双射。

  • 并集公理:对于任何集合 x,有一个集合精确的包含 x 的元素的元素。
  • 幂集公理:对于任何集合 x,有一个集合精确的包含 x 的子集。
  • 无穷公理:存在一个集合 y,空集是 y 的元素,且對每個 y 的元素 aa \cup \{a\} 也是 y 的元素。
  • 类基础(正规)公理:若類 A 不是空類,則存在類 A 的元素 x,使得 xA 不具有共同元素(可以理解為不相交)。

與类概括公理(模式)等價的一組公理[编辑]

我們可以用幾個公理來取代 NBG 的类概括公理模式。 我們將用以下的公理作為例子,但不保证它跟正規的方法一樣。

  • 集合公理:对于任何集合 x,有一个类 X 使得 x=X

这个公理给予我们某些东西作為起始(结合上第一个公理化中的关于集合存在的那些公理),并且使我們可以处理在公式中的集合参数(parameter)。

注意如果 A=\{x \mid \phi\}B=\{x \mid \psi\},则 \{x \mid \neg\phi\} = V-A\{x \mid \phi\wedge \psi\} = A \cap B。這些已經足够处理所有命题连结词。

  • 补类公理:对于任何类 A,补集 V-A = \{x \mid x \not\in A\} 是类。
  • 交类公理:对于任何类 AB,交集 A \cap B = \{x \mid x \in A \wedge x \in B\} 是类。

现在我们需要处理量化。为了处理多个变量,我们需要能够表示关系。有序对 (a,b) 被定义为平常的 \{\{a\},\{a,b\}\}(我们假定了其他 NBG 公理所以有配对)。

  • 积类公理:对于任何类 AB,类 A \times B = \{(a,b) \mid a \in A \wedge b \in B\} 是类(V \times A 实际上就是我们所需要的全部)。
  • 类逆转公理:对于任何类 R, 类 Conv1(R) = \{(b,a)\mid (a,b)\in R\}Conv2(R) = \{(b,(a,c)) \mid (a,(b,c)) \in R\} 存在。
  • 类结合公理:对于任何类 R,类 Assoc1(R) = \{((a,b),c)) \mid (a,(b,c)) \in R\}Assoc2(R) = \{(d,(a,(b,c))) \mid (d,((a,b),c))) \in R\} 存在。

通过这些公理,我们可以自由的增加啞變元(dummy argument)并在任意元数关系中重排變元的次序。看起來有點奇特的结合公理,它正是設計用來作調動,使得我們可以把任一變元提到列表前面(加上逆转公理的辅助)。我们把變元的列表 (x_1,x_2,\ldots,x_n) 表示为 (x_1,(x_2,\ldots,x_n))(它是第一个變元作为它的第一个投影,而列表的“尾部”作为它的第二个投影的有序对)。想法是一直应用 Assoc1 ,直到这个要提到前面的變元位於第二個投影,接着適當地应用 Conv1 或 Conv2 ,把第二个變元提到前面,接着应用 Assoc2 直到最初 Assoc1 一系列應用的效果(现在在被移动的變元之後)被改正。

现在我们观察到如果 \{(x,y)\mid \phi(x,y)\} 存在,则集合 \{y \mid (\exists x.\phi(x,y))\} 按关系考慮的話,就單純是第一个集合的值域。全称量词可以通過存在量词和否定来定义。

  • 类值域公理:对于任何类 R,类 Rng(R) = \{y \mid (\exists x.(x,y)\in R)\} 存在。可以使用前面的公理重排變元,把任何单一變元提到變元列表的前面来被量化。

现在我们需要专注于由原子公式表达的关系。

  • 类成员公理:[\in] = \{(x,y) \mid x\in y\} 存在。
  • 类对角公理:[=] = \{(x,y) \mid \,x=y\} 存在。

通過对角公理、加入啞變量,以及重排變量,可以構造断言它的参数中任意的两个變量相等這樣的关系;這可以被用来处理重复的变量。

引用[编辑]

  • Bernays, Paul. Axiomatic Set Theory. Dover Publications. 1991. ISBN 0-486-66637-9. 
  • 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.