View source for User:RJGray/Sandboxcantor5

==History==
[[File:NBG Evolution svg.svg|thumb|400px|History of approaches that led to NBG set theory]]
=== Von Neumann's 1925 axiom system ===
Von Neumann published an introductory article on his axiom system in 1925. In 1928, he provided a detailed treatment of his system.<ref>{{harvnb|von Neumann|1925}}, {{harvnb|von Neumann|1928}}.</ref> Von Neumann based his axiom system on two domains of [[Primitive notion|primitive]] objects: functions and arguments. These domains overlap—objects that are in both domains are called argument-functions. Functions correspond to classes in NBG, and argument-functions correspond to sets. Von Neumann's primitive operation is [[function application]], denoted by [''a'',&nbsp;''x''] rather than ''a''(''x'') where ''a'' is a function and ''x'' is an argument. This operation produces an argument. Von Neumann defined classes and sets using functions and argument-functions that take only two values, ''A'' and ''B''. He defined ''x''&nbsp;∈&nbsp;''a'' if [''a'',&nbsp;''x'']&nbsp;≠&nbsp;''A''.<ref name=VN1925def />

Von Neumann's work in set theory was influenced by [[Georg Cantor]]'s articles, [[Zermelo set theory|Ernst Zermelo's 1908 axioms for set theory]], and the 1922 critiques of [[Ernst Zermelo|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 {''Z''<sub>0</sub>,&nbsp;''Z''<sub>1</sub>,&nbsp;''Z''<sub>2</sub>,&nbsp;...} where ''Z''<sub>0</sub> is the set of [[natural number]]s and ''Z''<sub>''n''+1</sub> is the [[power set]] of ''Z''<sub>''n''</sub>. They then introduced the axiom of replacement, which would guarantee the existence of such sets.<ref>{{harvnb|Ferreirós|2007|p=369}}. In 1917, [[Dmitry Mirimanoff]] published a form of replacement based on cardinal equivalence {{harv|Mirimanoff|1917|p=49}}.</ref> However, they were reluctant to adopt this axiom: Fraenkel stated "that Replacement was too strong an axiom for 'general set theory'", while "Skolem only wrote that 'we could introduce' Replacement".<ref>{{harvnb|Kanamori|2012|p=62}}.</ref>

Von Neumann worked on the problems of [[Zermelo set theory]] and provided solutions for some of them:
* '''A theory of ordinals''' 
** Problem: Cantor's theory of [[ordinal number]]s cannot be developed in Zermelo set theory because it lacks the axiom of replacement.{{efn|name=ordinaltheorem|In 1928, von Neumann stated: "A treatment of ordinal number closely related to mine was known to Zermelo in 1916, as I learned subsequently from a personal communication. Nevertheless, the fundamental theorem, according to which to each well-ordered set there is a similar ordinal, could not be rigorously proved because the replacement axiom was unknown." {{harv|Hallett|1984|p=280.}}}} 
** Solution: Von Neumann recovered Cantor's theory by defining the ordinals using sets that are [[well-ordered]] by the ∈-relation,{{efn|{{harvnb|von Neumann|1923}}. Von Neumann's definition also used the theory of well-ordered sets. Later, his definition was simplified to the current one: An ordinal is a [[transitive set]] that is well-ordered by ∈ {{harv|Kunen|1980|p=16}}.}} and by using the axiom of replacement to prove key theorems about the ordinals, such as every well-ordered set is [[order-isomorphic]] with an ordinal.{{efn|name=ordinaltheorem}} In contrast to Fraenkel and Skolem, von Neumann emphasized how important the replacement axiom is for set theory: "In fact, I believe that no theory of ordinals is possible at all without this axiom."<ref>{{harvnb|von Neumann|1925|p=223}} (footnote); English translation: {{Harvnb|van&nbsp;Heijenoort|2002b|p=398 (footnote)}}.</ref>
* '''A criterion identifying classes that are too large to be sets''' 
** Problem: Zermelo did not provide such a criterion. His set theory avoids the large classes that lead to the [[Georg Cantor#Absolute infinite, well-ordering theorem, and paradoxes|paradoxes]], but it leaves out many sets, such as the one mentioned by Fraenkel and Skolem.{{efn|After introducing the [[cumulative hierarchy]], von Neumann could show that Zermelo's axioms do not prove the existence of ordinals α&nbsp;≥&nbsp;ω&nbsp;+&nbsp;ω, which include uncountably many [[hereditarily countable set]]s. This follows from Skolem's result that V<sub>ω+ω</sub> satisfies Zermelo's axioms {{harv|Kanamori|2012|p=61}} and from α&nbsp;∈&nbsp;V<sub>β</sub> implying α&nbsp;<&nbsp;β {{harv|Kunen|1980|pp=95&ndash;96}}. Kunen uses the notation R(β) instead of ''V''<sub>β</sub>.}} 
** Solution: Von Neumann introduced the criterion: A class is too large to be a set if and only if it can be mapped [[onto]] the class ''V'' of all sets. Von Neumann realized that the set-theoretic paradoxes could be avoided by not allowing such large classes to be members of any class. Combining this restriction with his criterion, he obtained his [[axiom of limitation of size]]: A class ''C'' is not a member of any class if and only if ''C'' can be mapped onto ''V''.<ref>{{harvnb|Hallett|1984|pp=288&ndash;290}}. Von Neumann stated his axiom in an equivalent functional form ({{harvnb|von Neumann|1925|p=225}}; English translation: {{Harvnb|van&nbsp;Heijenoort|2002b|p=400}}).</ref>
* '''Finite axiomatization''' 
** Problem: Zermelo had used the imprecise concept of "definite [[propositional function]]" in [[Zermelo set theory#The axioms of Zermelo set theory|his axiom of separation]].
** Solutions: Skolem introduced the [[axiom schema of separation]] that was later used in ZFC, and Fraenkel introduced an equivalent solution. However, Zermelo rejected both approaches "particularly because they implicitly involve the concept of natural number which, in Zermelo's view, should be based upon set theory."{{efn|Fraenkel, ''Historical Introduction'' in {{harvnb|Bernays|1991|p=13}}. Skolem's approach implicitly involves natural numbers because the formulas of an axiom schema are built using [[structural recursion]], which is a generalization of [[mathematical recursion]] over the natural numbers.}} Von Neumann avoided [[axiom schema]]s by formalizing the concept of "definite propositional function" with his functions, whose construction requires only finitely many axioms. This led to his set theory having finitely many axioms.<ref>{{harvnb|von Neumann|1925|pp=224&ndash;226}}; English translation: {{Harvnb|van&nbsp;Heijenoort|2002b|pp=399&ndash;401}}.</ref> In 1961, [[Richard Montague]] proved that ZFC cannot be finitely axiomatized.<ref>{{harvnb|Montague|1961}}.</ref>
* '''The axiom of regularity''' 
** Problem: Zermelo set theory starts with the empty set and an infinite set, and iterates the axioms of pairing, union, power set, separation, and choice to generate new sets. However, it does not restrict sets to these. For example, it allows sets that are not [[well-founded set|well-founded]], such as a set ''x'' satisfying ''x''&nbsp;∈&nbsp;''x''.<ref>Mirimanoff defined well-founded sets in 1917 {{harv|Mirimanoff|1917|p=41}}.</ref> 
** Solutions: Fraenkel introduced an axiom to exclude these sets. Von Neumann analyzed Fraenkel's axiom and stated that it was not "precisely formulated", but it would approximately say: "Besides the sets ... whose existence is absolutely required by the axioms, there are no further sets."<ref>{{harvnb|von Neumann|1925|pp=230&ndash;232}}; English translation: {{Harvnb|van&nbsp;Heijenoort|2002b|pp=404&ndash;405}}.</ref> Von Neumann proposed the axiom of regularity as a way to exclude non-well-founded sets, but did not include it in his axiom system. In 1930, Zermelo became the first to publish an axiom system that included regularity.{{efn|[[Akihiro Kanamori]] points out that Bernays lectured on his axiom system in 1929-1930 and states that "… he and Zermelo must have arrived at the idea of incorporating Foundation [regularity] almost at the same time." {{harv|Kanamori|2009|pp=53&ndash;54}}. However, Bernays did not publish the part of his axiom system containing regularity until 1941 {{harv|Bernays|1941|p=6}}.}}

=== Von Neumann's 1929 axiom system ===
[[File:JohnvonNeumann-LosAlamos.gif|thumb|upright=0.97|John von Neumann in the 1940s]]

In 1929, von Neumann published an article containing the axioms that would lead to NBG. This article was motivated by his concern about the consistency of the axiom of limitation of size. He stated that this axiom "does a lot, actually too much." Besides implying the axioms of separation and replacement, and the [[well-ordering theorem]], it also implies that any class whose [[cardinality]] is less than that of ''V'' is a set. Von Neumann thought that this last implication went beyond Cantorian set theory and concluded: "We must therefore discuss whether its [the axiom's] consistency is not even more problematic than an axiomatization of set theory that does not go beyond the necessary Cantorian framework."<ref>{{harvnb|von Neumann|1929|p=229}}; {{harvnb|Ferreirós|2007|pp=379&ndash;380}}.</ref>

Von Neumann started his consistency investigation by introducing his 1929 axiom system, which contains all the axioms of his 1925 axiom system except the axiom of limitation of size. He replaced this axiom with two of its consequences, the axiom of replacement and a choice axiom. Von Neumann's choice axiom states: "Every relation ''R'' has a subclass that is a function with the same domain as ''R''."<ref>{{harvnb|Kanamori|2009|pp=49, 53}}.</ref>

Let ''S'' be von Neumann's 1929 axiom system. Von Neumann introduced the axiom system ''S'' + Regularity (which consists of ''S'' and the axiom of regularity) to demonstrate that his 1925 system is [[relative consistency|consistent relative]] to ''S''. He proved:
# If ''S'' is consistent, then ''S'' + Regularity is consistent.
# ''S'' + Regularity implies the axiom of limitation of size. Since this is the only axiom of his 1925 axiom system that ''S'' + Regularity does not have, ''S'' + Regularity implies all the axioms of his 1925 system. 
These results imply: If ''S'' is consistent, then von Neumann's 1925 axiom system is consistent. Proof: If ''S'' is consistent, then ''S'' + Regularity is consistent (result  1). Using [[proof by contradiction]], assume that the 1925 axiom system is inconsistent, or equivalently: the 1925 axiom system implies a contradiction. Since ''S'' + Regularity implies the axioms of the 1925 system (result 2), ''S'' + Regularity also implies a contradiction. However, this contradicts the consistency of ''S'' + Regularity. Therefore, if ''S'' is consistent, then von Neumann's 1925 axiom system is consistent.

Since ''S'' is his 1929 axiom system, von Neumann's 1925 axiom system is consistent relative to his 1929 axiom system, which is closer to Cantorian set theory. The major differences between Cantorian set theory and the 1929 axiom system are classes and von Neumann's choice axiom. The axiom system ''S'' + Regularity was modified by Bernays and Gödel to produce the equivalent NBG axiom system.

=== Bernays' axiom system ===

[[File:PaulBernays 1949 MFO.jpg|right|border|150px|Paul Bernays, 1949]]
[[File:PaulBernays 1949 MFO.jpg|thumb|150px|Paul Bernays, 1949]]
[[File:PaulBernays 1949 MFO.jpg|thumb|100x150px|Paul Bernays, 1949]]
[[File:PaulBernays 1949 MFO.jpg|thumb|upright=1.50|Paul Bernays, 1949]]

In 1929, [[Paul Bernays]] started modifying von Neumann's new axiom system by taking classes and sets as primitives. He published his work in a series of articles appearing from 1937 to 1954.<ref>{{harvnb|Kanamori|2009|pp=48, 58}}.</ref> 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.{{efn|His classes also used "some of the set-theoretic concepts of the [[Ernst Schröder|Schröder]] logic and of ''[[Principia Mathematica]]''" (quotation from Bernays in {{harvnb|Ferreirós|2007|p=380}}).}} Bernays handled sets and classes in a [[Many-sorted first-order logic|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.<ref>{{harvnb|Kanamori|2009|pp=48&ndash;54}}. Bernays' articles are reprinted in {{harvnb|Müller|1976|pp=1&ndash;117}}.</ref>

=== Gödel's axiom system (NBG) ===
[[File:1925 kurt gödel.png|thumb|upright=0.97|Kurt Gödel, 1925]]

In 1931, Bernays sent a letter containing his set theory to [[Kurt Gödel]].<ref>{{harvnb|Kanamori|2009|p=48}}; {{harvnb|Gödel|2003|pp=104&ndash;115}}.</ref> Gödel simplified Bernays' theory by making every set a class, which allowed him to use just one sort and one membership primitive. He also weakened some of Bernays' axioms and replaced von Neumann's choice axiom with the equivalent axiom of global choice.<ref>{{harvnb|Kanamori|2009|p=56}}.</ref>{{efn|Proof that von Neumann's axiom implies global choice: Let <math>R = \{(x, y): x \ne \empty \land y \in x\}.</math> Von Neumann's axiom implies there is a function <math>G \subseteq R</math> such that <math>Dom(G) = Dom(R).</math> The function <math>G</math> is a global choice function since for all nonempty sets <math>x,</math> <math>G(x) \in x.</math> Proof that global choice implies von Neumann's axiom: Let <math>G</math> be a global choice function, and let <math>R</math> be a relation. For <math>x \in Dom(R),</math> let <math>\alpha(x) = \text{least}\,\{\alpha: \exists y[(x, y) \in R \cap V_\alpha]\}</math> where <math>V_\alpha</math> is the set of all sets having [[Rank (set theory)|rank]] less than <math>\alpha.</math> Let <math>z_x = \{y: (x, y) \in R \cap V_{\alpha(x)}\}.</math> Then <math>F = \{(x, G(z_x)): x \in Dom(R)\}</math> is a function that satisfies von Neumann's axiom since <math>F \subseteq R</math> and <math>Dom(F) = Dom(R).</math>}} Gödel used his axioms in his 1940 monograph on the relative consistency of global choice and the generalized continuum hypothesis.<ref>{{harvnb|Kanamori|2009|pp=56&ndash;58}}; {{harvnb|Gödel|1940}}.</ref>

Several reasons have been given for Gödel choosing NBG for his monograph:{{efn|Gödel used von Neumann's 1929 axioms in his 1938 announcement of his relative consistency theorem and stated "A corresponding theorem holds if ''T'' denotes the system of ''Principia mathematica''" {{harv|Gödel|1990|p=26}}. His 1939 sketch of his proof is for Zermelo set theory and ZF {{harv|Gödel|1990|pp=28&ndash;32}}. Proving a theorem in multiple [[formal systems]] was not unusual for Gödel. For example, he proved his [[incompleteness theorem]] for the system of ''Principia mathematica'', but pointed out that it "holds for a wide class of formal systems ..." {{harv|Gödel|1986|p=145}}.}}
* Gödel gave a mathematical reason—NBG's global choice produces a stronger consistency theorem: "This stronger form of the axiom [of choice], if consistent with the other axioms, implies, of course, that a weaker form is also consistent."<ref name=Godelp6 />
* [[Robert Solovay]] conjectured: "My guess is that he [Gödel] wished to avoid a discussion of the technicalities involved in developing the rudiments of [[model theory]] within axiomatic set theory."{{efn|{{harvnb|Gödel|1990|p=13}}. Gödel's consistency proof builds the [[constructible universe]]. To build this in ZF requires some model theory. Gödel built it in NBG without model theory. For Gödel's construction, see {{harvnb|Gödel|1940|pp=35&ndash;46}} or {{harvnb|Cohen|1966|pp=99&ndash;103}}.}}
* [[Kenneth Kunen]] gave a reason for Gödel avoiding this discussion: "There is also a much more combinatorial approach to '''L''' [the [[constructible universe]]], developed by ... [Gödel in his 1940 monograph] in an attempt to explain his work to non-logicians. ... This approach has the merit of removing all vestiges of logic from the treatment of '''L'''."<ref>{{harvnb|Kunen|1980|p=176}}.</ref>
* [[Charles Parsons (philosopher)|Charles Parsons]] provided a philosophical reason for Gödel's choice: "This view [that 'property of set' is a primitive of set theory] may be reflected in Gödel's choice of a theory with class variables as the framework for ... [his monograph]."{{efn|{{harvnb|Gödel|1990|p=108}}, footnote i. The paragraph containing this footnote discusses why Gödel considered "property of set" a primitive of set theory and how it fit into his [[ontology]]. "Property of set" corresponds to the "class" primitive in NBG.}}

Gödel's achievement together with the details of his presentation led to the prominence that NBG would enjoy for the next two decades.<ref>{{harvnb|Kanamori|2009|p=57}}.</ref> In 1963, [[Paul Cohen (mathematician)|Paul Cohen]] proved his [[Independence (mathematical logic)|independence]] proofs for ZF with the help of some tools that Gödel had developed for his relative consistency proofs for NBG.<ref>{{harvnb|Cohen|1963}}.</ref> Later, ZFC became more popular than NBG.  This was caused by several factors, including the extra work required to handle [[Forcing (mathematics)|forcing]] in NBG,{{efn|{{harvnb|Kanamori|2009|p=65}}: "Forcing itself went a considerable distance in downgrading any formal theory of classes because of the added encumbrance of having to specify the classes of generic extensions."}} Cohen's 1966 presentation of forcing, which used ZF,<ref>{{harvnb|Cohen|1966|pp=107&ndash;147}}. Cohen also gave a detailed proof of Gödel's relative consistency theorems using ZF {{harv|Cohen|1966|pp=85&ndash;99}}.</ref> and the proof that NBG is a conservative extension of ZFC.{{efn|In the 1960s, this conservative extension theorem was proved independently by Paul Cohen, [[Saul Kripke]], and Robert Solovay. In his 1966 book, Cohen mentioned this theorem and stated that its proof requires forcing. It was also proved independently by [[Ronald Jensen]] and Ulrich Felgner, who published his proof in 1971. ({{harvnb|Ferreirós|2007|pp=381&ndash;382}}; {{harvnb|Cohen|1966|p=77}}; {{harvnb|Felgner|1971}}.)}}