Editing Von Neumann universe

{{short description|Set theory concept}}
In [[set theory]] and related branches of [[mathematics]], the '''von Neumann universe''', or '''von Neumann hierarchy of sets''', denoted by '''''V''''', is the [[class (set theory)|class]] of [[hereditary set|hereditary]] [[well-founded set]]s. This collection, which is formalized by [[Zermelo–Fraenkel set theory]] (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after [[John von Neumann]], although it was first published by [[Ernst Zermelo]] in 1930.

The '''rank''' of a well-founded set is defined inductively as the smallest [[ordinal number]] greater than the ranks of all members of the set.<ref>{{harvnb|Mirimanoff|1917}}; {{harvnb|Moore|2013|pp=261–262}}; {{harvnb|Rubin|1967|p=214}}.</ref> In particular, the rank of the [[empty set]] is zero, and every ordinal has a rank equal to itself. The sets in ''V'' are divided into the [[Transfinite induction|transfinite]] hierarchy ''V<sub>α</sub>{{space|hair}}'', called '''the cumulative hierarchy''', based on their rank.

== Definition ==

[[Image:Von Neumann Hierarchy.svg|thumb|right|upright=1.4|An initial segment of the von Neumann universe. Ordinal multiplication is reversed from our usual convention; see [[Ordinal arithmetic]].]]

The cumulative hierarchy is a collection of sets ''V''<sub>α</sub>
indexed by the class of [[ordinal number]]s; in particular, ''V''<sub>α</sub> is the set of all sets having ranks less than α. Thus there is one set ''V''<sub>α</sub> for each ordinal number α. ''V''<sub>α</sub> may be defined by [[transfinite recursion]] as follows:

* Let ''V''<sub>0</sub> be the [[empty set]]:<math display="block"> V_0 := \varnothing .</math>
* For any [[ordinal number]] β, let ''V''<sub>β+1</sub> be the [[power set]] of ''V''<sub>β</sub>:<math display="block"> V_{\beta+1} := \mathcal{P} (V_\beta) .</math>
* For any [[limit ordinal]] λ, let ''V''<sub>λ</sub> be the [[union (set theory)|union]] of all the ''V''-stages so far:<math display="block"> V_\lambda := \bigcup_{\beta < \lambda} V_\beta .</math>
A crucial fact about this definition is that there is a single formula φ(α,''x'') in the language of ZFC that states "the set ''x'' is in ''V''<sub>&alpha;</sub>".

The sets  ''V''<sub>α</sub> are called '''stages''' or '''ranks'''.

The class ''V'' is defined to be the union of all the ''V''-stages:

<math display="block"> V := \bigcup_{\alpha} V_\alpha.</math>

===Rank of a set===

The '''rank''' of a set ''S'' is the smallest α such that <math>S \subseteq V_\alpha \,.</math> In other words, <math>\mathcal{P} (V_\alpha) </math> is the set of sets with rank ≤α. The stage ''V''<sub>α</sub> can also be characterized as the set of sets with rank strictly less than α, regardless of whether α is 0, a successor ordinal, or a limit ordinal:

<math display="block">V_\alpha := \bigcup_{\beta < \alpha} \mathcal{P} (V_\beta).</math>

This gives an equivalent definition of ''V''<sub>α</sub> by transfinite recursion.

Substituting the above definition of ''V''<sub>α</sub> back into the definition of the rank of a set gives a self-contained recursive definition:

{{block indent| The rank of a set is the smallest ordinal number strictly greater than the rank of all of its members.}}

In other words,

<math display="block">\operatorname{rank} (S) = \bigcup \{ \operatorname{rank} (z) + 1 \mid z \in S \}.</math>

===Finite and low cardinality stages of the hierarchy===

The first five von Neumann stages ''V''<sub>0</sub> to ''V''<sub>4</sub> may be visualized as follows. (An empty box represents the empty set. A box containing only an empty box represents the set containing only the empty set, and so forth.)

[[File:Von Neumann universe 4.png|upright=3<!--[[WP:IAR]]: 1.8 would be too small-->|frameless|center|First 5 von Neumann stages]]

This sequence exhibits [[tetrational]] growth. The set ''V''<sub>5</sub> contains 2<sup>16</sup> = 65536 elements; the set ''V''<sub>6</sub> contains 2<sup>65536</sup> elements, which very substantially exceeds the [[Observable universe#Matter content—number of atoms|number of atoms in the known universe]]; and for any natural ''n'', the set ''V''<sub>''n''+1</sub> contains 2 ⇈ ''n'' elements using [[Knuth's up-arrow notation]]. So the finite stages of the cumulative hierarchy cannot be written down explicitly after stage 5. The set ''V''<sub>&omega;</sub> has the same cardinality as &omega;. The set ''V''<sub>&omega;+1</sub> has the same cardinality as the set of real numbers.

==Applications and interpretations==

===Applications of ''V'' as models for set theories===
If ω is the set of [[natural number]]s, then ''V''<sub>ω</sub> is the set of [[hereditarily finite set]]s, which is a [[model (logic)|model]] of set theory without the [[axiom of infinity]].<ref>{{harvnb|Roitman|2011|p=136}}, proves that: "''V''<sub>ω</sub> is a model of all of the axioms of ZFC except infinity."</ref><ref>{{harvnb|Cohen|2008|p=54}}, states: "The first really interesting axiom [of ZF set theory] is the Axiom of Infinity. If we drop it, then we can take as a model for ZF the set ''M'' of all finite sets which can be built up from ∅. [...] It is clear that ''M'' will be a model for the other axioms, since none of these lead out of the class of finite sets."</ref>

''V''<sub>ω+ω</sub> is the [[universe (set theory)|universe]] of "ordinary mathematics", and is a model of [[Zermelo set theory]] (but not a model of [[Zermelo–Fraenkel set theory|ZF]]).<ref>{{harvnb|Smullyan|Fitting|2010}}.
See page 96 for proof that ''V''<sub>ω+ω</sub> is a Zermelo model.</ref>  A simple argument in favour of the adequacy of ''V''<sub>ω+ω</sub> is the observation that ''V''<sub>ω+1</sub> is adequate for the integers, while ''V''<sub>ω+2</sub> is adequate for the real numbers, and most other normal mathematics can be built as relations of various kinds from these sets without needing the [[axiom of replacement]] to go outside ''V''<sub>ω+ω</sub>.

If κ is an [[inaccessible cardinal]], then ''V''<sub>κ</sub> is a model of [[Zermelo–Fraenkel set theory]] (ZFC) itself, and ''V''<sub>κ+1</sub> is a model of [[Morse–Kelley set theory]].<ref>{{harvnb|Cohen|2008|p=80}}, states and justifies that if κ is strongly inaccessible, then ''V''<sub>κ</sub> is a model of ZF.
: "It is clear that if A is an inaccessible cardinal, then the set of all sets of rank less than A is a model for ZF, since the only two troublesome axioms, Power Set and Replacement, do not lead out of the set of cardinals less than A."</ref><ref>{{harvnb|Roitman|2011|pp=134–135}}, proves that if κ is strongly inaccessible, then ''V''<sub>κ</sub> is a model of ZFC.</ref> (Note that every ZFC model is also a ZF model, and every ZF model is also a Z model.)

===Interpretation of ''V'' as the "set of all sets"===
V is not "the [[set of all sets|set of all (naive) sets]]" for two reasons. First, it is not a set; although each individual stage ''V''<sub>α</sub> is a set, their union ''V'' is a [[proper class]]. Second, the sets in ''V'' are only the well-founded sets. The [[axiom of foundation]] (or regularity) demands that every set be well founded and hence in ''V'', and thus in ZFC every set is in ''V''. But other axiom systems may omit the axiom of foundation or replace it by a strong negation (an example is [[Aczel's anti-foundation axiom]]). These non-well-founded set theories are not commonly employed, but are still possible to study.

A third objection to the "set of all sets" interpretation is that not all sets are necessarily "pure sets", which are constructed from the empty set using power sets and unions. Zermelo proposed in 1908 the inclusion of [[urelement]]s, from which he constructed a transfinite recursive hierarchy in 1930.<ref name=Zermelo /> Such urelements are used extensively in [[model theory]], particularly in Fraenkel-Mostowski models.<ref name=Howard>{{harvnb|Howard|Rubin|1998|pp=175–221}}.</ref>

===Hilbert's paradox===
The von Neumann universe satisfies the following two properties:

* <math>\mathcal{P}(x) \in V</math> for every ''set'' <math>x \in V</math>.
* <math>\bigcup x \in V</math> for every ''subset'' <math>x \subseteq V</math>.

Indeed, if <math>x \in V</math>, then <math>x \in V_\alpha</math> for some ordinal <math>\alpha</math>.  Any stage is a [[transitive set]], hence every <math>y \in x</math> is already <math>y \in V_\alpha</math>, and so every subset of <math>x</math> is a subset of <math>V_\alpha</math>.  Therefore, <math>\mathcal{P}(x) \subseteq V_{\alpha+1}</math> and <math>\mathcal{P}(x) \in V_{\alpha+2} \subseteq V</math>. For unions of subsets, if <math>x \subseteq V</math>, then for every <math>y \in x</math>, let <math>\beta_y</math> be the smallest ordinal for which <math>y \in V_{\beta_y}</math>.  Because by assumption <math>x</math> is a set, we can form the limit <math>\alpha = \sup \{ \beta_y : y \in x \}</math>.  The stages are cumulative, and therefore again every <math>y \in x</math> is <math>y \in V_\alpha</math>.  Then every <math>z \in y</math> is also <math>z \in V_\alpha</math>, and so <math>\cup x \subseteq V_\alpha</math> and <math>\cup x \in V_{\alpha+1}</math>.

Hilbert's paradox implies that no set with the above properties exists .<ref>A. Kanamori, "[https://math.bu.edu/people/aki/10.pdf Zermelo and Set Theory]", p.490. Bulletin of Symbolic Logic vol. 10, no. 4 (2004). Accessed 21 August 2023.</ref>  For suppose <math>V</math> was a set.  Then <math>V</math> would be a subset of itself, and <math>U = \cup V</math> would belong to <math>V</math>, and so would <math>\mathcal{P}(U)</math>.  But more generally, if <math>A \in B</math>, then <math>A \subseteq \cup B</math>.  Hence, <math>\mathcal{P}(U) \subseteq \cup V = U</math>, which is impossible in models of ZFC such as <math>V</math> itself.

Interestingly, <math>x</math> is a subset of <math>V</math> if, and only if, <math>x</math> is a member of <math>V</math>.  Therefore, we can consider what happens if the union condition is replaced with <math>x \in V \implies \cup x \in V</math>.  In this case, there are no known contradictions, and any [[Grothendieck universe]] satisfies the new pair of properties.  However, whether Grothendieck universes exist is a question beyond ZFC.

===''V'' and the axiom of regularity===
The formula ''V'' = ⋃<sub>α</sub>''V''<sub>α</sub> is often considered to be a theorem, not a definition.<ref name=Bernays /><ref name=Mendelson /> Roitman states (without references) that the realization that the [[axiom of regularity]] is equivalent to the equality of the universe of ZF sets to the cumulative hierarchy is due to von Neumann.<ref name=Roitman>{{harvnb|Roitman|2011}}. See page 79.</ref>

===The existential status of ''V''===

Since the class ''V'' may be considered to be the arena for most of mathematics, it is important to establish that it "exists" in some sense. Since existence is a difficult concept, one typically replaces the existence question with the consistency question, that is, whether the concept is free of contradictions. A major obstacle is posed by [[Gödel's incompleteness theorems]], which effectively imply the impossibility of proving the consistency of ZF set theory in ZF set theory itself, provided that it is in fact consistent.<ref>See article [[On Formally Undecidable Propositions of Principia Mathematica and Related Systems]] and {{harvnb|Gödel|1931}}.</ref>

The integrity of the von Neumann universe depends fundamentally on the integrity of the [[ordinal number]]s, which act as the rank parameter in the construction, and the integrity of [[transfinite induction]], by which both the ordinal numbers and the von Neumann universe are constructed. The integrity of the ordinal number construction may be said to rest upon von Neumann's 1923 and 1928 papers.<ref>{{harvnb|von Neumann|1923}}, {{harvnb|von Neumann|1928b}}. See also the English-language presentation of von Neumann's "general recursion theorem" by {{harvnb|Bernays|1991|pp=100–109}}.</ref> The integrity of the construction of ''V'' by transfinite induction may be said to have then been established in Zermelo's 1930 paper.<ref name=Zermelo />

==History==

The cumulative type hierarchy, also known as the von Neumann universe, is claimed by Gregory H. Moore (1982) to be inaccurately attributed to [[John von Neumann|von Neumann]].<ref name=Moore>{{harvnb|Moore|2013}}. See page 279 for the assertion of the false attribution to von Neumann. See pages 270 and 281 for the attribution to Zermelo.</ref> The first publication of the von Neumann universe was by [[Ernst Zermelo]] in 1930.<ref name=Zermelo>{{harvnb|Zermelo|1930}}. See particularly pages 36–40.</ref>

Existence and uniqueness of the general transfinite recursive definition of sets was demonstrated in 1928 by von Neumann for both Zermelo-Fraenkel set theory<ref>{{harvnb|von Neumann|1928b}}.</ref> and von Neumann's own set theory (which later developed into [[NBG set theory]]).<ref>{{harvnb|von Neumann|1928a}}. See pages 745–752.</ref> In neither of these papers did he apply his transfinite recursive method to construct the universe of all sets. The presentations of the von Neumann universe by Bernays<ref name=Bernays>{{harvnb|Bernays|1991}}. See pages 203–209.</ref> and Mendelson<ref name=Mendelson>{{harvnb|Mendelson|1964}}. See page 202.</ref> both give credit to von Neumann for the transfinite induction construction method, although not for its application to the construction of the universe of ordinary sets.

The notation ''V'' is not a tribute to the name of von Neumann. It was used for the universe of sets in 1889 by Peano, the letter ''V'' signifying "Verum", which he used both as a logical symbol and to denote the class of all individuals.<ref>{{harvnb|Peano|1889}}. See pages VIII and XI.</ref> Peano's notation ''V'' was adopted also by Whitehead and Russell for the class of all sets in 1910.<ref name=Whitehead>{{harvnb|Whitehead|Russell|2009}}. See page 229.</ref> The ''V'' notation (for the class of all sets) was not used by von Neumann in his 1920s papers about ordinal numbers and transfinite induction. Paul Cohen<ref name="Cohen">{{harvnb|Cohen|2008}}. See page 88.</ref> explicitly attributes his use of the letter ''V'' (for the class of all sets) to a 1940 paper by Gödel,<ref name="goedel1940">{{harvnb|Gödel|1940}}.</ref> although Gödel most likely obtained the notation from earlier sources such as Whitehead and Russell.<ref name=Whitehead />

==Philosophical perspectives==

There are two approaches to understanding the relationship of the von Neumann universe V to ZFC (along with many variations of each approach, and shadings between them). Roughly, formalists will tend to view V as something that flows from the ZFC axioms (for example, ZFC proves that every set is in V). On the other hand, realists are more likely to see the von Neumann hierarchy as something directly accessible to the intuition, and the axioms of ZFC as propositions for whose truth in V we can give direct intuitive arguments in natural language. A possible middle position is that the mental picture of the von Neumann hierarchy provides the ZFC axioms with a motivation (so that they are not arbitrary), but does not necessarily describe objects with real existence.{{cn|date=December 2024}}

==See also==
{{div col}}
*[[Universe (mathematics)]]
*[[Constructible universe]]
*[[Grothendieck universe]]
*[[Inaccessible cardinal]]
*[[S (set theory)]]
{{colend}}

==Notes==
{{Reflist}}

== References ==
* {{cite book|last1=Bernays|first1=Paul|author1-link=Paul Bernays|title=Axiomatic Set Theory | publisher=Dover Publications | orig-year=1958 | year=1991 | isbn=0-486-66637-9}}
* {{cite book|last1=Cohen|first1=Paul Joseph|author1-link=Paul Cohen (mathematician)|title=Set theory and the continuum hypothesis|year=2008|orig-year=1966|publisher=Dover Publications|location=Mineola, New York|isbn=978-0-486-46921-8}}
* {{cite journal|last1=Gödel|first1=Kurt|author1-link=Kurt Gödel|year=1931|title=Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I|journal=Monatshefte für Mathematik und Physik|volume=38|pages=173–198|doi=10.1007/BF01700692}}
* {{cite book|last1=Gödel|first1=Kurt|author1-link=Kurt Gödel|title=The consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory|series=Annals of Mathematics Studies|volume=3|publisher= Princeton University Press|place= Princeton, N. J.|year= 1940}}
* {{cite book|last1=Howard|first1=Paul|last2=Rubin|first2=Jean E.|author2-link= Jean E. Rubin |title=Consequences of the axiom of choice|url=https://archive.org/details/consequencesofax0000howa|url-access=registration|year=1998|publisher=American Mathematical Society|location=Providence, Rhode Island|isbn=9780821809778|pages=[https://archive.org/details/consequencesofax0000howa/page/175 175–221]}}
* {{cite book|last1=Jech|first1=Thomas|author1-link=Thomas Jech|year=2003|title=Set Theory: The Third Millennium Edition, Revised and Expanded|publisher=Springer|isbn=3-540-44085-2}}
* {{cite book|last1=Kunen|first1=Kenneth|author1-link=Kenneth Kunen|year=1980|title=Set Theory: An Introduction to Independence Proofs|url=https://archive.org/details/settheoryintrodu0000kune|url-access=registration|publisher=Elsevier|isbn=0-444-86839-9}}
* {{cite book|last=Manin|first=Yuri I.|author-link=Yuri Manin|translator-last=Koblitz|translator-first=N.|translator-link=Neal Koblitz|title=A Course in Mathematical Logic for Mathematicians|year=2010|edition=2nd|orig-year=1977|pages=89–96|series=Graduate Texts in Mathematics|volume=53|publisher=Springer-Verlag|location=New York|isbn=978-144-190-6144|doi=10.1007/978-1-4419-0615-1}}
* {{cite book|last1=Mendelson|first1=Elliott|author1-link=Elliott Mendelson|title=Introduction to Mathematical Logic|year=1964|publisher=Van Nostrand Reinhold}}
* {{cite journal| last1=Mirimanoff | first1=Dmitry |author1-link=Dmitry Mirimanoff|title=Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theorie des ensembles | year=1917 | journal=L'Enseignement Mathématique | volume=19 | pages=37–52}}
* {{cite book|last1=Moore|first1=Gregory H|title=Zermelo's axiom of choice: Its origins, development & influence|orig-year=1982|year=2013|publisher=Dover Publications|isbn=978-0-486-48841-7}}
* {{cite book| first1=Giuseppe | last1=Peano |author1-link=Giuseppe Peano|year=1889 | title=Arithmetices principia: nova methodo exposita|url=https://archive.org/details/arithmeticespri00peangoog|publisher=Fratres Bocca}}
* {{cite book|last1=Roitman|first1=Judith|author1-link=Judith Roitman|title=Introduction to Modern Set Theory|year=2011|orig-year=1990|publisher = [[Virginia Commonwealth University]]|isbn=978-0-9824062-4-3}}
* {{cite book|title=Set Theory for the Mathematician|url=https://archive.org/details/settheoryformath0000rubi|url-access=registration|last1=Rubin|first1=Jean E.|year=1967|publisher=Holden-Day|location=San Francisco|asin=B0006BQH7S}}
* {{cite book
|title=Set Theory and the Continuum Problem
|last1=Smullyan
|first1=Raymond M.
|author1-link=Raymond Smullyan
|last2=Fitting
|first2=Melvin
|author2-link=Melvin Fitting
|publisher=Dover
|year=2010
|orig-year=revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York
|isbn=978-0-486-47484-7
}}
* {{cite journal|last1=von Neumann|first1=John|author1-link=John von Neumann| title = Zur Einführung der transfiniten Zahlen | url = http://bbi-math.narod.ru/newmann/newmann.html | journal = Acta Litt. Acad. Sc. Szeged X. | volume = 1 | pages = 199&ndash;208| year = 1923}}. English translation: {{citation|last=van&nbsp;Heijenoort | first =Jean | year =1967 | publisher = Harvard University Press | title = From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931 | chapter = On the introduction of transfinite numbers | pages = 346&ndash;354}}
* {{cite journal|last1=von Neumann|first1=John|author1-link=John von Neumann|title = Die Axiomatisierung der Mengenlehre | url = http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN266833020_0027&DMDID=DMDLOG_0042 | journal = [[Mathematische Zeitschrift]] | volume = 27 | pages = 669&ndash;752 |date=1928a | doi=10.1007/bf01171122}}
* {{cite journal|last1=von Neumann|first1=John|author1-link=John von Neumann|date=1928b|title=Über die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre | journal=Mathematische Annalen | volume = 99 | pages=373–391 | doi=10.1007/bf01459102}}
* {{Cite book|last1=Whitehead|first1=Alfred North|last2=Russell|first2=Bertrand|author1-link=Alfred North Whitehead|author2-link=Bertrand Russell|year=2009|orig-year=1910|title=Principia Mathematica|volume=One|publisher=Merchant Books|isbn=978-1-60386-182-3}}
* {{cite journal|last1=Zermelo|first1=Ernst|author1-link=Ernst Zermelo|title=Über Grenzzahlen und Mengenbereiche: Neue Untersuchungen über die Grundlagen der Mengenlehre|journal=Fundamenta Mathematicae|volume=16|year=1930|pages=29–47|doi=10.4064/fm-16-1-29-47|doi-access=free}}

{{Set theory}}
{{Mathematical logic}}

[[Category:John von Neumann]]
[[Category:Set-theoretic universes]]