In the foundations of mathematics, von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical Zermelo–Fraenkel set theory (ZFC). This set theory is often referred to by the abbreviation NBG or NGB. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes proper classes, objects having members but that cannot be members of other entities. NBG's principle of class comprehension is predicative; quantified variables in the defining formula can range only over sets. Allowing impredicative comprehension turns NBG into Morse–Kelley set theory (MK). NBG, unlike ZFC and MK, can be finitely axiomatized.
Contents
Ontology
The defining aspect of NBG is the distinction between proper class and set. Let a and s be two individuals. Then the atomic sentence
By NBG's axiom schema of class comprehension, all objects satisfying any given formula in the first-order language of NBG form a class; if a class is not a set in ZFC, it is an NBG proper class.
The development of classes mirrors the development of naive set theory. The principle of abstraction is given, and thus classes can be formed out of all individuals satisfying any statement of first-order logic whose atomic sentences all involve either the membership relation or predicates definable from membership. Equality, pairing, subclass, and such, are all definable and so need not be axiomatized – their definitions denote a particular abstraction of a formula.
Sets are developed in a manner very similarly to ZF. Let Rp(A,a), meaning "the set a represents the class A," denote a binary relation defined as follows:
That is, a "represents" A if every element of a is an element of A, and conversely. Classes lacking representations, such as the class of all sets that do not contain themselves (the class invoked by the Russell paradox), are the proper classes.
History
In two articles published in 1925 and 1928, John von Neumann stated his axioms and showed they were adequate to develop set theory. Von Neumann took functions and arguments as primitives. His functions correspond to classes, and functions that can be used as arguments correspond to sets. In fact, he defined classes and sets using functions that can take only two values (that is, indicator functions whose domain is the class of all arguments).
Von Neumann's work in set theory was influenced by Georg Cantor's articles, Ernst Zermelo's 1908 axioms for set theory, and the 1922 critiques of Zermelo's set theory that were given independently by Abraham Fraenkel and Thoralf Skolem. Both Fraenkel and Skolem pointed out that Zermelo's axioms cannot prove the existence of the set {Z0, Z1, Z2, ... } where Z0 is the set of natural numbers, and Zn+1 is the power set of Zn. They then introduced the axiom of replacement, which would guarantee the existence of such sets. However, they were reluctant to adopt this axiom: Fraenkel's opinion was "that Replacement was too strong an axiom for 'general set theory' ... and ... Skolem only wrote that 'we could introduce' Replacement".
Von Neumann worked on the deficiencies in Zermelo's set theory and introduced several innovations to remedy them, including:
In 1929, von Neumann published his last article on set theory, which contains the axioms that would lead to NGB. Von Neumann wrote that his axiom of limitation of size "does a lot, actually too much." It implies the axioms of separation and replacement, and the well-ordering theorem. It also implies that any class whose cardinality is less than that of
Von Neumann approached this consistency problem by first replacing the axiom of limitation of size with two of its consequences—namely, replacement and the choice axiom: "Every relation R has a subclass which is a function and has the same domain as R. This axiom is equivalent to the axiom of global choice. Next, he proved that if this weaker axiom system is consistent, it remains consistent after adding the axiom of regularity. This produces the axiom system that (after modifications by Bernays and Gödel) would become NBG. Finally, he showed that this axiom system implies the axiom of limitation of size. Therefore, his 1925 axiom system is relatively consistent with an axiom system that is closer to ZFC—the major remaining differences are that this system uses classes and its choice axiom is stronger.
In 1929, Paul Bernays started modifying this axiom system by taking classes and sets as primitives. He published his work in a series of articles appearing from 1937 to 1954. By using sets, Bernays was following the tradition established by Cantor, Richard Dedekind, and Zermelo. His classes followed the tradition of Boolean algebra since they permit the operation of complement as well as union and intersection. Bernays handled sets and classes in a two-sorted logic and introduced two membership primitives: one for membership in sets and one for membership in classes. With these primitives, Bernays rewrote and simplified von Neumann's 1929 axioms.
Kurt Gödel simplified Bernays' theory by making every set a class, which allowed him to use just one sort for classes and one membership primitive. Gödel modified some of Bernays' axioms and replaced von Neumann's choice axiom with the axiom of global choice. He used his axioms in his 1940 monograph on the relative consistency of global choice and the generalized continuum hypothesis.
Several reasons have been given for Gödel choosing NBG for his 1940 monograph:
Gödel's achievement together with the details of his presentation led to the prominence that NBG would enjoy for the next two decades. Even Paul Cohen's 1963 independence proofs for ZF used tools that Gödel developed for his work in NBG. However, in the 1960s, ZFC became more popular than NBG. This was caused by several factors, including the extra work required to handle forcing in NBG, Cohen's 1966 presentation of forcing (which uses techniques that naturally belong to ZF), and the proof that NBG is a conservative extension of ZFC.
Axiomatizating NBG
NBG is presented here as a two-sorted theory, with lower case letters denoting variables ranging over sets, and upper case letters denoting variables ranging over classes. Hence "
We first axiomatize NBG using the axiom schema of Class Comprehension. This schema is provably equivalent to 9 of its finite instances, stated in the following section. Hence these 9 finite axioms can replace Class Comprehension. This is the precise sense in which NBG can be finitely axiomatized.
With Class Comprehension schema
The following five axioms are identical to their ZFC counterparts:
The remaining axioms have capitalized names because they are primarily concerned with classes rather than sets. The next two axioms differ from their ZFC counterparts only in that their quantified variables range over classes, not sets:
The last two axioms are peculiar to NBG:
Replacing Class Comprehension with finite instances thereof
An appealing but somewhat mysterious feature of NBG is that its axiom schema of Class Comprehension is equivalent to the conjunction of a finite number of its instances. The axioms of this section may replace the Axiom Schema of Class Comprehension in the preceding section. The finite axiomatization presented below does not necessarily resemble exactly any NBG axiomatization in print.
We develop our axiomatization by considering the structure of formulas.
This axiom, in combination with the set existence axioms from the previous axiomatization, assures the existence of classes from the outset, and enables formulas with class parameters.
Let
We now turn to quantification. In order to handle multiple variables, we need the ability to represent relations. Define the ordered pair
These axioms license adding dummy arguments, and rearranging the order of arguments, in relations of any arity. The peculiar form of Association is designed exactly to make it possible to bring any term in a list of arguments to the front (with the help of Converses). We represent the argument list
If
The above axioms can reorder the arguments of any relation so as to bring any desired argument to the front of the argument list, where it can be quantified.
Finally, each atomic formula implies the existence of a corresponding class relation:
Diagonal, together with addition of dummy arguments and rearrangement of arguments, can build a relation asserting the equality of any two of its arguments; thus repeated variables can be handled.
Mendelson's variant
Mendelson refers to his axioms B1-B7 of class comprehension as "axioms of class existence." Four of these identical to axioms already stated above: B1 is Membership; B2, Intersection; B3, Complement; B5, Product. B4 is Ranges modified to assert the existence of the domain of R (by existentially quantifying y instead of x). The last two axioms are:
B6:B6 and B7 enable what Converses and Association enable: given any class X of ordered triples, there exists another class Y whose members are the members of X each reordered in the same way.
Discussion
For a discussion of some ontological and other philosophical issues posed by NBG, especially when contrasted with ZFC and MK, see Appendix C of Potter (2004).
Even though NBG is a conservative extension of ZFC, a theorem may have a shorter and more elegant proof in NBG than in ZFC (or vice versa). For a survey of known results of this nature, see Pudlak (1998).
Model theory
ZFC, NBG, and MK have models describable in terms of V, the standard model of ZFC and the von Neumann universe. Now let the members of V include the inaccessible cardinal κ. Also let Def(X) denote the Δ0 definable subsets of X (see constructible universe). Then:
Note that Def(Vκ) is not necessarily a model of NBG, since Limitation of Size might fail; in the other two cases the structures are always models of ZFC and MK, respectively.
Category theory
The ontology of NBG provides scaffolding for speaking about "large objects" without risking paradox. In some developments of category theory, for instance, a "large category" is defined as one whose objects make up a proper class, with the same being true of its morphisms. A "small category", on the other hand, is one whose objects and morphisms are members of some set. We can thus easily speak of the "category of all sets" or "category of all small categories" without risking paradox. Those categories are large, of course. There is no "category of all categories" since it would have to contain large categories which no category can do. Although yet another ontological extension can enable one to talk formally about such a "category" (see for example the "quasicategory of all categories" of Adámek et al. (1990), whose objects and morphisms form a "proper conglomerate").
On whether an ontology including classes as well as sets is adequate for category theory, see Muller (2001).