[proofplan] We prove the statement by [set induction](/page/Set%20Induction), which is available from the [Axiom of Foundation](/page/Axiom%20of%20Foundation). Assuming that every element $y \in x$ already belongs to some level of the [cumulative hierarchy](/page/Cumulative%20Hierarchy), we choose the least such level for each $y$ and collect these ordinals by the [Axiom Schema of Replacement](/page/Axiom%20Schema%20of%20Replacement). The supremum of those ordinals gives a single stage containing every element of $x$, so $x$ itself belongs to the next stage of the hierarchy. [/proofplan] [step:Prove monotonicity of the cumulative hierarchy] We first record the monotonicity property of the hierarchy: if $\beta$ and $\gamma$ are [ordinals](/page/Ordinal) with $\beta \in \gamma$ or $\beta = \gamma$, then $V_\beta \subset V_\gamma$ or $V_\beta = V_\gamma$ respectively in the sense that $V_\beta \subseteq V_\gamma$. [claim:Each stage of the cumulative hierarchy is transitive] For every ordinal $\theta$, if $z \in V_\theta$ and $w \in z$, then $w \in V_\theta$. [/claim] [proof] We prove the claim by [transfinite induction](/page/Transfinite%20Induction) on the ordinal $\theta$. For $\theta = 0$, one has $V_0 = \varnothing$, so there is no $z \in V_0$. Suppose $\theta = \eta + 1$ and assume the claim holds at stage $\eta$. Let $z \in V_{\eta+1}$ and $w \in z$. By the successor-stage definition of the cumulative hierarchy, \begin{align*} V_{\eta+1} = \mathcal{P}(V_\eta). \end{align*} Thus $z \subseteq V_\eta$, and hence $w \in V_\eta$. Also $w \subseteq V_\eta$ follows from the induction hypothesis applied to $w \in V_\eta$, so $w \in \mathcal{P}(V_\eta) = V_{\eta+1}$. Suppose $\theta$ is a nonzero limit ordinal and assume the claim holds for every ordinal $\eta \in \theta$. Let $z \in V_\theta$ and $w \in z$. Since \begin{align*} V_\theta = \bigcup_{\eta \in \theta} V_\eta, \end{align*} there exists an ordinal $\eta \in \theta$ such that $z \in V_\eta$. The induction hypothesis at $\eta$ gives $w \in V_\eta$, and therefore $w \in V_\theta$ because $V_\eta$ is one of the sets in the union defining $V_\theta$. This proves the claim. [/proof] Fix an ordinal $\gamma$. We prove by transfinite induction on $\gamma$ that $V_\beta \subseteq V_\gamma$ for every ordinal $\beta \in \gamma$. If $\gamma = 0$, there is no ordinal $\beta \in 0$, so the assertion is vacuous. If $\gamma = \delta + 1$, let $\beta \in \gamma$. Then either $\beta = \delta$ or $\beta \in \delta$. If $\beta = \delta$, then \begin{align*} V_\gamma = V_{\delta+1} = \mathcal{P}(V_\delta), \end{align*} and every element of $V_\delta$ is a subset of $V_\delta$ because the cumulative hierarchy is transitive at each previous stage; hence $V_\delta \subseteq \mathcal{P}(V_\delta) = V_\gamma$. If $\beta \in \delta$, the induction hypothesis gives $V_\beta \subseteq V_\delta$, and the preceding case gives $V_\delta \subseteq V_\gamma$, so $V_\beta \subseteq V_\gamma$. If $\gamma$ is a nonzero limit ordinal and $\beta \in \gamma$, then by definition \begin{align*} V_\gamma = \bigcup_{\xi \in \gamma} V_\xi. \end{align*} Since $\beta \in \gamma$, every element of $V_\beta$ belongs to this union, so $V_\beta \subseteq V_\gamma$. Thus $V_\beta \subseteq V_\gamma$ whenever $\beta \in \gamma$. The case $\beta = \gamma$ gives $V_\beta = V_\gamma$. [guided] We need a basic structural fact about the hierarchy before using ranks: later, if an element $y$ lies in some $V_{\beta_y}$ and $\beta_y \leq \delta$, we want to conclude that $y \in V_\delta$. This is exactly monotonicity. Fix an ordinal $\gamma$. We prove by transfinite induction on $\gamma$ that whenever $\beta \in \gamma$, one has $V_\beta \subseteq V_\gamma$. For $\gamma = 0$, there is no ordinal $\beta \in 0$, so there is nothing to prove. Suppose $\gamma = \delta + 1$. Let $\beta \in \gamma$. Then either $\beta = \delta$ or $\beta \in \delta$. If $\beta = \delta$, then \begin{align*} V_\gamma = V_{\delta+1} = \mathcal{P}(V_\delta). \end{align*} The cumulative hierarchy is transitive at each stage: every element of $V_\delta$ is a subset of $V_\delta$. Therefore every element of $V_\delta$ is an element of $\mathcal{P}(V_\delta)$, and hence $V_\delta \subseteq V_{\delta+1} = V_\gamma$. If $\beta \in \delta$, the induction hypothesis gives $V_\beta \subseteq V_\delta$, and the previous paragraph gives $V_\delta \subseteq V_\gamma$, so $V_\beta \subseteq V_\gamma$ by transitivity of inclusion. Now suppose $\gamma$ is a nonzero limit ordinal. Let $\beta \in \gamma$. By the definition of the hierarchy at limit stages, \begin{align*} V_\gamma = \bigcup_{\xi \in \gamma} V_\xi. \end{align*} Since $\beta$ is one of the indices in this union, every element of $V_\beta$ belongs to $V_\gamma$. Hence $V_\beta \subseteq V_\gamma$. This proves $V_\beta \subseteq V_\gamma$ whenever $\beta \in \gamma$. If $\beta = \gamma$, then $V_\beta = V_\gamma$, so in all cases $\beta \leq \gamma$ implies $V_\beta \subseteq V_\gamma$. [/guided] [/step] [step:Apply set induction to reduce the theorem to the elements of a fixed set] By Foundation, it suffices to prove the assertion by set induction. Define the property \begin{align*} P(x) \quad \Longleftrightarrow \quad \text{there exists an ordinal } \alpha \text{ such that } x \in V_\alpha . \end{align*} Let $x$ be an arbitrary set and assume the induction hypothesis: \begin{align*} \forall y \in x \, P(y). \end{align*} That is, for every $y \in x$, there exists an ordinal $\alpha$ such that $y \in V_\alpha$. We must prove $P(x)$. [guided] The [Axiom of Foundation](/page/Axiom%20of%20Foundation) gives the [set-induction](/page/Set%20Induction) principle: to prove that every set has a property $P$, it is enough to prove that an arbitrary set $x$ has $P$ under the assumption that every element of $x$ has $P$. Here the property is \begin{align*} P(x) \quad \Longleftrightarrow \quad \text{there exists an ordinal } \alpha \text{ such that } x \in V_\alpha . \end{align*} So fix a set $x$ and assume that every element $y \in x$ already appears somewhere in the cumulative hierarchy. Formally, for each $y \in x$, there exists an ordinal $\alpha$ such that $y \in V_\alpha$. The task is to build one ordinal level that contains $x$ itself. [/guided] [/step] [step:Collect the least hierarchy levels of the elements of $x$] For each $y \in x$, let $\rho(y)$ be the least ordinal $\alpha$ such that $y \in V_\alpha$. This ordinal exists by the induction hypothesis and exists uniquely because the ordinals are well-ordered by membership. Define \begin{align*} R := \{\rho(y) : y \in x\}. \end{align*} By Replacement, $R$ is a set of ordinals. Let \begin{align*} \delta := \bigcup R. \end{align*} Then $\delta$ is an ordinal, and for every $y \in x$ we have $\rho(y) \in \delta$ or $\rho(y) = \delta$. [guided] For each element $y \in x$, the induction hypothesis gives at least one ordinal $\alpha$ with $y \in V_\alpha$. Choose one witness ordinal $\alpha_y$ such that $y \in V_{\alpha_y}$. The possible witnesses below or equal to $\alpha_y$ form the set \begin{align*} A_y := \{\alpha \in \alpha_y \cup \{\alpha_y\} : y \in V_\alpha\}. \end{align*} This set is nonempty because $\alpha_y \in A_y$. Since the [ordinals](/page/Ordinal) are well-ordered by membership, $A_y$ has a least element. Define $\rho(y)$ to be that least ordinal: \begin{align*} \rho(y) := \min A_y. \end{align*} If $\beta$ is any ordinal with $y \in V_\beta$, then applying the same construction with the witness $\beta$ shows that no smaller witness is missed; hence $\rho(y)$ is the least ordinal such that $y \in V_\rho(y)$. This definition is legitimate for every $y \in x$ by the induction hypothesis. Now we need one ordinal that works uniformly for all elements of $x$. The [Axiom Schema of Replacement](/page/Axiom%20Schema%20of%20Replacement) is used precisely here: the assignment $y \mapsto \rho(y)$ is a definable functional assignment on the set $x$, so its image \begin{align*} R := \{\rho(y) : y \in x\} \end{align*} is a set. Since each $\rho(y)$ is an ordinal, $R$ is a set of ordinals. Define the supremum ordinal of these ranks by \begin{align*} \delta := \bigcup R. \end{align*} The union of a set of ordinals is an ordinal. Moreover, for every $y \in x$, the ordinal $\rho(y)$ belongs to $R$, so $\rho(y) \leq \delta$, meaning $\rho(y) \in \delta$ or $\rho(y) = \delta$. [/guided] [/step] [step:Place every element of $x$ into a single hierarchy level] Let $y \in x$. By definition of $\rho(y)$, we have $y \in V_{\rho(y)}$. Since $\rho(y) \leq \delta$, monotonicity of the cumulative hierarchy gives \begin{align*} V_{\rho(y)} \subseteq V_\delta. \end{align*} Hence $y \in V_\delta$. Since $y \in x$ was arbitrary, this proves \begin{align*} x \subseteq V_\delta. \end{align*} [guided] Fix an arbitrary element $y \in x$. By the definition of $\rho(y)$, we know \begin{align*} y \in V_{\rho(y)}. \end{align*} From the construction of $\delta = \bigcup R$, we also know $\rho(y) \leq \delta$. The monotonicity of the cumulative hierarchy therefore gives \begin{align*} V_{\rho(y)} \subseteq V_\delta. \end{align*} Combining these two facts yields $y \in V_\delta$. Because the argument works for every $y \in x$, every element of $x$ lies in $V_\delta$. Therefore \begin{align*} x \subseteq V_\delta. \end{align*} This is the key transition: the induction hypothesis gave separate hierarchy levels for the separate elements of $x$, and the supremum construction has converted them into one common level. [/guided] [/step] [step:Move from containment of the elements to membership of the set] Since $x \subseteq V_\delta$, we have \begin{align*} x \in \mathcal{P}(V_\delta). \end{align*} By the successor-stage definition of the cumulative hierarchy, \begin{align*} V_{\delta+1} = \mathcal{P}(V_\delta). \end{align*} Therefore $x \in V_{\delta+1}$. Thus $P(x)$ holds. By [set induction](/page/Set%20Induction), $P(x)$ holds for every set $x$. Hence for every set $x$ there exists an ordinal $\alpha$ such that $x \in V_\alpha$. [guided] We have reached the point where all elements of $x$ lie in one hierarchy level: \begin{align*} x \subseteq V_\delta. \end{align*} The successor-stage definition of the [cumulative hierarchy](/page/Cumulative%20Hierarchy) says that the next level is the power set of the current level: \begin{align*} V_{\delta+1} = \mathcal{P}(V_\delta). \end{align*} Since $x \subseteq V_\delta$, the defining property of the power set gives \begin{align*} x \in \mathcal{P}(V_\delta). \end{align*} Combining the two displayed facts yields $x \in V_{\delta+1}$. Therefore the property \begin{align*} P(x) \quad \Longleftrightarrow \quad \text{there exists an ordinal } \alpha \text{ such that } x \in V_\alpha \end{align*} holds for the arbitrary set $x$ under the induction hypothesis that $P(y)$ holds for every $y \in x$. By [set induction](/page/Set%20Induction), $P(x)$ holds for every set $x$. Thus for every set $x$ there exists an ordinal $\alpha$ such that $x \in V_\alpha$. [/guided] [/step]