Von Neumann–Bernays–Gödel set theory: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Updated live from Wikipedia, last check: May 26, 2013 02:20 UTC (50 seconds ago)

From Wikipedia, the free encyclopedia

In the foundations of mathematics, Von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. 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. 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.

1 Ontology
- 1.1 History
2 Axiomatizating NBG
- 2.1 With Class Comprehension schema
- 2.2 Replacing Class Comprehension with finite instances thereof
  - 2.2.1 Mendelson's variant
3 Discussion
- 3.1 Model theory
- 3.2 Category theory
4 See also
5 Notes
6 References
7 External links

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 $a \in s$ is defined if a is a set and s is a class. In other words, $a \in s$ is defined unless a is a proper class. A proper class is very large; NBG even admits of "the class of all sets", the universal class called V. However, NBG does not admit "the class of all classes" (which fails because classes are not "objects" that can be put into classes in NBG) or "the set of all sets" (whose existence cannot be justified with NBG axioms).

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 the class would not be 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:

$\mathrm{Rp}(A,a) := \forall x(x \in A \leftrightarrow x \in a).$

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

The first variant of NBG, by John von Neumann in the 1920s, took functions and not sets, as primitive. In a series of articles published 1937-54, Paul Bernays modified Von Neumann's theory so as to make sets and set membership primitive. Gödel (1940), while investigating the independence of the Continuum hypothesis, further simplified the theory and discovered that it could be finitely axiomatized. Montague (1961) showed that ZFC cannot be finitely axiomatized.

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 " $x \in y$ " should be read "set x is a member of set y," and " $x \in Y$ " as "set x is a member of class Y." Statements of equality may take the form " $x = y$ " or " $X = Y$ ". " $a = A$ " stands for " $\forall x (x \in a \leftrightarrow x \in A)$ " and is an abuse of notation. NBG can also be presented as a one-sorted theory of classes, with sets being those classes that are members of at least one other class.

We first axiomatize NBG using the axiom schema of Class Comprehension. This schema is provably equivalent^[1] 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 NGB can be finitely axiomatized.

With Class Comprehension schema

The following five axioms are identical to their ZFC counterparts:

extensionality: $\forall x (x \in a \leftrightarrow x \in b)\rightarrow a=b.$ : Sets with the same elements are the same set.
pairing: $\forall x \forall y \exist z \forall w [w \in z \leftrightarrow (w = x \or w = y)].$ For any sets x and y, there is a set, ${x, y}$ , whose elements are exactly x and y.

pairing implies that for any set x, the set {x} (the singleton set) exists. Also, given any two sets x and y and the usual set-theoretic definition of the ordered pair, the ordered pair (x,y) exists and is a set. By Class Comprehension, all relations on sets are classes. Moreover, certain kinds class relations are one or more of functions, injections, and bijections from one class to another. pairing is an axiom in Zermelo set theory and a theorem in ZFC.

union: For any set x, there is a set which contains exactly the elements of elements of x.
power set: For any set x, there is a set which contains exactly the subsets of x.
infinity: There exists an inductive set, namely a set x whose members are (i) the empty set; (ii) for every member y of x, $y \cup \{y\}$ is also a member of x.

infinity can be formulated so as to imply the existence of the empty set.^[2]

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:

Extensionality: $\forall x (x \in A \leftrightarrow x \in B)\rightarrow A=B.$ : Classes with the same elements are the same class.
Foundation (Regularity): Each nonempty class is disjoint from one of its elements.

The last two axioms are peculiar to NBG:

Limitation of Size: For any class C, a set x such that x=C exists if and only if there is no bijection between C and the class V of all sets.

From this axiom, due to Von Neumann, Subsets, Replacement, and Global Choice can all be derived. This axiom implies the axiom of global choice because the class of ordinals is not a set; hence there exists a bijection between the ordinals and the universe. If Limitation of Size were weakened to "If the domain of a class function is a set, then the range of that function is likewise a set," then no form of the axiom of choice is an NBG theorem. In this case, any of the usual local forms of Choice may be taken as an added axiom, if desired.

Limitation of Size cannot be found in Mendelson (1997) NGB. In its place, we find the usual axiom of choice for sets, and the following form of the axiom schema of replacement: if the class F is a function whose domain is a set, the range of F is also a set .^[3]

Class Comprehension schema: For any formula $φ$ containing no quantifiers over classes (it may contain class and set parameters), there is a class A such that $\forall x (x \in A \leftrightarrow \phi(x)).$

This axiom asserts that invoking the principle of unrestricted comprehension of naive set theory yields a class rather than a set, thereby banishing the paradoxes of set theory.

