Axiom of limitation of size

The usual version of the axiom of limitation of size—a class is a proper class if and only if there is a function that maps it onto V—is expressed in the formal language of set theory as: :\begin{align} \forall C \Bigl[ \lnot \exist D \left(C \in D\right) \iff \exist F \bigl[&\,\forall y \bigl(\exist D(y \in D) \implies \exist x [\,x \in C \land (x, y) \in F\,]\bigr) \\ &\, \land \, \forall x \forall y \forall z \bigl(\,[\,(x, y) \in F \land (x, z) \in F\,] \implies y = z\bigr)\,\bigr]\,\Bigr] \end{align} Gödel introduced the convention that uppercase variables range over all the classes, while lowercase variables range over all the sets. This convention allows us to write: • \exist y\, \varphi(y) instead of \exist y \bigl(\exist D (y \in D) \land \varphi(y)\bigr) • \forall y\, \varphi(y) instead of \forall y \bigl(\exist D (y \in D) \implies \varphi(y)\bigr) With Gödel's convention, the axiom of limitation of size can be written: :\begin{align} \forall C \Bigl[ \lnot \exist D \left( C \in D\right) \iff \exist F \bigl[&\,\forall y \exist x \bigl( x \in C \land (x, y) \in F \bigr) \\ &\, \land \, \forall x \forall y \forall z \bigl(\,[\,(x, y) \in F \land (x, z) \in F\,] \implies y = z\bigr)\,\bigr]\,\Bigr] \end{align} == Implications of the axiom ==

