Axiom of limitation of size

In class theories, the axiom of limitation of size says that for any class C, C is a proper class, that is a class which is not a set (an element of other classes), if and only if it can be mapped onto the class V of all sets.^[1]

This axiom is due to John von Neumann. It implies the axiom schema of specification, axiom schema of replacement, axiom of global choice, and even, as noticed later by Azriel Levy, axiom of union^[2] at one stroke. The axiom of limitation of size implies the axiom of global choice because the class of ordinals is not a set, so there is a surjection from the ordinals to the universe, thus an injection from the universe to the ordinals, that is, the universe of sets is well-ordered.

Together the axiom of replacement and the axiom of global choice (with the other axioms of von Neumann–Bernays–Gödel set theory) imply this axiom. This axiom is thus equivalent to the combination of replacement, global choice, specification and union in von Neumann–Bernays–Gödel or Morse–Kelley set theory.

However, the axiom of replacement and the usual axiom of choice (with the other axioms of von Neumann–Bernays–Gödel set theory) do not imply von Neumann's axiom. In 1964, Easton used forcing to build a model that satisfies the axioms of von Neumann–Bernays–Gödel set theory with one exception: the axiom of global choice is replaced by the axiom of choice. In Easton's model, the axiom of limitation of size fails dramatically: the universe of sets cannot even be linearly ordered.^[3]

From this axiom, it can be shown that a class is a proper class if and only if it is equinumerous to V, but von Neumann's axiom does not capture all of the "limitation of size doctrine",^[4] because the axiom of power set is not a consequence of it. Later expositions of class theories (Bernays, Gödel, Kelley, ...) generally use replacement and a form of the axiom of choice rather than the axiom of limitation of size.

Zermelo's models and the axiom of limitation of size

In 1930, Zermelo published an article on models of set theory, in which he proved that some of his models satisfy the axiom of limitation of size. These models are built in ZFC by using the cumulative hierarchy V_α, which is defined by transfinite recursion:

1. V₀ = ∅.^[5]
2. V_α+1 = V_α ∪ P(V_α). That is, the union of V_α and its power set.^[6]
3. For limit β: V_β = ∪_α < β V_α. That is, V_β is the union of the preceding V_α.

Zermelo worked with models of the form V_κ where κ is a cardinal. The classes of the model are the subsets of V_κ, and the model's ∈-relation is the standard ∈-relation. The sets of the model V_κ are the classes X such that X ∈ V_κ.^[7] Zermelo identified cardinals κ such that V_κ satisfies:^[8]

Theorem 1. A class X is a set if and only if | X | < κ.

Theorem 2. | V_κ | = κ.

Since every class is a subset of V_κ, Theorem 2 implies that every class X has cardinality ≤ κ. Combining this with Theorem 1 proves: every proper class has cardinality κ. Hence, every proper class can be put into one-to-one correspondence with V_κ. This correspondence is a subset of V_κ, so it is a class of the model. Therefore, the axiom of limitation of size holds for the model V_κ.

The theorem stating that V_κ has a well-ordering can be proved directly. Since κ is an ordinal of cardinality κ and | V_κ | = κ, there is a one-to-one correspondence between κ and V_κ. This correspondence produces a well-ordering of V_κ. Von Neumann's proof is indirect. It uses the Burali-Forti paradox to prove by contradiction that the class of all ordinals is a proper class. Hence, the axiom of limitation of size implies that there exists a one-to-one correspondence between the class of all ordinals and the class of all sets. This correspondence produces a well-ordering of V_κ.^[9]

The model V_ω

To demonstrate that Theorems 1 and 2 hold for some V_κ, we first prove that if a set belongs to V_α then it belongs to all subsequent V_β, or equivalently: V_α ⊆ V_β for α ≤ β. This is proved by transfinite induction on β:

1. β = 0: V₀ ⊆ V₀.
2. For β+1: By inductive hypothesis, V_α ⊆ V_β. Hence, V_α ⊆ V_β ⊆ V_β ∪ P(V_β) = V_β+1.
3. For limit β: If α < β, then V_α ⊆ ∪_ξ < β V_ξ = V_β. If α = β, then V_α ⊆ V_β.