Class Comprehension is the only axiom schema of NBG. In the next section, we show how this schema can be replaced by a number of its own instances. Hence NBG can be finitely axiomatized. If the quantified variables in φ(x) range over classes instead of sets, the result is Morse-Kelley set theory, a proper extension of ZFC which cannot be finitely axiomatized.

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 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.

Sets: For any set x, there is a class X such that x=X.

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 $A=\{x \mid \phi\}$ and $B=\{x \mid \psi\}.$ Then $\{x \mid \neg\phi\} = V-A$ and $\{x \mid \phi\wedge \psi\} = A \cap B$ suffice for handling all sentential connectives, because ∧ and ¬ are a functionally complete set of connectives.

Complement: For any class A, the complement $V-A = \{x \mid x \not\in A\}$ is a class.
Intersection: For any classes A and B, the intersection $A \cap B = \{x \mid x \in A \wedge x \in B\}$ is a class.

We now turn to quantification. In order to handle multiple variables, we need the ability to represent relations. Define the ordered pair $(a, b)$ as ${{a},{a, b}},$ as usual. Note that two applications of pairing to a and b assure that (a,b) is indeed a set.

Products: For any classes A and B, the class $A \times B = \{(a,b) \mid a \in A \wedge b \in B\}$ is a class. (In practice, only $V \times A$ is needed.)
Converses: For any class R, the classes:

$\mathit{Conv}1(R) = \{(b,a)\mid (a,b)\in R\}$ and

$\mathit{Conv}2(R) = \{(b,(a,c)) \mid (a,(b,c)) \in R\}$ exist.

Association: For any class R, the classes:

$\mathit{Assoc}1(R) = \{((a,b),c) \mid (a,(b,c)) \in R\}$ and

$\mathit{Assoc}2(R) = \{(d,(a,(b,c))) \mid (d,((a,b),c)) \in R\}$ exist.

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 $(x_1,x_2,\ldots,x_n)$ as $(x_1,(x_2,\ldots,x_n))$ (it is a pair with the first argument as its first projection and the "tail" of the argument list as the second projection). The idea is to apply Assoc1 until the argument to be brought to the front is second, then apply Conv1 or Conv2 as appropriate to bring the second argument to the front, then apply Assoc2 until the effects of the original applications of Assoc1 (which are now behind the moved argument) are corrected.

If $\{(x,y)\mid \phi(x,y)\}$ exists, then the set $\{y \mid \exists x[\phi(x,y)]\}$ is simply the range of the first set, considered as a relation. The universal quantifier can be defined in terms of the existential quantifier and negation.

Ranges: For any class R, the class $\mathit{Rng}(R) = \{y \mid \exists x[(x,y)\in R]\}$ exists.

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:

Membership: The class $[\in] = \{(x,y) \mid x\in y\}$ exists.
Diagonal: The class $[=] = \{(x,y) \mid \,x=y\}$ exists.

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 (1997: 230) 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: $\forall X \exist Y \forall uvw[(u,v,w) \in Y \leftrightarrow (v,w,u) \in X].$

B7: $\forall X \exist Y \forall uvw[(u,v,w) \in Y \leftrightarrow (u,w,v) \in X].$

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 Δ₀ definable subsets of X (see constructible universe). Then:

V_κ is an intended model of ZFC;
Def(V_κ) is an intended model of NBG;
V_κ+1 is an intended model of MK.

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 the category of small categories, 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).

Notes

^ Mendelson (1997), p. 232, Prop. 4.4, proves Class Comprehension equivalent to the axioms B1-B7 shown on p. 230 and described below.
^ Mendelson (1997), p. 239, Ex. 4.22(b).
^ Mendelson (1997), p. 239, axiom R.

References

Adámek, Jiří; Herrlich, Horst, and Strecker, George E (2004) [1990] (PDF). Abstract and Concrete Categories (The Joy of Cats). New York: Wiley & Sons. ISBN 0-471-60922-6. http://katmat.math.uni-bremen.de/acc/.
Bernays, Paul (1991). Axiomatic Set Theory. Dover Publications. ISBN 0-48-666637-9.
Mendelson, Elliott, 1997. An Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall. ISBN 0412808307. Pp. 225–86 contain the classic textbook treatment of NBG, showing how it does what we expect of set theory, by grounding relations, order theory, ordinal numbers, transfinite numbers, etc.
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.
Muller, F. A., 2001, "Sets, classes, and categories," British Journal of the Philosophy of Science 52: 539-73.
Potter, Michael, 2004. Set Theory and Its Philosophy. Oxford Univ. Press.
Pudlak, P., 1998, "The lengths of proofs" in Buss, S., ed., Handbook of Proof Theory. North-Holland: 547-637.
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. 393 - 413

External links

von Neumann-Bernays-Gödel set theory on PlanetMath

Categories: Systems of set theory

The Full Wiki

Search:

More info on Von Neumann–Bernays–Gödel set theory

Related topics