Von Neumann proved that the axiom of limitation of size implies the axiom of replacement, which can be expressed as: If F is a function and A is a set, then F(A) is a set. This is proved by contradiction. Let F be a function and A be a set. Assume that F(A) is a proper class. Then there is a function G that maps F(A) onto V. Since the composite function G \circ F maps A onto V, the axiom of limitation of size implies that A is a proper class, which contradicts A being a set. Therefore, F(A) is a set. Since the axiom of replacement implies the axiom of separation, the axiom of limitation of size implies the axiom of separation. Von Neumann also proved that his axiom implies that V can be well-ordered. The proof starts by proving by contradiction that Ord, the class of all ordinals, is a proper class. Assume that Ord is a set. Since it is a transitive set that is strictly well-ordered by ∈, it is an ordinal. So Ord ∈ Ord, which contradicts Ord being strictly well-ordered by ∈. Therefore, Ord is a proper class. So von Neumann's axiom implies that there is a function F that maps Ord onto V. To define a well-ordering of V, let G be the subclass of F consisting of the ordered pairs (α, x) where α is the least β such that (β, x) ∈ F; that is, G = {(α, x) ∈ F: ∀β((β, x) ∈ F ⇒ α ≤ β)}. The function G is a one-to-one correspondence between a subclass of Ord and V. Therefore, x −1(x) −1(y) defines a well-ordering of V. This well-ordering defines a global choice function: Let Inf(x) be the least element of a non-empty set x. Since Inf(x) ∈ x, this function chooses an element of x for every non-empty set x. Therefore, Inf(x) is a global choice function, so Von Neumann's axiom implies the axiom of global choice. In 1968, Azriel Lévy proved that von Neumann's axiom implies the axiom of union. First, he proved without using the axiom of union that every set of ordinals has an upper bound. Then he used a function that maps Ord onto V to prove that if A is a set, then ∪A is a set. The axioms of replacement, global choice, and union (with the other axioms of NBG) imply the axiom of limitation of size. Therefore, this axiom is equivalent to the combination of replacement, global choice, and union in NBG or Morse–Kelley set theory. These set theories only substituted the axiom of replacement and a form of the axiom of choice for the axiom of limitation of size because von Neumann's axiom system contains the axiom of union. Lévy's proof that this axiom is redundant came many years later. The axioms of NBG with the axiom of global choice replaced by the usual axiom of choice do not imply the axiom of limitation of size. In 1964, William B. Easton used forcing to build a model of NBG with global choice replaced by the axiom of choice. In Easton's model, V cannot be linearly ordered, so it cannot be well-ordered. Therefore, the axiom of limitation of size fails in this model. Ord is an example of a proper class that cannot be mapped onto V because (as proved above) if there is a function mapping Ord onto V, then V can be well-ordered. The axioms of NBG with the axiom of replacement replaced by the weaker axiom of separation do not imply the axiom of limitation of size. Define \omega_\alpha as the \alpha-th infinite initial ordinal, which is also the cardinal \aleph_\alpha; numbering starts at 0, so \omega_0 = \omega. In 1939, Gödel pointed out that Lωω, a subset of the constructible universe, is a model of ZFC with replacement replaced by separation. To expand it into a model of NBG with replacement replaced by separation, let its classes be the sets of Lωω+1, which are the constructible subsets of Lωω. This model satisfies NBG's class existence axioms because restricting the set variables of these axioms to Lωω produces instances of the axiom of separation, which holds in L.{{efn|An axiom's set variable is restricted on the right side of the "if and only if". Also, an axiom's class variables are converted to set variables. For example, the class existence axiom \forall A \, \exists B \, \forall u \, [u \in B \Leftrightarrow u \notin A)] becomes \forall a \, \exists b \, \forall u \, [u \in b \Leftrightarrow (u \in L_{\omega_\omega} \land u \notin a)]. The class existence axioms are in }} It satisfies the axiom of global choice because there is a function belonging to Lωω+1 that maps ωω onto Lωω, which implies that Lωω is well-ordered.{{efn|Gödel defined a function F that maps the class of ordinals onto L. The function {F|}_{\omega_\omega} (which is the restriction of F to \omega_\omega) maps \omega_\omega onto L_{\omega_\omega}, and it belongs to L_{\omega_{\omega+1}} because it is a constructible subset of L_{\omega_\omega}. Gödel uses the notation F\omega_\alpha for L_{\omega_\alpha}. (.)}} The axiom of limitation of size fails because the proper class {ωn : n'' ∈ ω} has cardinality \aleph_0, so it cannot be mapped onto Lωω, which has cardinality \aleph_\omega.{{efn|Proof by contradiction that \{\omega_n: n \in \omega\} is a proper class: Assume that it is a set. By the axiom of union, \cup\,\{\omega_n: n \in \omega\} is a set. This union equals \omega_\omega, the model's proper class of all ordinals, which contradicts the union being a set. Therefore, \{\omega_n: n \in \omega\} is a proper class. Proof that |L_{\omega_\omega}| = \aleph_\omega\!: The function {F|}_{\omega_\omega} maps \omega_\omega onto L_{\omega_\omega}, so |L_{\omega_\omega}| \le |\omega_\omega|. Also, \omega_\omega \subseteq L_{\omega_\omega} implies |\omega_\omega| \le |L_{\omega_\omega}|. Therefore, |L_{\omega_\omega}| = |\omega_\omega| = \aleph_\omega.}} In a 1923 letter to Zermelo, von Neumann stated the first version of his axiom: A class is a proper class if and only if there is a one-to-one correspondence between it and V. The axiom of limitation of size implies von Neumann's 1923 axiom. Therefore, it also implies that all proper classes are equinumerous with V. {{math proof|title = Proof that the axiom of limitation of size implies von Neumann's 1923 axiom|drop = hidden|proof = To prove the \Longleftarrow direction, let A be a class and F be a one-to-one correspondence from A to V. Since F maps A onto V, the axiom of limitation of size implies that A is a proper class. To prove the \Longrightarrow direction, let A be a proper class. We will define well-ordered classes (A, and (V, and construct order isomorphisms between (Ord, and (V, Then the order isomorphism from (A, to (V, is a one-to-one correspondence between A and V. It was proved above that the axiom of limitation of size implies that there is a function F that maps Ord onto V. Also, G was defined as a subclass of F that is a one-to-one correspondence between Dom(G) and V. It defines a well-ordering on V\colon\, x if G^{-1}(x) Therefore, G is an order isomorphism from (Dom(G), to (V, If (C, is well-ordered class, its proper initial segments are the classes \{x \in C: x where y \in C. Now (Ord, has the property that all of its proper initial segments are sets. Since Dom(G) \subseteq Ord, this property holds for (Dom(G), The order isomorphism G implies that this property holds for (V, Since A \subseteq V, this property holds for (A, To obtain an order isomorphism from (A, to (V, the following theorem is used: If P is a proper class and the proper initial segments of (P, are sets, then there is an order isomorphism from (Ord, to (P, {{efn|This is the first half of theorem 7.7 in . Gödel defines the order isomorphism F: (Ord, by transfinite recursion: F(\alpha) = Inf(A \setminus \{F(\beta): \beta \in \alpha\}).}} Since (A, and (V, satisfy the theorem's hypothesis, there are order isomorphisms I_A\colon (Ord, and I_V\colon (Ord, Therefore, the order isomorphism I_V \circ I_A^{-1}\colon (A, is a one-to-one correspondence between A and V. }} ==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. : Theorem 1. A class X is a set if and only if |X| κ| = κ. 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 is a function that maps the class of all ordinals onto the class of all sets. This function produces a well-ordering of Vκ. 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 β: • β = 0: V0 ⊆ V0. • For β+1: By inductive hypothesis, Vα ⊆ Vβ. Hence, Vα ⊆ Vβ ⊆ Vβ ∪ P(Vβ) = Vβ+1. • For limit β: If α α ⊆ ∪ξ  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. :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 Vn is finite for all n 0| = 0. • |Vn+1| = |Vn ∪ P(Vn)| ≤ |Vn| + 2 |Vn|, which is finite since Vn is finite by inductive hypothesis. Proof of Theorem 1: A set X enters Vω through P(Vn) for some n n. Since Vn 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 ⊆ VN+1, so X ∈ VN+2 ⊆ Vω. Therefore, X ∈ Vω. Proof of Theorem 2: Vω is the union of countably infinitely many finite sets of increasing size. Hence, it has cardinality \aleph_0, which equals ω by von Neumann cardinal assignment. The sets and classes of Vω satisfy all the axioms of NBG except the axiom of infinity. The models Vκ where κ is a strongly inaccessible cardinal Two properties of finiteness were used to prove Theorems 1 and 2 for Vω: • If λ is a finite cardinal, then 2λ is finite. • 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 " ω and: • If λ is a cardinal such that λ λ α| 0| = 0. • For α+1: |Vα+1| = |Vα ∪ P(Vα)| ≤ |Vα| + 2 |Vα| = 2 |Vα| α| = |∪ξ  Vξ| ≤ sup {|Vξ| : ξ κ through P(Vα) for some α α. Since |Vα| β+1, so X ∈ Vβ+2 ⊆ Vκ. Therefore, X ∈ Vκ. Proof of Theorem 2: |Vκ| = |∪α  Vα| ≤ sup {|Vα| : α |β|. Since λ ⊆ Vλ and |Vλ| is in the supremum, we have λ ≤ |Vλ| ≤ β. This contradicts β κ| = β = κ. The sets and classes of Vκ satisfy all the axioms of NBG. == Limitation of size doctrine ==

The limitation of size doctrine is a heuristic principle that is used to justify axioms of set theory. It avoids the set theoretical paradoxes by restricting the full (contradictory) axiom schema of comprehension: :\forall w_1,\ldots,w_n \, \exists x \, \forall u \, ( u \in x \iff \varphi(u, w_1, \ldots, w_n) ) to instances "that do not give sets 'too much bigger' than the ones they use." If "bigger" means "bigger in cardinal size", then most of the axioms can be justified: The axiom of separation produces a subset of x that is not bigger than x. The axiom of replacement produces an image set f(x) that is not bigger than x. The axiom of union produces a union whose size is not bigger than the size of the biggest set in the union times the number of sets in the union. The axiom of choice produces a choice set whose size is not bigger than the size of the given set of nonempty sets. The limitation of size doctrine does not justify the axiom of infinity: :\exists y \, [\empty \in y \, \land \, \forall x (x \in y \implies x \cup \{x\} \in y)], which uses the empty set and sets obtained from the empty set by iterating the ordinal successor operation. Since these sets are finite, any set satisfying this axiom, such as ω, is much bigger than these sets. Fraenkel and Lévy regard the empty set and the infinite set of natural numbers, whose existence is implied by the axioms of infinity and separation, as the starting point for generating sets. Von Neumann's approach to limitation of size uses the axiom of limitation of size. As mentioned in , von Neumann's axiom implies the axioms of separation, replacement, union, and choice. Like Fraenkel and Lévy, von Neumann had to add the axiom of infinity to his system since it cannot be proved from his other axioms. The differences between von Neumann's approach to limitation of size and Fraenkel and Lévy's approach are: • Von Neumann's axiom puts limitation of size into an axiom system, making it possible to prove most set existence axioms. The limitation of size doctrine justifies axioms using informal arguments that are more open to disagreement than a proof. • Von Neumann assumed the power set axiom since it cannot be proved from his other axioms.{{efn|The model whose sets are the elements of L_{\omega_1} and whose classes are the elements of L_{\omega_2} satisfies all of his axioms except for the power set axiom. This axiom fails because all sets are countable.}} Fraenkel and Lévy state that the limitation of size doctrine justifies the power set axiom. There is disagreement on whether the limitation of size doctrine justifies the power set axiom. Michael Hallett has analyzed the arguments given by Fraenkel and Lévy. Some of their arguments measure size by criteria other than cardinal size—for example, Fraenkel introduces "comprehensiveness" and "extendability". Hallett points out what he considers to be flaws in their arguments. Hallett then argues that results in set theory seem to imply that there is no link between the size of an infinite set and the size of its power set. This would imply that the limitation of size doctrine is incapable of justifying the power set axiom because it requires that the power set of x is not "too much bigger" than x. For the case where size is measured by cardinal size, Hallett mentions Paul Cohen's work. Starting with a model of ZFC and \aleph_\alpha, Cohen built a model in which the cardinality of the power set of ω is \aleph_\alpha if the cofinality of \aleph_\alpha is not ω; otherwise, its cardinality is \aleph_{\alpha+1}. Since the cardinality of the power set of ω has no bound, there is no link between the cardinal size of ω and the cardinal size of P(ω). Hallett also discusses the case where size is measured by "comprehensiveness", which considers a collection "too big" if it is of "unbounded comprehension" or "unlimited extent". He points out that for an infinite set, we cannot be sure that we have all its subsets without going through the unlimited extent of the universe. He also quotes John L. Bell and Moshé Machover: "... the power set P(u) of a given [infinite] set u is proportional not only to the size of u but also to the 'richness' of the entire universe ..." After making these observations, Hallett states: "One is led to suspect that there is simply no link between the size (comprehensiveness) of an infinite a and the size of P(a)." He concludes that "von Neumann's explicit assumption [of the smallness of power-sets] seems preferable to Zermelo's, Fraenkel's, and Lévy's obscurely hidden implicit assumption of the smallness of power-sets." ==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." The historical development of the ZFC axioms began in 1908 when Zermelo chose axioms to eliminate the paradoxes and to support his proof of the well-ordering theorem. In 1922, Abraham Fraenkel and Thoralf 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 also introduced the axiom of replacement, which guarantees the existence of this set. 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 sets that are "too big" and might lead to contradictions. Von Neumann identified these sets using the criterion: "A set is 'too big' if and only if it is equivalent with the set of all things." 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." By combining this restriction with his criterion, von Neumann obtained his first version of the axiom of limitation of size, which in the language of classes states: A class is a proper class if and only if it is equinumerous with V. == Notes ==