Sets enter the cumulative hierarchy through the power set P(V_β) at step β+1. The following definitions will be needed:

If x is a set, rank(x) is the least ordinal β such that x ∈ V_β+1.^[10]

The supremum of a set of ordinals A, denoted by sup A, is the least ordinal β such that α ≤ β for all α ∈ A.

Zermelo's smallest model is V_ω. Mathematical induction proves that V_n is finite for all n < ω:

1. | V₀ | = 0.
2. | V_n+1 | = | V_n ∪ P(V_n) | ≤ | V_n | + 2 ^| V_n |, which is finite since V_n is finite by inductive hypothesis.

Proof of Theorem 1: since a set X enters V_ω through P(V_n) for some n < ω, we have X ⊆ V_n. Since V_n is finite, X is finite. Conversely: if a class X is finite, let N = sup {rank(x): x ∈ X}. Since rank(x) ≤ N for all x ∈ X, we have X ⊆ V_N+1, so X ∈ V_N+2 ⊆ V_ω. Therefore, X ∈ V_ω.

Proof of Theorem 2: since V_ω is the union of countably many finite sets, it has cardinality , which equals ω by von Neumann cardinal assignment.

The sets and classes of V_ω satisfy all the axioms of NBG (von Neumann–Bernays–Gödel set theory) except the axiom of infinity.^[11]

The models V_κ where κ is a strongly inaccessible cardinal

Two properties of finiteness were used to prove Theorems 1 and 2 for V_ω:

1. If λ is a finite cardinal, then 2^λ is finite.
2. If A is a set of ordinals such that | A | is finite, and α is finite for all α ∈ A, then sup A is finite.

To find models satisfying the axiom of infinity, replace "finite" by "< κ" to produce the properties that define strongly inaccessible cardinals. A cardinal κ is strongly inaccessible if κ > ω and:

1. If λ is a cardinal such that λ < κ, then 2^λ < κ.
2. If A is a set of ordinals such that | A | < κ, and α < κ for all α ∈ A, then sup A < κ.

These properties assert that κ cannot be reached from below. The first property says κ cannot be reached by power sets; the second says κ cannot be reached by the axiom of replacement.^[12] Just as the axiom of infinity is required to obtain ω, an axiom is needed to obtain strongly inaccessible cardinals. Zermelo postulated the existence of an unbounded sequence of strongly inaccessible cardinals.^[13]

If κ is a strongly inaccessible cardinal, then transfinite induction proves | V_α | < κ for all α < κ:

1. α = 0: | V₀ | = 0.
2. For α+1: | V_α+1 | = | V_α ∪ P(V_α) | ≤ | V_α | + 2 ^| V_α | = 2 ^| V_α | < κ. Last inequality uses inductive hypothesis and κ being strongly inaccessible.
3. For limit α: | V_α | = | ∪_ξ < α V_ξ | ≤ sup {| V_ξ | : ξ < α} < κ. Last inequality uses inductive hypothesis and κ being strongly inaccessible.

Proof of Theorem 1: since a set X enters V_κ through P(V_α) for some α < κ, we have X ⊆ V_α. Since | V_α | < κ, we obtain | X | < κ. Conversely: if a class X has | X | < κ, let β = sup {rank(x): x ∈ X}. Because κ is strongly inaccessible, | X | < κ and rank(x) < κ for all x ∈ X imply β = sup {rank(x): x ∈ X} < κ. Since rank(x) ≤ β for all x ∈ X, we have X ⊆ V_β+1, so X ∈ V_β+2 ⊆ V_κ. Therefore, X ∈ V_κ.

Proof of Theorem 2: | V_κ | = | ∪_α < κ V_α | ≤ sup {| V_α | : α < κ}. Let β be this supremum. Since each ordinal in the supremum is less than κ, we have β ≤ κ. Assume β < κ. Then there is a cardinal λ such that β < λ < κ; for example, let λ = 2^| β |. Since λ ⊆ V_λ and | V_λ | is in the supremum, we have λ ≤ | V_λ | ≤ β. This contradicts β < λ. Therefore, | V_κ | = β = κ.

The sets and classes of V_κ satisfy all the axioms of NBG.^[14]

History

Von Neumann developed the axiom of limitation of size as a new method of identifying sets. ZFC identifies sets via its set building axioms. However, as Abraham Fraenkel pointed out: "The rather arbitrary character of the processes which are chosen in the axioms of Z [ZFC] as the basis of the theory, is justified by the historical development of set-theory rather than by logical arguments."^[15]

The historical development of the ZFC axioms began in 1908 when Zermelo chose axioms to support his proof of the well-ordering theorem and to avoid contradictory sets.^[16] In 1922, Fraenkel and Skolem pointed out that Zermelo's axioms cannot prove the existence of the set {Z₀, Z₁, Z₂, … } where Z₀ is the set of natural numbers, and Z_n+1 is the power set of Z_n.^[17] They also introduced the axiom of replacement, which guarantees the existence of this set.^[18] However, adding axioms as they are needed neither guarantees the existence of all reasonable sets nor clarifies the difference between sets that are safe to use and collections that lead to contradictions.

In a 1923 letter to Zermelo, von Neumann outlined an approach to set theory that identifies the sets that are "too big" (now called proper classes) and that can lead to contradictions.^[19] Von Neumann identified these sets using the criterion: "A set is 'too big' if and only if it is equivalent to the set of all things."^[20] He then restricted how these sets may be used: "… in order to avoid the paradoxes those [sets] which are 'too big' are declared to be impermissible as elements."^[21] By combining this restriction with his criterion, von Neumann obtained the axiom of limitation of size (which in the language of classes states): A class X is not an element of any class if and only if X is equivalent to the class of all sets.^[22] So von Neumann identified sets as classes that are not equivalent to the class of all sets. Von Neumann realized that, even with his new axiom, his set theory does not fully characterize sets.^[23]

Gödel found von Neumann's axiom to be "of great interest":

"In particular I believe that his [von Neumann's] necessary and sufficient condition which a property must satisfy, in order to define a set, is of great interest, because it clarifies the relationship of axiomatic set theory to the paradoxes. That this condition really gets at the essence of things is seen from the fact that it implies the axiom of choice, which formerly stood quite apart from other existential principles. The inferences, bordering on the paradoxes, which are made possible by this way of looking at things, seem to me, not only very elegant, but also very interesting from the logical point of view.^[24] Moreover I believe that only by going farther in this direction, i.e., in the direction opposite to constructivism, will the basic problems of abstract set theory be solved."^[25]

See also

• Axiom of global choice
• Limitation of size
• Von Neumann–Bernays–Gödel set theory
• Morse–Kelley set theory

Notes

1. ↑ This is roughly von Neumann's original formulation, see Fraenkel & al, p. 137.
2. ↑ showing directly that a set of ordinals has an upper bound, see A. Levy, " On von Neumann's axiom system for set theory ", Amer. Math. Monthly, 75 (1968), p. 762-763.
3. ↑ Easton 1964.
4. ↑ Fraenkel & al, p. 137. A guiding principle for ZF to avoid set theoretical paradoxes is to restrict to instances of full (contradictory) comprehension scheme that do not give sets "too much bigger" than the ones they use; it is known as "limitation of size", Fraenkel & al call it "limitation of size doctrine", see p. 32.
5. ↑ This is the standard definition of V₀. Zermelo let V₀ be a set of urelements and proved that if this set contains a single element, the resulting model satisfies the axiom of limitation of size (his proof also works for V₀ = ∅). Zermelo stated that the axiom is not true for all models built from a set of urelements. (Zermelo 1930, p. 38; English translation: p. 1227.)
6. ↑ This is Zermelo's definition (Zermelo 1930, p. 36; English translation: p. 1225). If V₀ = ∅, this definition is equivalent to the standard definition V_α+1 = P(V_α) since V_α ⊆ P(V_α) (Kunen 1980, p. 95; Kunen uses the notation R(α) instead of V_α). If V₀ is a set of urelements, the standard definition eliminates the urelements at V₁.
7. ↑ If X is a set, then there is a class Y such that X ∈ Y. Since Y ⊆ V_κ, we have X ∈ V_κ. Conversely: if X ∈ V_κ, then X belongs to the class V_κ, so X is a set.
8. ↑ These theorems are part of Zermelo's Second Development Theorem. (Zermelo 1930, p. 37; English translation: p. 1226.)
9. ↑ Von Neumann 1925, p. 223. English translation: p. 398. Von Neumann's proof, which only uses axioms, has the advantage of applying to all models rather than just to V_κ.
10. ↑ Kunen 1980, p. 95.
11. ↑ Zermelo proved that V_ω satisfies ZFC without the axiom of infinity. The class existence axioms of NBG (Gödel 1940, p. 5) are true because V_ω is a set when viewed from the set theory that constructs it (namely, ZFC). Therefore, the axiom of specification produces subsets of V_ω that satisfy the class existence axioms.
12. ↑ Zermelo introduced strongly inaccessible cardinals κ so that V_κ would satisfy ZFC. The axioms of power set and replacement led him to the properties of strongly inaccessible cardinals. (Zermelo 1930, p. 31–35; English translation: p. 1221–1224.) Independently, Sierpiński and Tarski introduced these cardinals in 1930. (Sierpiński and Tarski 1930.)
13. ↑ Zermelo used this sequence of cardinals to obtain a sequence of models that explains the paradoxes of set theory — such as, the Burali-Forti paradox and Russell's paradox. He stated that the paradoxes "depend solely on confusing set theory itself … with individual models representing it. What appears as an 'ultrafinite non- or super-set' in one model is, in the succeeding model, a perfectly good, valid set with both a cardinal number and an ordinal type, and is itself a foundation stone for the construction of a new domain [model]." (Zermelo 1930, p. 46–47; English translation: p. 1233.)
14. ↑ Zermelo proved that V_κ satisfies ZFC if κ is a strongly inaccessible cardinal. The class existence axioms of NBG (Gödel 1940, p. 5) are true because V_κ is a set when viewed from the set theory that constructs it (namely, ZFC + there exist infinitely many strongly inaccessible cardinals). Therefore, the axiom of specification produces subsets of V_κ that satisfy the class existence axioms.
15. ↑ Historical Introduction in Bernays 1991, p. 31.
16. ↑ "... we must, on the one hand, restrict these principles [axioms] sufficiently to exclude all contradictions and, on the other hand, take them sufficiently wide to retain all that is valuable in this theory." (Zermelo 1908, p. 261; English translation, p. 200). Gregory Moore analyzed Zermelo's reasons behind his axiomatization and concluded that "his axiomatization was primarily motivated by a desire to secure his demonstration of the Well-Ordering Theorem …" and "For Zermelo, … the paradoxes were an inessential obstacle to be circumvented with as little fuss as possible." (Moore 1982, p. 159–160).
17. ↑ Fraenkel 1922, p. 230–231; Skolem 1922 (English translation, p. 296–297).
18. ↑ Ferreirós 2007, p. 369. In 1917, Mirimanoff published a form of replacement based on cardinal equivalence (Mirimanoff 1917, p. 49).
19. ↑ He gave a detailed exposition of his set theory in two articles: von Neumann 1925 and von Neumann 1928.
20. ↑ Hallett 1984, p. 288.
21. ↑ Hallett 1984, p. 290.
22. ↑ Hallett 1984, p. 290. Von Neumann later changed "equivalent to the class of all sets" to "can be mapped onto the class of all sets."
23. ↑ To be precise, von Neumann investigated whether his set theory is categorical; that is, whether it uniquely determines sets in the sense that any two of its models are isomorphic. He showed that it is not categorical because of a weakness in the axiom of regularity: this axiom only excludes descending ∈-sequences from existing in the model; descending sequences may still exist outside the model. A model having "external" descending sequences is not isomorphic to a model having no such sequences since this latter model lacks isomorphic images for the sets belonging to external descending sequences. This led von Neumann to conclude "that no categorical axiomatization of set theory seems to exist at all" (von Neumann 1925, p. 239; English translation: p. 412).
24. ↑ For example, von Neumann's proof that his axiom implies the well-ordering theorem uses the Burali-Forte paradox (von Neumann 1925, p. 223; English translation: p. 398).
25. ↑ From a Nov. 8, 1957 letter Gödel wrote to Stanislaw Ulam (Kanamori 2003, p. 295).

References

• Bernays, Paul (1991), Axiomatic Set Theory, Dover Publications, ISBN 0-486-66637-9 .
• Easton, William B. (1964), Powers of Regular Cardinals (Ph.D. thesis), Princeton University .
• Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised ed.), Basel, Switzerland: Birkhäuser, ISBN 3-7643-8349-6 .
• Fraenkel, Abraham (1922), "Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre", Mathematische Annalen, 86: 230–237, doi:10.1007/bf01457986 .
• Fraenkel, Abraham; Bar-Hillel, Yehoshua; Levy, Azriel (1973), Foundations of Set Theory (2nd revised ed.), Basel, Switzerland: Elsevier, ISBN 0-7204-2270-1 .
• Gödel, Kurt (1940), The Consistency of the Continuum Hypothesis, Princeton University Press .
• Hallett, Michael (1984), Cantorian Set Theory and Limitation of Size, Oxford: Clarendon Press, ISBN 0-19-853179-6 .
• Kanamori, Akihiro (2003), "Stanislaw Ulam" (PDF), in Solomon Fefermann and John W. Dawson, Jr., Kurt Gödel Collected Works, Volume V: Correspondence H-Z, Clarendon Press, pp. 280–300, ISBN 0-19-850075-0 .
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, North-Holland, ISBN 0-444-86839-9 .
• Mirimanoff, Dmitry (1917), "Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theorie des ensembles", L'Enseignement Mathématique, 19: 37–52 .
• Moore, Gregory H. (1982), Zermelo's Axiom of Choice: Its Origins, Development, and Influence, Springer, ISBN 0-387-90670-3 .
• Sierpiński, Wacław; Tarski, Alfred (1930), "Sur une propriété caractéristique des nombres inaccessibles" (PDF), Fundamenta Mathematicae, 15: 292–300, ISSN 0016-2736 .
• Skolem, Thoralf (1922), "Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre", Matematikerkongressen i Helsingfors den 4-7 Juli, 1922, pp. 217–232 . English translation: van Heijenoort, Jean (1967), "Some remarks on axiomatized set theory", From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, pp. 290–301, ISBN 978-0-674-32449-7 .
• von Neumann, John (1925), "Eine Axiomatisierung der Mengenlehre", Journal für die Reine und Angewandte Mathematik, 154: 219–240 . English translation: van Heijenoort, Jean (1967), "An axiomatization of set theory", From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, pp. 393–413, ISBN 978-0-674-32449-7 .
• von Neumann, John (1928), "Die Axiomatisierung der Mengenlehre", Mathematische Zeitschrift, 27: 669–752, doi:10.1007/bf01171122 .
• Zermelo, Ernst (1930), "Über Grenzzahlen und Mengenbereiche: neue Untersuchungen über die Grundlagen der Mengenlehre" (PDF), Fundamenta Mathematicae, 16: 29–47 . English translation: Ewald, William B. (ed.) (1996), "On boundary numbers and domains of sets: new investigations in the foundations of set theory", From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Oxford University Press, pp. 1208–1233, ISBN 978-0-19-853271-2 .
• Zermelo, Ernst (1908), "Untersuchungen über die Grundlagen der Mengenlehre I", Mathematische Annalen, 65 (2): 261–281, doi:10.1007/bf01449999 . English translation: van Heijenoort, Jean (1967), "Investigations in the foundations of set theory", From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, pp. 199–215, ISBN 978-0-674-32449-7 .